Mathematical Challenges in Phylogenetic Landscapes

点击翻译按钮获取中文摘要

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 tocompare, optimize and visualize phylogenetic, or evolutionary,trees. We will analyze, via a combination of theoreticaladvances and computational experimentation, the metric space oftrees. Our efforts will focus on better understanding of andimproving algorithms for calculating biologically relevant treemetrics. We will focus on the interaction between these metricsand the canonical, but NP-hard, optimization criteria favored bybiologists. Computationally expensive searches are currentlyused to estimate the optimum and can survey only a tiny fractionof treespace. Deeper understanding of treespace will improvesearches and sampling methods by suggesting better startingpoints, identifying clustering of local optima and suggestinglocations of global optima.Phylogenies, or evolutionary histories, play a central role inmodern biology, illustrating the interrelationships betweenspecies, and also aiding the prediction of structural,physiological, and biochemical properties that can lead to thediscovery of new drugs and vaccines. The reconstruction of theunderlying evolutionary history from a set of morphologicalcharacters or biomolecular sequences is difficult since theoptimality criteria favored by biologists are hard to compute,and the space of possible answers is huge. Due to this, cleversearching techniques and heuristics are used to estimate theoptimal tree. To improve these important, and computationallyintensive, methods, we propose to step back and rigorouslyexamine the underlying space of trees, along with differentoptimality criteria (often called the ?landscape? of trees), andprovide a detailed understanding of the space of trees to improvephylogenetic tree reconstruction.