The Ultrametric Constraint and its Application to Phylogenetics
  A phylogenetic tree shows the evolutionary relationships among species.
Internal nodes of the tree represent speciation events and leaf nodes
correspond to 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.
