Efficient Construction of a Complete Index for Pan-Genomics Read Alignment
Efficient Construction of a Complete Index for Pan-Genomics Read Alignment
复制标题
DOI：
10.1089/cmb.2019.0309
复制
发表时间：
2020-03-16
影响因子：
1.7
通讯作者：
Manzini, Giovanni
中科院分区：
文献类型：
--
作者：
Kuhnle, Alan;Mun, Taher;Manzini, Giovanni
短读比对主要使用FM索引，其能够容易地索引一个或几个人类基因组。然而，它不能很好地扩展到索引数千个基因组的集合。驱动这个问题的是索引的两个主要组成部分：（1）字符串的Burrows-Wheeler变换（BWT）上的秩数据结构，它允许我们在字符串的后缀数组（SA）中找到区间，以及（2）SA的样本，当与秩数据结构一起使用时，它允许我们访问SA。即使对于大型基因组数据库，通过行程长度压缩BWT，秩数据结构也可以保持较小，但是直到最近，还没有已知的方法可以在不大大减慢对SA的访问的情况下保持SA样本较小。现在（SODA 2018）已经定义了一个SA样本，它占用的空间与游程压缩的BWT相同，我们已经设计了基因组数据库的高效FM索引，但面临着构建它们的问题。在2018年，我们展示了如何有效地构建大型基因组数据库的BWT（WABI 2018），但有效构建样本的问题仍然悬而未决。我们比较了我们的方法，以国家的最先进的方法来构建SA样本，并证明这是最快的和最节省空间的方法在高度重复的基因组数据库。最后，我们应用我们的方法索引部分和整个人类基因组，并表明它改善了FM索引为基础的Bowtie方法的内存和时间，并在混合索引为基础的CHIC方法的查询时间和索引所需的内存。
Short-read aligners predominantly use the FM-index, which is easily able to index one or a few human genomes. However, it does not scale well to indexing collections of thousands of genomes. Driving this issue are the two chief components of the index: (1) a rank data structure over the Burrows-Wheeler Transform (BWT) of the string that will allow us to find the interval in the string's suffix array (SA), and (2) a sample of the SA that-when used with the rank data structure-allows us to access the SA. The rank data structure can be kept small even for large genomic databases, by run-length compressing the BWT, but until recently there was no means known to keep the SA sample small without greatly slowing down access to the SA. Now that (SODA 2018) has defined an SA sample that takes about the same space as the run-length compressed BWT, we have the design for efficient FM-indexes of genomic databases but are faced with the problem of building them. In 2018, we showed how to build the BWT of large genomic databases efficiently (WABI 2018), but the problem of building the sample efficiently was left open. We compare our approach to state-of-the-art methods for constructing the SA sample, and demonstrate that it is the fastest and most space-efficient method on highly repetitive genomic databases. Lastly, we apply our method for indexing partial and whole human genomes and show that it improves over the FM-index-based Bowtie method with respect to both memory and time and over the hybrid index-based CHIC method with respect to query time and memory required for indexing.