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 language | English (US) |
|---|---|
| Pages | 22-30 |
| Number of pages | 9 |
| DOIs | |
| State | Published - 2001 |
| Externally published | Yes |
| Event | 5th Annual Internatinal Conference on Computational Biology - Montreal, Que., Canada Duration: May 22 2001 → May 26 2001 |
Other
| Other | 5th Annual Internatinal Conference on Computational Biology |
|---|---|
| Country/Territory | Canada |
| City | Montreal, Que. |
| Period | 5/22/01 → 5/26/01 |
All Science Journal Classification (ASJC) codes
- General Computer Science
- General Biochemistry, Genetics and Molecular Biology