This work revisits the classic problem of coverage in genomic shotgun assembly (the “Lander-Waterman statistics”). A novel formulation, based on the analysis of an autonomous Markov automaton, is presented, and two main conclusions are derived. The first is an evaluation of the minimum multiplicity (“coverage”) required to achieve uninterrupted covering (one single contig) with a prescribed confidence level. The second is a detailed analysis of the effect of replacing the hypothesis of fixed-length genomic fragments with that of an arbitrary distribution of lengths over a finite interval.
Get full access to this article
View all access options for this article.
References
1.
ArratiaR., LanderE.S., TavaréS., WatermanM.S.1991. Genomic mapping by anchoring random clones: a mathematical analysis. Genomics, 11:806–827.
2.
EwensW.J., GrantG.R.2005. Statistical Methods in Bioinformatics. An Introduction. Springer Verlag: Berlin/Heidelberg.
3.
LanderE.S., WatermanM.S.1988. Genomic mapping by fingerprinting random clones: a mathematical analysis. Genomics, 2:231–239.
4.
WatermanM.S.1995. Introduction to Computational Biology: Maps, Sequences and Genomes. CRC Press: Boca Raton, FL.
5.
ZadehL.A., DesoerC.A.1963. Linear System Theory: The State Space Approach. McGraw-Hill Book Company: New York.
