The fragment assembly string graph
The fragment assembly string graph
复制标题
DOI：
10.1093/bioinformatics/bti1114
复制
发表时间：
2005-09-01
期刊：
影响因子：
5.8
通讯作者：
Myers, EW
中科院分区：
文献类型：
--
作者：
Myers, EW
我们提出了一个概念和形式，字符串图，它代表了从收集的一组鸟枪测序读数中关于DNA序列的所有可推断的东西。我们给出了在给定读数之间重叠的集合的情况下构造字符串图的时间和空间高效的算法，特别是在这种情况下，提出了一种新的线性期望时间算法。结果表明，在前面描述的De Bruijn图方法中使用的Kmer的分解是不必要的，并暴露了它与我们在Celera开发的Untig方法的密切联系。本文是一个初步的工作，给出了基本算法和结果，证明了该方法的有效性和可扩展性。这些想法正被用来建造下一代全基因组组装器，称为BOA(伯克利开放组装器)，它将很容易地扩展到哺乳动物基因组。
We present a concept and formalism, the string graph, which represents all that is inferable about a DNA sequence from a collection of shotgun sequencing reads collected from it. We give time and space efficient algorithms for constructing a string graph given the collection of overlaps between the reads and, in particular, present a novel linear expected time algorithm for transitive reduction in this context. The result demonstrates that the decomposition of reads into kmers employed in the de Bruijn graph approach described earlier is not essential, and exposes its close connection to the unitig approach we developed at Celera. This paper is a preliminary piece giving the basic algorithm and results that demonstrate the efficiency and scalability of the method. These ideas are being used to build a next-generation whole genome assembler called BOA (Berkeley Open Assembler) that will easily scale to mammalian genomes.