Efficient construction of an assembly string graph using the FM-index.
Efficient construction of an assembly string graph using the FM-index.
复制标题
DOI：
10.1093/bioinformatics/btq217
复制
发表时间：
2010-06-15
期刊：
影响因子：
--
通讯作者：
Durbin R
中科院分区：
文献类型：
--
作者：
Simpson JT;Durbin R
动机：序列组装是一个困难的问题，随着测序成本的大幅下降，它的重要性最近再次上升。大多数新的序列组装软件都是从构建de Bruijn图开始的，避免了以前使用的基于重叠的方法，因为这些方法的计算成本和复杂性具有非常大量的短读取。在这里，我们展示了如何使用基于后缀数组的方法，这些方法构成了最近非常快速的序列映射算法的基础，以查找重叠并以渐进的速度生成汇编字符串图的速度比前面描述的算法要快。结果：标准重叠组装方法的时间复杂度为O(N2)，其中N为读出长度之和。我们使用源自Burrow-Wheeler变换的费拉吉纳-曼齐尼指数(FM-INDEX)在一组读数中找到长度至少为τ的重叠。以及一种找到所有重叠然后执行传递约简以生成字符串图的方法，我们展示了如何仅直接输出不可约的重叠，显著减少了内存需求，并将计算时间减少到O(N)，而与深度无关。基于重叠的组装方法自然处理混合长度读取组，包括第三代测序技术承诺的毛细管读数或长读数。我们在这里提出的算法为基于重叠的组装方法发展到整个脊椎动物基因组从头组装铺平了道路。联系方式：js18@sanger.ac.uk
Motivation: Sequence assembly is a difficult problem whose importance has grown again recently as the cost of sequencing has dramatically dropped. Most new sequence assembly software has started by building a de Bruijn graph, avoiding the overlap-based methods used previously because of the computational cost and complexity of these with very large numbers of short reads. Here, we show how to use suffix array-based methods that have formed the basis of recent very fast sequence mapping algorithms to find overlaps and generate assembly string graphs asymptotically faster than previously described algorithms. Results: Standard overlap assembly methods have time complexity O(N2), where N is the sum of the lengths of the reads. We use the Ferragina–Manzini index (FM-index) derived from the Burrows–Wheeler transform to find overlaps of length at least τ among a set of reads. As well as an approach that finds all overlaps then implements transitive reduction to produce a string graph, we show how to output directly only the irreducible overlaps, significantly shrinking memory requirements and reducing compute time to O(N), independent of depth. Overlap-based assembly methods naturally handle mixed length read sets, including capillary reads or long reads promised by the third generation sequencing technologies. The algorithms we present here pave the way for overlap-based assembly approaches to be developed that scale to whole vertebrate genome de novo assembly. Contact: js18@sanger.ac.uk
登录
查看更多内容
影响因子：
7
作者：
Chaisson, Mark J.;Pevzner, Pavel A.
通讯作者：
Pevzner, Pavel A.
影响因子：
7
作者：
Simpson, Jared T.;Wong, Kim;Birol, Inanc
通讯作者：
Birol, Inanc
影响因子：
12.3
作者：
Langmead B;Trapnell C;Pop M;Salzberg SL
通讯作者：
Salzberg SL
DOI：
10.1093/bioinformatics/btp698
发表时间：
2010-03-01
期刊：
Bioinformatics (Oxford, England)
影响因子：
--
作者：
Li H;Durbin R
通讯作者：
Durbin R
SOAP2：改进的超快工具，用于短读对齐
影响因子：
5.8
作者：
Li, Ruiqiang;Yu, Chang;Wang, Jun
通讯作者：
Wang, Jun