DIMACS Seminar on Math and CS in Biology


Some Convergence Analysis for the Phylogeny Reconstruction Methods


Kevin Atteson
University of Pennsylvania


Seminar Room 431, CoRE Building
Rutgers University.


11:00 a.m.
Thursday, March 27, 1997

The phylogeny reconstruction problem involves the determination of the evolutionary relationship of a set of species based upon biomolecular sequence data from the species. The recent proliferation of such data due in improvements in sequencing technology make this problem increasingly important. However, the methods which are thought to yield good solutions to the problem are computationally intractible and there is no concensus regarding which among tractible methods is best.

In this talk, I will present an analysis of the popular neighbor-joining method of phylogeny reconstruction. Here, phylogenies are represented by trees on the set of species. Given a stochastic model of evolution, a reasonable measuring stick for phylogenetic reconstruction methods is the probability of reconstructing a tree having the correct topology. We demonstrate that this method does the best possible among distance-based method at determining the topology in the sense of having the largest possible L-infinity radius.

Document last modified on March 21, 1997