Efficient Algorithms for Constructing and Comparing Evolutionary Trees
Professor Ming-Yang Kao, Department of Computer Science, Yale University, U.S.A.

Abstract: An evolutionary tree is a rooted tree where each internal node has two children and the leaves are labeled with distinct symbols representing species. Evolutionary trees are useful for modeling the evolutionary history of species. This talk will discuss an ongoing project to develop a multilevel integrated platform for constructing evolutionary trees from biological sequence data and extracting information from these trees. The discussion will focus on recent algorithmic results on two prototypical problems. We will first discuss how to construct evolutionary trees from relatively short DNA sequences with provable accuracy guarantees. Different theories or data sets about the evolutionary history of the same species may result in different evolutionary trees. A basic problem in biology is to determine how consistent certain theories or data sets are. To a useful extent, this problem can be answered by computing a maximum topological subtree of the corresponding evolutionary trees. This talk will also discuss some of the fastest known algorithms for computing such subtrees.

(This talk is partly based on joint works with Csuros, Lam, Sung, Ting, Lingas, and Ostlin)

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 2 October 1998.

back