Graphical pan-genome analysis with compressed suffix trees and the Burrows-Wheeler transform
Graphical pan-genome analysis with compressed suffix trees and the Burrows-Wheeler transform
复制标题
DOI：
10.1093/bioinformatics/btv603
复制
发表时间：
2016-02-15
期刊：
影响因子：
5.8
通讯作者：
Ohlebusch, Enno
中科院分区：
文献类型：
--
作者：
Baier, Uwe;Beller, Timo;Ohlebusch, Enno
动机：低成本的基因组测序提供了有关人群遗传结构的前所未有的完整信息，人口图捕获了许多人群的许多人之间的变化。最近，Marcus等。建议使用压缩的de bruijn图代表整个基因组群体。他们设计了一个称为splitMem的O（n log g）时间算法，该算法直接基于后缀树直接构造此图（即不使用未压缩的de bruijn图），其中n是基因组的总长度，g是g的长度。最长的基因组。由于其算法的适用性仅限于相当小的数据集，因此对空间有效的构造算法的需求非常需要：我们提出的两种算法在理论上和实践中都优于Splitmem。第一个通过压缩的后缀树实现了新型线性后缀树算法。第二算法使用burrows-wheeler变换在O（n log Sigma）时间中构建压缩的de bruijn图，其中Sigma是字母的大小。为了证明算法的可伸缩性，我们将其应用于七个人类基因组。
Motivation: Low-cost genome sequencing gives unprecedented complete information about the genetic structure of populations, and a population graph captures the variations between many individuals of a population. Recently, Marcus et al. proposed to use a compressed de Bruijn graph for representing an entire population of genomes. They devised an O(n log g) time algorithm called splitMEM that constructs this graph directly (i.e. without using the uncompressed de Bruijn graph) based on a suffix tree, where n is the total length of the genomes and g is the length of the longest genome. Since the applicability of their algorithm is limited to rather small datasets, there is a strong need for space-efficient construction algorithms.Results: We present two algorithms that outperform splitMEM in theory and in practice. The first implements a novel linear-time suffix tree algorithm by means of a compressed suffix tree. The second algorithm uses the Burrows-Wheeler transform to build the compressed de Bruijn graph in O(n log sigma) time, where sigma is the size of the alphabet. To demonstrate the scalability of the algorithms, we applied it to seven human genomes.