An optimal procedure for gap closing in whole genome shotgun sequencing

R. Beigel, N. Alon, M. S. Apaydin, L. Fortnow, S. Kasif

Research output: Contribution to conferencePaper

34 Scopus citations

Abstract

Tettelin et. al. proposed a new method for closing the gaps in whole genome shotgun sequencing projects. The method uses a multiplex PCR strategy in order to minimize the time and effort required to sequence the DNA in the missing gaps. This procedure has been used in a number of microbial sequencing projects including Streptococcus pneumoniae and other bacteria. In this paper we describe a theoretical framework for this problem and propose an improved method that guarantees to minimize the number of steps involved in the gap closure procedures. In particular, given a collection of n/2 DNA fragments we describe a strategy that requires 0.75n log n work in eight parallel rounds of experiments, closely matching a corresponding lower bound of 0.5n log n.

Original languageEnglish (US)
Pages22-30
Number of pages9
DOIs
StatePublished - 2001
Event5th Annual Internatinal Conference on Computational Biology - Montreal, Que., Canada
Duration: May 22 2001May 26 2001

Other

Other5th Annual Internatinal Conference on Computational Biology
CountryCanada
CityMontreal, Que.
Period5/22/015/26/01

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Biochemistry, Genetics and Molecular Biology(all)

Fingerprint Dive into the research topics of 'An optimal procedure for gap closing in whole genome shotgun sequencing'. Together they form a unique fingerprint.

  • Cite this

    Beigel, R., Alon, N., Apaydin, M. S., Fortnow, L., & Kasif, S. (2001). An optimal procedure for gap closing in whole genome shotgun sequencing. 22-30. Paper presented at 5th Annual Internatinal Conference on Computational Biology, Montreal, Que., Canada. https://doi.org/10.1145/369133.369152