Computational Biology

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].

Resources

• Phylogeny Programs
• Phylogeny Wing at the Museum of Paleontology of UC Berkeley, California, USA
• TreeBASE, a database of phylogenetic knowledge
• Tree-of-Life Web Project
• Glossary of Genetic Terms at HHGRI