Paper ID: 8348
Supertree construction with constraint programming: recent progress and new challenges
WCB06 - Workshop on Constraint Based Methods for Bioinformatics
Page Numbers : 75-82
One goal of biology is to build the Tree of Life (ToL), a representation of the evolutionary history of every living thing. To date, biologists have catalogued about 1.7 million species, yet estimates of the total number of species ranges from 4 to 100 million. Of the 1.7 million species identified only about 80,000 species have been
placed in the ToL. There are applications for the ToL: to help understand how pathogens become more virulent over time, how new diseases emerge, and to recognise species at
risk of extinction. One approach to building the ToL is to combine smaller trees into ``supertrees''. Phylogenetic trees have been created for relatively small sets of species. These trees are then combined together into supertrees.
In 2003 Ian Gent, Barbara Smith, Christine Wu Wei, and myself reported the first constraint programming model for supertree construction. This was essentially a proof of concept, showing that constraint programming could address this problem in principle although our implementation was somewhat inefficient. This has recently been re-implemented using a faster constraint programming toolkit (JChoco, a java constraint programming tool) and has allowed us to look at larger problems and get a better idea of the limits of this encoding. Furthermore, with this new implementation we are able to demonstrate the flexibility of our model, something that should be expected when using a versatile technology such as constraint programming.
Keywords: The tree of life, supertree construction, constraint programming