DOI: 10.1515/mr-2021-0016
TahcoRoll:fast genomic signature profiling via thinned automaton and rolling hash
Chelsea J.-T.Ju
Jyun-Yu Jiang
Ruirui Li
Zeyu Li
Wei Wang
Department of Computer Science,University of California,Los Angeles,USA
摘要：Objectives: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.Methods: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.Results:In extensive experiments,TahcoRoll signifi-cantly 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.Conclusions: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.
机标关键词：signatureprofilingautomatonrollinghashgenomicfasttahcoroll
论文发表日期：2021-04-28
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：12( 114-125 )
英文信息