Mathematical Challenges in Phylogenetic Landscapes

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。这个项目的目标是开发创新的数学来比较，优化和可视化系统发育，或进化，树。 我们将通过理论进展和计算实验的结合来分析树的度量空间。 我们的努力将集中在更好地理解和改进算法计算生物相关的树。 我们将集中在这些指标和规范之间的相互作用，但NP难，优化标准的生物学家青睐。 计算昂贵的搜索目前被用来估计最佳，只能调查一小部分的树空间。 对树空间的深入理解将通过提出更好的起点、识别局部最优的聚类和确定全局最优的位置来改进搜索和采样方法。系统发育或进化史在现代生物学中起着核心作用，它阐明了物种之间的相互关系，也有助于预测结构、生理和生化特性，从而发现新药和疫苗。从一组形态特征或生物分子序列重建潜在的进化历史是困难的，因为生物学家喜欢的最优性标准很难计算，可能的答案空间很大。由于这一点，聪明的搜索技术和算法被用来估计最优树。为了提高这些重要的，计算密集型，方法，我们建议退一步，严格检查树的底层空间，沿着与不同的最优性标准（通常称为？风景？的树），并提供了一个详细的了解空间的树，以改善系统发育树重建。

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.