Computational Biology

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 tree global constraint, 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 apply 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]. Current work addresses the incorporation of temporal side constraints into the global constraint, so that we can simultaneously deal with absolute or relative divergence dates. Future work will concern the optimisation version of the problem, which is necessary when the given trees are incompatible.

... details coming up ...

• Phylogeny Programs
• Phylogeny Wing at the Museum of Paleontology of UC Berkeley, California, USA
• Supertree, an experimental program for constructing supertrees, by Rod Page
• Supertree Algorithms, further programs (by Hordijk) for constructing supertrees, based on algorithms by Bryant, Daniel, Semple, and Steel
• TreeBASE, a database of phylogenetic knowledge
• Tree-of-Life Web Project
• Glossary of Genetic Terms at HHGRI