The Restriction Scaffold Problem
- 1 June 2003
- journal article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 10 (3-4) , 385-398
Abstract
Most shotgun sequencing projects undergo a long and costly phase of finishing, in which a partial assembly forms several contigs whose order, orientation, and relative distance is unknown. We propose here a new technique that supplements the shotgun assembly data by experimentally simple and commonly used complete restriction digests of the target. By computationally combining information from the contig sequences and the fragment sizes measured for several different enzymes, we seek to form a "scaffold" on which the contigs will be placed in their correct orientation, order, and distance. We give a heuristic search algorithm for solving the problem and report on promising preliminary simulation results. The key to the success of the search scheme is the very rapid solution of two time-critical subproblems that are solved to optimality in linear time. Our simulations indicate that with noise levels of some 3% relative error in measuring fragment sizes, using six enzymes, most datasets of 13 contigs spanning 300kb can be correctly ordered, and the remaining ones have most of their pairs of neighboring contigs correct. Hence, the technique has a potential to provide real help to finishing. Even without closing all gaps, the ability to order and orient the contigs correctly makes the partial assembly both more accessible and more useful for biologists.Keywords
This publication has 11 references indexed in Scilit:
- A Clone-Array Pooled Shotgun Strategy for Sequencing Large GenomesGenome Research, 2001
- The greedy path-merging algorithm for sequence assembly2001
- Automated Finishing with AutofinishGenome Research, 2001
- The Sequence of the Human GenomeScience, 2001
- Initial sequencing and analysis of the human genomeNature, 2001
- Optimized Multiplex PCR: Efficiently Closing a Whole-Genome Shotgun Sequencing ProjectGenomics, 1999
- A new strategy for genome sequencingNature, 1996
- Pairwise end sequencing: a unified approach to genomic mapping and sequencingGenomics, 1995
- Optimization by Simulated AnnealingScience, 1983
- Two special cases of the assignment problemDiscrete Mathematics, 1975