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.

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