UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 8348

Supertree construction with constraint programming: recent progress and new challenges
Prosser,P.

Publication Type: Conference Proceedings
Appeared in: WCB06 - Workshop on Constraint Based Methods for Bioinformatics
Page Numbers : 75-82
Publisher: N/A
Year: 2006
ISBN/ISSN:
Abstract:

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


PDF Bibtex entry Endnote XML