Minimum Tree Cost Quartet Puzzling - Archive ouverte HAL Access content directly
Journal Articles Journal of Classification Year : 2010

Minimum Tree Cost Quartet Puzzling


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.

Dates and versions

hal-00530627 , version 1 (29-10-2010)



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



Gmail Facebook Twitter LinkedIn More