期刊名称：Journal of Automation, Mobile Robotics & Intelligent Systems (JAMRIS)
印刷版ISSN：1897-8649
电子版ISSN：2080-2145
出版年度：2008
卷号：32
页码：901-938
出版社：Industrial Research Inst. for Automation and Measurements, Warsaw
摘要：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.
