An optimal procedure for gap closing in whole genome shotgun sequencing

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.