×

zbMATH — the first resource for mathematics

The ultrametric constraint and its application to phylogenetics. (English) Zbl 1166.92033
Summary: A phylogenetic tree shows the evolutionary relationships among species. Internal nodes of the tree represent speciation events and the leaf nodes correspond to the species. A goal of phylogenetics is to combine such trees into larger trees, called supertrees, whilst respecting the relationships in the original trees. A rooted tree exhibits an ultrametric property; that is, for any three leaves of the tree it must be that one pair has a deeper most recent common ancestor than the other pairs, or that all three have the same most recent common ancestor. This inspires a constraint programming encoding for rooted trees.
We present an efficient constraint that enforces the ultrametric property over a symmetric array of constrained integer variables, with the inevitable property that the lower bounds of any three variables are mutually supportive. We show that this allows an efficient constraint-based solution to the supertree construction problem. We demonstrate that the versatility of constraint programming can be exploited to allow solutions to variants of the supertree construction problem.

MSC:
92D15 Problems related to evolution
05C05 Trees
90C90 Applications of mathematical programming
05C90 Applications of graph theory
PDF BibTeX XML Cite
Full Text: Link