This project is in the area of computational biology; specifically, problems which deal with how to construct evolutionary trees, or phylogeny, (i.e., models of the evolutionary history of various species). There are three standard criteria on which tree construction algorithms are based: distance methods, maximum likelihood, and parsimony. The first two methods are used by the biologists and are dealt with in the statistical literature. The traditional algorithms literature for tree construction is focused on the parsimony methods; notably the Perfect Phylogeny Problem. Although this problem has significant combinatorial appeal, there is a gap between the results for this algorithmic theory and the theory for distance based tree construction methods. The project focuses on problems in the distance based phylogeny, including: (1) Methods for computing distances from strings; (2) Methods for comparing different trees for consensus; (3) Methods for fitting distance data to metric models. The second part of the project involves developing empirical methods for testing the statistical robustness of heuristic methods currently in use. The Educational Component of this CAREER Grant includes: (a) Development and implementation of a post doctoral training program in computational molecular biology at DIMACS; (b) Modification of the graduate seminar in biocomputing; (c) Development and modification of the Rutgers University undergraduate program in biomathematics which focuses on combinatorics and molecular biology.
