A greedy alignment-free distance estimator for phylogenetic inference

BMC Bioinformatics

Research

Sharma V. Thankachan¹  Sriram P. Chockalingam²  Srinivas Aluru³  Yongchao Liu⁴  Ambujam Krishnan⁵ 

[1] Department of Computer Science, University of Central Florida, 32816, Orlando, FL, USA;Institute for Data Engineering and Science, Georgia Institute of Technology, 30332, Atlanta, GA, USA;Institute for Data Engineering and Science, Georgia Institute of Technology, 30332, Atlanta, GA, USA;School of Computational Science and Engineering, Georgia Institute of Technology, 30332, Atlanta, GA, USA;School of Computational Science and Engineering, Georgia Institute of Technology, 30332, Atlanta, GA, USA;School of Electrical Engineering and Computer Science, Louisiana State University, 70703, Baton Rouge, LA, USA;

关键词: Alignment-free methods;    Sequence comparison;    Phylogeny reconstruction;   

DOI  :  10.1186/s12859-017-1658-0

来源: Springer

【 摘 要 】

BackgroundAlignment-free sequence comparison approaches have been garnering increasing interest in various data- and compute-intensive applications such as phylogenetic inference for large-scale sequences. While k-mer based methods are predominantly used in real applications, the average common substring (ACS) approach is emerging as one of the prominent alignment-free approaches. This ACS approach has been further generalized by some recent work, either greedily or exactly, by allowing a bounded number of mismatches in the common substrings.ResultsWe present ALFRED-G, a greedy alignment-free distance estimator for phylogenetic tree reconstruction based on the concept of the generalized ACS approach. In this algorithm, we have investigated a new heuristic to efficiently compute the lengths of common strings with mismatches allowed, and have further applied this heuristic to phylogeny reconstruction. Performance evaluation using real sequence datasets shows that our heuristic is able to reconstruct comparable, or even more accurate, phylogenetic tree topologies than the kmacs heuristic algorithm at highly competitive speed.ConclusionsALFRED-G is an alignment-free heuristic for evolutionary distance estimation between two biological sequences. This algorithm is implemented in C++ and has been incorporated into our open-source ALFRED software package (http://alurulab.cc.gatech.edu/phylo).

【 授权许可】

CC BY   
© The Author(s) 2017

【 图 表 】

Fig. 9

Fig. 1

12951_2015_155_Article_IEq34.gif

12951_2015_155_Article_IEq33.gif

12951_2015_155_Article_IEq32.gif

Fig. 1

12864_2016_2889_Article_IEq3.gif

Fig. 1