<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>8979</REFNUM><AUTHORS><AUTHOR>Moore,N.C.A.</AUTHOR><AUTHOR>Prosser,P.</AUTHOR></AUTHORS><YEAR>2008</YEAR><TITLE>The Ultrametric Constraint and its Application to Phylogenetics</TITLE><PLACE_PUBLISHED>Journal of Artificial Intelligence Research, Volume 32</PLACE_PUBLISHED><PUBLISHER>AAAI Press</PUBLISHER><PAGES>901-938</PAGES><ISBN>ISSN 11076-9757</ISBN><LABEL>Moore:2008:8979</LABEL><KEYWORDS><KEYWORD>supertrees construction constraint programming tree of life ultrametric</KEYWORD></KEYWORDS<ABSTRACT>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.</ABSTRACT></RECORD></RECORDS></XML>