This Small Grant for Exploratory Research (SGER), jointly funded by the Theory of Computing (TOC) Program, CCR, by Computational Biology Activity, BIR and by the Systemic Biology Program, DEB, addresses problems in the construction of phylogenies or evolutionary trees. The formulation and effective solution of this problem requires a collaborative multidisciplinary effort from biologists, statisticians and computer scientists. The ideal methodology for solving this problem would include the following steps:(a) Observe data on the species that exist today; (b) Identify a biological model (such as the Jukes-Cantor model or Kimura two parameter model); (c) Based on the model from Step (b), design an objective function and efficient optimization methods for this function so that the tree that optimizes this objective function is the tree that best fits the model. Unfortunately, this ideal program is impossible to realize, because of roadblocks at every step: (i) Data is subject to experimental error and to errors due to its interpretation and use in phylogeny construction methods;(ii) It seems difficult to identify a precise biological model for evolution; (iii) Given the stochastic model of evolution, one candidate for the optimizing tree is the ``most likely tree''. Given the uncertainty of what is actually the ``best'' model, a most likely tree under one model should still be a very likely tree under a slightly different model. Demonstrating this has proven to be a very difficult problem. The goals of this SGER proposal include:(1) Modification of the ideal methodology so that Difficulties(i) -- (iii) are removed; (2) Testing of various models using r-RNA and tufA sequence data supplied by a molecular biologist; (3) Using the experimental results, design of general methods for inferring phylogeny;(4) Comparison of these new models with existing models for the data. In addition, one of the goals of this SGER award is to initiate a multidisciplinary effort between the biologists, statisticians, and computer scientists at the University of Pennsylvania.***
