I will present a novel distance-based algorithm for evolutionary tree reconstruction. In the general Markov model of evolution, the algorithm recovers the topology of a tree with N leaves successfully with l-o(l) probability from sequences with polynomial length in N. The algorithm runs in O(N^2) time using O(N) working space, which makes it the fastest known topology reconstruction algorithm with polynomial sample length requirements. The theoretical results are supported by simulation experiments involving trees with 500, 1895, and 3135 leaves. The trees are recovered in the experiments with high success from 2000-character sequences.

Monday, March 19, 2001 @ 4:00 in Keck 102

A reception will be held BEFORE the talk outside of Keck 102

About Miklos Csuros

Miklos Csuros received his degree in Electrical Engineering from Budapest University of Technology in 1994, and his Ph. D. in Computer Science from Yale University in December 2000. While finishing his graduate studies he worked for Curagen Corp., a biotechnology company, on algorithmic problems associated with get-based sequencing and gene expression analysis. He is currently a computer scientist with Genometrix, Inc., a Texas-based biotechnology company, working on gene expression and genotyping analysis of high-throughput microarray data. His research interests include computational leaming theory and computational biology.

Miklos Csuros is a faculty candidate.