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

J Bioinform Comput Biol

Département d'informatique, Université du Québec à Montréal, Case postale 8888, Succursale Centre-ville, Montréal (Québec) H3C 3P8, Canada.

Published: October 2014

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.

Download full-text PDF

Source
http://dx.doi.org/10.1142/S0219720014500243DOI Listing

Publication Analysis

Top Keywords

algorithm inferring
8
hybridization networks
8
efficient algorithm
4
inferring explicit
4
hybridization
4
explicit hybridization
4
networks
4
networks neighbor-joining
4
neighbor-joining principle
4
principle algorithms
4

Similar Publications

Want AI Summaries of new PubMed Abstracts delivered to your In-box?

Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!