AF: Small: Algorithms for Reconstructing Complex Evolutionary History with Discordant Phylogenetic Trees

用不一致的系统发育树重建复杂进化历史的算法PI：吴玉峰，康涅狄格大学生物数据分析中许多重要的计算公式本身就很难处理。许多现有的计算方法要么太慢，要么不能把握生物学的复杂性，这是对潜在生物学进行更可靠的建模所需的。与此同时，生物数据的规模正在迅速增长。因此，目前需要开发更高效、更准确的算法来分析大量数据和求解更复杂的计算公式。研究物种和种群的复杂进化史是这个项目的主旋律。进化史通常由系统发育树来模拟，即所谓的生命树，这已经得到了广泛的研究。最近，一个更复杂的模型--系统发育网络被提出和研究，以适应包括水平基因转移、重组和杂交物种形成在内的各种进化过程。作为系统发育树模型的推广，系统发育网络是具有两个或多个亲本的节点的有向图(除了树模型中只有一个亲本的节点)。对于一种称为不完全世系排序的复杂进化过程，还有其他研究较少的计算公式。粗略地说，不完全的世系排序导致基因组不同部分的进化史不一致。这可能会使系统发育研究变得非常复杂。该项目致力于开发新的算法来解决在重建复杂进化历史时出现的困难优化问题，例如那些由系统发生网络建模的进化历史。这些算法考虑了多个不协调的系统发育树，它们模拟了不同基因组区域的进化历史。这个项目将开发算法来比较两个或更多相关的系统发生树，并推断出解释给定树的看似合理的系统发生网络。虽然这个公式通常很难处理，但这个项目将开发出实用的算法，可以给出一定范围内的数据的最佳解决方案。在这个项目中要采取的一种方法是有效地找到最优解的可计算的闭合下界和上界。当最优解很难直接计算时，这可能有助于量化解决方案的范围。本项目还将探讨在不完全世系分类研究中出现的相关计算问题。预期的项目成果将包括解决上述计算问题的有效算法、生物学家容易使用的相关开放源码软件工具，以及对算法进行理论和经验评估的严格方法。开发的软件工具将免费提供给多学科研究社区，并有望在研究复杂进化方面实现新的生物学应用。研究成果将融入课堂教学。拟议的教育和外联活动包括接触具有不同背景的学生，以及培训具有跨学科技能的未来研究人员。

Algorithms for Reconstructing Complex Evolutionary History with Discordant Phylogenetic TreesPI: Yufeng Wu, University of ConnecticutMany important computational formulations in biological data analysis are inherently intractable. Many existing computational approaches are either too slow or not able to grasp biological complexity needed for more faithful modeling of the underlying biology. In the meantime, the size of biological data is growing rapidly. Therefore, currently there is a need to develop more efficient and accurate algorithms for analyzing large amount of data and solving more complex computational formulations. The study of the complex evolutionary history of species and populations is the main theme of this project. Evolutionary history is often modeled by phylogenetic tree, the so-called ?tree of life?, which has been studied extensively. Recently, a more complex model, phylogenetic network, has been proposed and studied to accommodate various evolutionary processes, including horizontal gene transfer, recombination and hybrid speciation. As a generalization of the phylogenetic tree model, phylogenetic network is a directed graph with nodes with two or more parents (in addition to nodes with a single parent as in the tree model). There are also other less studied computational formulations for a complex evolutionary process called incomplete lineage sorting. Roughly speaking, incomplete lineage sorting causes discordance of evolutionary histories in different parts of genomes. This can greatly complicate phylogenetic study.This project is focused on developing new algorithms for hard optimization problems arising in reconstructing complex evolutionary histories, such as those modeled by phylogenetic networks. These algorithms consider multiple discordant phylogenetic trees, which model the evolutionary histories of different genomic regions. This project will develop algorithms to compare two or more correlated phylogenetic trees and infer the plausible phylogenetic networks that explain the given trees. Although this formulation is generally intractable, this project will develop practical algorithms that can give optimal solutions for data within certain range. One approach to be taken in this project is finding efficiently computable close lower and upper bounds of optimal solutions. This may help to quantify the range of solutions when the optimal solutions are difficult to compute directly. This project will also explore related computational problems arising in the study of incomplete lineage sorting. The expected project outcome will include efficient algorithms for the above computational problems, related open-source software tools that are readily usable by biologists, and rigorous methodologies for both theoretical and empirical evaluation of the algorithms. Developed software tools will be made available freely to the multi-disciplinary research community, and are expected to enable novel biological applications in studying complex evolution. Research results will be integrated into classroom teaching. The proposed educational and outreach activities include reaching out to students with various backgrounds, and training of future researchers with interdisciplinary skills.