Bounds on the distribution of the number of gaps when circles and lines are covered by fragments: theory and practical application to genomic and metagenomic projects

Loading...
Thumbnail Image
Files
JM_BoundsPV2007.pdf(197.14 KB)
Published Version
Date
2007-03-02
Authors
Moriarty, John
Marchesi, Julian R.
Metcalfe, Anthony
Journal Title
Journal ISSN
Volume Title
Publisher
BioMed Central
Published Version
Research Projects
Organizational Units
Journal Issue
Abstract
Background: The question of how a circle or line segment becomes covered when random arcs are marked off has arisen repeatedly in bioinformatics. The number of uncovered gaps is of particular interest. Approximate distributions for the number of gaps have been given in the literature, one motivation being ease of computation. Error bounds for these approximate distributions have not been given. Results: We give bounds on the probability distribution of the number of gaps when a circle is covered by fragments of fixed size. The absolute error in the approximation is typically on the order of 0.1% at 10× coverage depth. The method can be applied to coverage problems on the interval, including edge effects, and applications are given to metagenomic libraries and shotgun sequencing.
Description
Keywords
Gaps , Circles , Lines , Fragments , Genomic , Metagenomic , Bioinformatics
Citation
John Moriarty, Julian R Marchesi and Anthony Metcalf. (2007). Bounds on the distribution of the number of gaps when circles and lines are covered by fragments: Theory and practical application to genomic and metagenomic projects. BMC Bioinformatics. 8:70 doi:10.1186/1471-2105-8-70