Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum-Evolution Principle - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2002

Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum-Evolution Principle

Abstract

This paper investigates the standard ordinary least-squares version [24] and the balanced version [20] of the minimum evolution principle. For the standard version, we provide a greedy construction algorithm (GME) which produces a starting topology in O(n 2) time, and a tree swapping algorithm (FASTNNI) that searches for the best topology using nearest neighbor interchanges (NNIs), where the cost of doing p NNIs is O(n 2 + pn), i.e. O(n 2) in practice because p is always much smaller than n. The combination of GME and FASTNNI produces trees which are fairly close to Neighbor Joining (NJ) trees in terms of topological accuracy, especially with large trees. We also provide two closely related algorithms for the balanced version, called BME and BNNI, respectively. BME requires O(n 2 × diam(T)) operations to build the starting tree, and BNNI is in O(n 2 + pn × diam(T)), where diam(T) is the topological diameter of the output tree. In the usual Yule-Harding distribution on phylogenetic trees, the diameter expectation is in log(n), so our algorithms are in practice faster that NJ. Furthermore, BNNI combined with BME (or GME) has better topological accuracy than NJ, BIONJ and WEIGHBOR (all three in O(n 3)), especially with large trees.
Fichier principal
Vignette du fichier
ark__67375_HCB-T82SRHFK-0.pdf (821 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-00269513 , version 1 (17-10-2023)

Identifiers

Cite

Richard Desper, Olivier Gascuel. Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum-Evolution Principle. WABI 2002 - 2nd International Workshop on Algorithms in Bioinformatics, Sep 2002, Roma, Italy. pp.357-374, ⟨10.1007/3-540-45784-4_27⟩. ⟨lirmm-00269513⟩
100 View
11 Download

Altmetric

Share

Gmail Facebook X LinkedIn More