title: A new efficient algorithm for inferring explicit hybridization networks following the Neighbor-Joining principle.
abstract: 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.
authors.affiliation: Département d'informatique, Université du Québec à Montréal, Case postale 8888, Succursale Centre-ville, Montréal (Québec) H3C 3P8, Canada.
authors.forename: Matthieu
authors.initials: M
authors.lastname: Willems
authors.forename: Nadia
authors.initials: N
authors.lastname: Tahiri
authors.forename: Vladimir
authors.initials: V
authors.lastname: Makarenkov
mesh_terms: D000465:Algorithms; D000818:Animals; D005075:Biological Evolution; D019295:Computational Biology; D003198:Computer Simulation; D009033:Culicidae / Q000145:classification / Q000235:genetics; D030541:Databases, Genetic; D004171:Diploidy; D006824:Hybridization, Genetic; D016018:Least-Squares Analysis; D008957:Models, Genetic; D010802:Phylogeny; D010944:Plants / Q000145:classification / Q000235:genetics; D011123:Polyploidy; D012984:Software
keywords: Hybridization networks; Neighbor-Joining; phylogenetic trees