TahcoRoll: fast genomic signature profiling via thinned automaton and rolling hash.
TahcoRoll: fast genomic signature profiling via thinned automaton and rolling hash.
复制标题
DOI：
10.1515/mr-2021-0016
复制
发表时间：
2021-12-20
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
像k-MERS这样的基因组签名已经成为描述基因组数据的最重要的方法之一。因此，无数现实世界的应用，如基因组组装中de Bruijn图的构建，都得益于识别基因组签名。换句话说，一种有效的基因组签名分析方法是解决高通量测序读数的基本需要。然而，现有的方法大多只识别固定大小的k-MERS，而许多研究表明了考虑可变长度k-MERS的重要性。本文通过对Aho-Corasick算法(AC)的扩展，提出了一种新的基因组签名分析方法TahcoRoll，用于分析可变长度k-MERS。我们首先将核苷酸分成两个簇，并用一个比特表示每个簇。滚动散列技术还被用来编码签名和读取模式以进行有效的匹配。在广泛的实验中，TahcoRoll的性能显著优于最先进的k-mer计数器，并具有在经济型台式计算机上跨不同测序平台处理读取的能力。单线程版本的TahcoRoll与最先进的水母的八线程版本的效率一样高，而八线程的TahcoRoll的性能至少是八线程水母的四倍。
Genomic signatures like k-mers have become one of the most prominent approaches to describe genomic data. As a result, myriad real-world applications, such as the construction of de Bruijn graphs in genome assembly, have been benefited by recognizing genomic signatures. In other words, an efficient approach of genomic signature profiling is an essential need for tackling high-throughput sequencing reads. However, most of the existing approaches only recognize fixed-size k-mers while many research studies have shown the importance of considering variable-length k-mers. In this paper, we present a novel genomic signature profiling approach, TahcoRoll, by extending the Aho–Corasick algorithm (AC) for the task of profiling variable-length k-mers. We first group nucleotides into two clusters and represent each cluster with a bit. The rolling hash technique is further utilized to encode signatures and read patterns for efficient matching. In extensive experiments, TahcoRoll significantly outperforms the most state-of-the-art k-mer counters and has the capability of processing reads across different sequencing platforms on a budget desktop computer. The single-thread version of TahcoRoll is as efficient as the eight-thread version of the state-of-the-art, JellyFish, while the eight-thread TahcoRoll outperforms the eight-thread JellyFish by at least four times.