Minimum Tree Cost Quartet Puzzling

Abstract : We present a new distance based quartet method for phylogenetic tree reconstruction, called Minimum Tree Cost Quartet Puzzling. Starting from a distance matrix computed from natural data, the algorithm incrementally constructs a tree by adding one taxon at a time to the intermediary tree using a cost function based on the relaxed 4-point condition for weighting quartets. Different input orders of taxa lead to trees having distinct topologies which can be evaluated using a maximum likelihood or weighted least squares optimality criterion. Using reduced sets of quartets and a simple heuristic tree search strategy we obtain an overall complexity of O(n5 log2 n) for the algorithm. We evaluate the performances of the method through comparative tests and show that our method outperforms NJ when a weighted least squares optimality criterion is employed. We also discuss the theoretical boundaries of the algorithm.
Document type :
Journal articles
Complete list of metadatas

https://hal-supelec.archives-ouvertes.fr/hal-00530627
Contributor : Evelyne Faivre <>
Submitted on : Friday, October 29, 2010 - 3:15:23 PM
Last modification on : Tuesday, August 21, 2018 - 11:40:04 AM

Links full text

Identifiers

Collections

Citation

Tudor B. Ionescu, Géraldine Polaillon, Frédéric Boulanger. Minimum Tree Cost Quartet Puzzling. Journal of Classification, Springer Verlag, 2010, 27 (2), pp.136-157. ⟨10.1007/s00357-010-9053-9⟩. ⟨hal-00530627⟩

Share

Metrics

Record views

175