Associate Editor1 School of Computer Science, University of Science and Technology of China, Heifei, Anhui, China2 Key Laboratory on High Performance Computing, Anhui Province, National University of Defense Technology, Changsha, China3 Collaborative Innovation Center of High Performance Computing, National University of Defense Technology, Changsha, China
Checking for direct PDF access through Ovid
MotivationAs a fundamental task in bioinformatics, searching for massive short patterns over a long text has been accelerated by various compressed full-text indexes. These indexes are able to provide similar searching functionalities to classical indexes, e.g. suffix trees and suffix arrays, while requiring less space. For genomic data, a well-known family of compressed full-text indexes, called FM-indexes, presents unmatched performance in practice. One major drawback of FM-indexes is that their locating operations, which report all occurrence positions of patterns in a given text, are not efficient, especially for the patterns with many occurrences.ResultsIn this paper, we introduce a novel locating algorithm, FMtree, to fast retrieve all occurrence positions of any pattern via FM-indexes. When searching for a pattern over a given text, FMtree organizes the search space of the locating operation into a conceptual multiway tree. As a result, multiple occurrence positions of this pattern can be retrieved simultaneously by traversing the multiway tree. Compared with existing locating algorithms, our tree-based algorithm reduces large numbers of redundant operations and presents better data locality. Experimental results show that FMtree is usually one order of magnitude faster than the state-of-the-art algorithms, and still memory-efficient.Availability and implementationFMtree is freely available at https://github.com/chhylp123/FMtree.