Minimum Tree Cost Quartet Puzzling |
| |
Authors: | Tudor B Ionescu Géraldine Polaillon Frédéric Boulanger |
| |
Institution: | (1) Bioinformatics Laboratory and National Laboratory of Bromacromolecules, Institute of Biophysics, Chinese Academy of Sciences, Beijing, 100101, China;(2) Bioinformatics Research Group, Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Beijing, 100080, China;(3) Graduate School of the Chinese Academy of Sciences, Beijing, China |
| |
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(n
5 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|