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

AF：小：用不一致的系统发育树重建复杂进化历史的算法

• 批准号: 1116175
• 负责人: Yufeng Wu
• 金额: $ 25.68万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1116175&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Reconstructing; Complex

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.

用不协调系统发生树重建复杂进化历史的算法PI：Yufeng Wu，University of Connecticut生物数据分析中的许多重要计算公式本质上是难以处理的。许多现有的计算方法要么太慢，要么无法掌握生物学的复杂性，需要更忠实的建模的基础生物学。与此同时，生物数据的规模正在迅速增长。因此，目前需要开发更有效和准确的算法来分析大量数据和解决更复杂的计算公式。研究物种和种群的复杂进化历史是该项目的主题。进化历史通常是由系统发育树模型，所谓的？生命之树？已经被广泛研究过了。最近，一个更复杂的模型，系统发育网络，已被提出和研究，以适应各种进化过程，包括水平基因转移，重组和杂交物种形成。作为系统发生树模型的推广，系统发生网络是一个有向图，其中节点具有两个或多个父节点（除了树模型中的单个父节点）。还有其他研究较少的计算公式，用于复杂的进化过程，称为不完全谱系排序。粗略地说，不完整的谱系分类导致基因组不同部分的进化历史不一致。本项目的研究重点是开发新的算法，以解决系统发生网络等复杂进化历史的重建过程中出现的困难优化问题。这些算法考虑了多个不一致的系统发育树，它模拟了不同基因组区域的进化历史。本计画将发展演算法来比较两个或多个相关的系统发生树，并推论出解释这些树的合理系统发生网路。虽然这个公式通常是棘手的，这个项目将开发实用的算法，可以在一定范围内的数据提供最佳的解决方案。在这个项目中采取的一种方法是找到有效的可计算的最优解的上下限。当最优解难以直接计算时，这可能有助于量化解的范围。本计画亦将探讨在不完全谱系排序研究中所产生的相关计算问题。预期的项目成果将包括解决上述计算问题的有效算法、生物学家易于使用的相关开放源码软件工具，以及对算法进行理论和经验评估的严格方法。开发的软件工具将免费提供给多学科研究界，并有望在研究复杂的进化过程中实现新的生物学应用。研究成果将融入课堂教学。拟议的教育和外联活动包括接触不同背景的学生，并培训未来的研究人员掌握跨学科技能。