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

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

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.