Evolutionary Trees – Københavns Universitet

Videresend til en ven Resize Print Bookmark and Share

Datalogisk Institut, DIKU > Forskning > Algorithms and Programming Languages (APL) > Computational Biology > Evolutionary Trees

Evolutionary Trees

Evolutionary trees, also called phylogenetic trees show the evolutionary interrelationships between various species. In recent years, due to the explosion of available data, species are typically represented by appropriate DNA- or protein sequences.

There is surprising number of diiferent methods that have been used to determine evolutionary trees. They can be subdivided into four main groups. Parsimony methods are based on the Occam's razor principle: Whem given the choice between two explanations, choose the simpler one. In evolutionary trees, this usually amounts to looking for a tree with fewest number of evolutionary changes between interrelated species. Maximum likelihood methods are based on probabilistic models of evolution. Given such a model, the likelihood that a tree with given topology is the sought evolutionary tree, can be calculated. The tree with the maximum likelihood is of course selected as the evolutionary tree. Consensus methods attempt to find evolutionary trees for all species using trees for (usually small) subsets of species (which are much easier to determine for biologists)). Finally, distance methods are based on appropriately defined distances between species (for example appropriate edit distances between pairs of DNA- or protein sequences). Once distances are given, the problem reduces to that of determining a minimum cost tree satisfying some side constraints.

Research on evolutionary trees at DIKU focused so far on distance methods. In particular, our group suggested a novel distance-based approach. Species are represented by points in an appropriately chosen high-dimensional space such that the distances beetween points correspond to distances between DNA- or protein sequences. Multidimensional scaling is used to determine the locations of points. Once located, the problems reduces to that of finding minimal Steiner tree for the points (possibly with appropriate side constraints). Initial work suggests that the approach has some potential. Exploiting our in-depth knowledge of the Steiner tree problem here at DIKU may prove essential for making this approach a useful alternative to such distance methods as neighbor joining. This ongoing research has been carried out in cooperation with Dorin Thomas and Marcus Brazil from the Dept. of Engineering, Univ. of Melbourne.

M. Brazil, D.A. Thomas, B.K. Nielsen, P. Winter, C. Wulff-Nilsen and M. Zachariasen
A novel approach to phylogenetic tress: d-dimensional geometric Steiner trees
Networks 53 (2009) 104-111 [doi] [pdf]