A new efficient algorithm for inferring explicit hybridization networks following the Neighbor-Joining principle

作者：Willems Matthieu; Tahiri Nadia; Makarenkov Vladimir^*

来源：Journal of Bioinformatics and Computational Biology, 2014, 12(5): 1450024.

DOI：10.1142/S0219720014500243

• Hybridization networks
• Neighbor-Joining
• phylogenetic trees

Several algorithms and software have been developed for inferring phylogenetic trees. However, there exist some biological phenomena such as hybridization, recombination, or horizontal gene transfer which cannot be represented by a tree topology. We need to use phylogenetic networks to adequately represent these important evolutionary mechanisms. In this article, we present a new efficient heuristic algorithm for inferring hybridization networks from evolutionary distance matrices between species. The famous Neighbor-Joining concept and the least-squares criterion are used for building networks. At each step of the algorithm, before joining two given nodes, we check if a hybridization event could be related to one of them or to both of them. The proposed algorithm finds the exact tree solution when the considered distance matrix is a tree metric (i.e. it is representable by a unique phylogenetic tree). It also provides very good hybrids recovery rates for large trees (with 32 and 64 leaves in our simulations) for both distance and sequence types of data. The results yielded by the new algorithm for real and simulated datasets are illustrated and discussed in detail.

• 出版日期2014-10