This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).
The goal of this project is to develop innovative mathematics to compare, optimize and visualize phylogenetic, or evolutionary, trees. We will analyze, via a combination of theoretical advances and computational experimentation, the metric space of trees. Our efforts will focus on better understanding of and improving algorithms for calculating biologically relevant tree metrics. We will focus on the interaction between these metrics and the canonical, but NP-hard, optimization criteria favored by biologists. Computationally expensive searches are currently used to estimate the optimum and can survey only a tiny fraction of treespace. Deeper understanding of treespace will improve searches and sampling methods by suggesting better starting points, identifying clustering of local optima and suggesting locations of global optima.
Phylogenies, or evolutionary histories, play a central role in modern biology, illustrating the interrelationships between species, and also aiding the prediction of structural, physiological, and biochemical properties that can lead to the discovery of new drugs and vaccines. The reconstruction of the underlying evolutionary history from a set of morphological characters or biomolecular sequences is difficult since the optimality criteria favored by biologists are hard to compute, and the space of possible answers is huge. Due to this, clever searching techniques and heuristics are used to estimate the optimal tree. To improve these important, and computationally intensive, methods, we propose to step back and rigorously examine the underlying space of trees, along with different optimality criteria (often called the ?landscape? of trees), and provide a detailed understanding of the space of trees to improve phylogenetic tree reconstruction.
