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

John Moriarty; Julian R. Marchesi; Anthony Metcalfe

doi:10.1186/1471-2105-8-70

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

John Moriarty, Julian R. Marchesi, Anthony Metcalfe

Research output: Contribution to journal › Article › peer-review

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. © 2007 Moriarty et al; licensee BioMed Central Ltd.

Original language	English
Article number	70
Journal	BMC Bioinformatics
Volume	8
DOIs	https://doi.org/10.1186/1471-2105-8-70
Publication status	Published - 2 Mar 2007

Access to Document

10.1186/1471-2105-8-70

http://www.biomedcentral.com/1471-2105/8/70

Cite this

@article{eafb053ea609419bb002f7283eea3f87,

title = "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",

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. {\textcopyright} 2007 Moriarty et al; licensee BioMed Central Ltd.",

author = "John Moriarty and Marchesi, {Julian R.} and Anthony Metcalfe",

note = "The research of all the authors except JRM was supported by Science Foundation Ireland under Grant Number SFI 04/RP1/I512. JRM's work was supported by the Irish Government under the National Development Plan (2000–2006) and Science Foundation Ireland.",

year = "2007",

month = mar,

day = "2",

doi = "10.1186/1471-2105-8-70",

language = "English",

volume = "8",

journal = "BMC Bioinformatics",

issn = "1471-2105",

publisher = "Springer Nature",

}

TY - JOUR

T1 - 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

AU - Moriarty, John

AU - Marchesi, Julian R.

AU - Metcalfe, Anthony

N1 - The research of all the authors except JRM was supported by Science Foundation Ireland under Grant Number SFI 04/RP1/I512. JRM's work was supported by the Irish Government under the National Development Plan (2000–2006) and Science Foundation Ireland.

PY - 2007/3/2

Y1 - 2007/3/2

N2 - 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. © 2007 Moriarty et al; licensee BioMed Central Ltd.

AB - 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. © 2007 Moriarty et al; licensee BioMed Central Ltd.

U2 - 10.1186/1471-2105-8-70

DO - 10.1186/1471-2105-8-70

M3 - Article

SN - 1471-2105

VL - 8

JO - BMC Bioinformatics

JF - BMC Bioinformatics

M1 - 70

ER -

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

Abstract

Access to Document

Fingerprint

Cite this