Phylogenetic Supertree Construction
Cooperation with Nicolas Beldiceanu and Xavier Lorca at the École des Mines de Nantes, France.
One objective of phylogeny is to construct the genealogy of the species, called the tree of life, whose leaves represent the contemporary species and whose internal nodes represent extinct species that are not necessarily named. An important problem in phylogeny is the construction of a supertree that is compatible with several given trees.
Towards this (and other applications, especially in routing), we designed the global constraint TREE, which partitions a directed graph into node-disjoint trees, subject to side constraints on tree count, node degrees, precedences, and incomparabilities within node subsets. We applied this constraint to model the phylogenetic supertree construction problem, asking for one tree, whose speciation nodes all have degree two (or at least two), possibly under side constraints on nested species, modelled via the precedence parameter [BFL08].