ALFRED: A Practical Method for Alignment-Free Distance Computation

作者：Thankachan Sharma V; Chockalingam Sriram P; Liu Yongchao; Apostolico Alberto; Aluru Srinivas^*

来源：Journal of Computational Biology, 2016, 23(6): 452-460.

DOI：10.1089/cmb.2015.0217

• suffix trees
• approximate string matching
• phylogenetic tree

Alignment-free approaches are gaining persistent interest in many sequence analysis applications such as phylogenetic inference and metagenomic classification/clustering, especially for large-scale sequence datasets. Besides the widely used k-mer methods, the average common substring (ACS) approach has emerged to be one of the well-known alignment-free approaches. Two recent works further generalize this ACS approach by allowing a bounded number k of mismatches in the common substrings, relying on approximation (linear time) and exact computation, respectively. Albeit having a good worst-case time complexity O(n log(k) n), the exact approach is complex and unlikely to be efficient in practice. Herein, we present ALFRED, an alignment-free distance computation method, which solves the generalized common substring search problem via exact computation. Compared to the theoretical approach, our algorithm is easier to implement and more practical to use, while still providing highly competitive theoretical performances with an expected run-time of O(n logk n). By applying our program to phylogenetic inference as a case study, we find that our program facilitates to exactly reconstruct the topology of the reference phylogenetic tree for a set of 27 primate mitochondrial genomes, at reasonably acceptable speed. ALFRED is implemented in C++ programming language and the source code is freely available online.

• 出版日期2016-6