Optimal assembly for high throughput shotgun sequencing.
Optimal assembly for high throughput shotgun sequencing.
复制标题
DOI：
10.1186/1471-2105-14-s5-s18
复制
发表时间：
2013-01-01
影响因子：
3
通讯作者：
Tse, David
中科院分区：
文献类型：
--
作者：
Bresler, Guy;Bresler, Ma'ayan;Tse, David
我们提出了一个框架的最佳组装算法的设计鸟枪测序的标准下完全重建。我们推导出一个下限的读取长度和重建所需的基因组的重复统计的覆盖深度。在早期工作的基础上，我们设计了一个基于de Brujin图的组装算法，该算法可以实现非常接近广泛的测序基因组（包括GAGE数据集）的重复统计下限。这些结果是基于DNA序列和用于重建的读段的一组必要和充分条件。这些条件可以被视为鸟枪测序类似于Ukkonen-Pevzner的杂交测序的必要和充分条件。
We present a framework for the design of optimal assembly algorithms for shotgun sequencing under the criterion of complete reconstruction. We derive a lower bound on the read length and the coverage depth required for reconstruction in terms of the repeat statistics of the genome. Building on earlier works, we design a de Brujin graph based assembly algorithm which can achieve very close to the lower bound for repeat statistics of a wide range of sequenced genomes, including the GAGE datasets. The results are based on a set of necessary and sufficient conditions on the DNA sequence and the reads for reconstruction. The conditions can be viewed as the shotgun sequencing analogue of Ukkonen-Pevzner's necessary and sufficient conditions for Sequencing by Hybridization.