AitF: Full: Collaborative Research: Graph-theoretic algorithms to improve phylogenomic analyses

AitF：完整：协作研究：改进系统发育分析的图论算法

• 批准号: 1535977
• 负责人: Tandy Warnow
• 金额: $ 36万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1535977&HistoricalAwards=false
• 关键词: AitF; Full; Collaborative; Research; Graph

Understanding the history of life on earth ? how species evolved from their common ancestor ? is a major goal of biological research. These evolutionary trees are very hard to construct with high accuracy, because nearly all of the most accurate approaches require the solution to computationally hard optimization problems. Furthermore, research has shown that the evolutionary tree for a single gene can be different from the evolutionary tree for the species, and current methods do not provide adequate accuracy on genome-scale data. As a result, large evolutionary trees, covering big portions of ?The Tree of Life?, are very difficult to compute with high accuracy. This project will develop methods that can enable highly accurate species tree estimation. The key approach is the development of novel divide-and-conquer strategies, whereby a dataset is divided into overlapping subsets, species trees are constructed on the subsets, and then the subset species trees are merged together into a tree on the full dataset. These approaches will be combined with powerful statistical estimation methods, to potentially transform the capability of evolutionary biologists to analyze their data. This project will also provide open source software for the new methods that are developed, and provide training in the use of the software to biologists at national meetings. The project will also contribute to interdisciplinary training for two doctoral students, one at Illinois and one at Berkeley, and course materials for computational biology will be made available online. Understanding evolution, and how it has operated on species and on genes, is a major part of biological data analysis. Statistical estimation approaches often provide the best accuracy, but cannot scale to dataset sizes that are required for modern biology. In addition, species tree estimation is challenged by the heterogeneity of evolutionary trees across the genome, and no current methods are able to provide highly accurate species trees for genome-scale data. These challenges make it essential that new methods be developed in order to make highly accurate large-scale evolutionary tree estimation possible under these complex evolutionary scenarios. This project will develop novel algorithmic strategies to address three key problems: supertree estimation, species tree estimation in the presence of gene tree heterogeneity, and scaling statistical methods to large datasets. In addition to developing graph-theoretic algorithms, the project team will establish mathematical guarantees for these methods using chordal graph theory and probabilistic analysis, under stochastic models of gene and sequence evolution.

了解地球上的生命历史吗？物种是如何从共同祖先进化的？是生物学研究的主要目标。这些进化树非常难以构建高精度，因为几乎所有最准确的方法都需要解决计算上硬优化问题的解决方案。此外，研究表明，单个基因的进化树与物种的进化树不同，并且当前方法对基因组规模数据没有足够的准确性。结果，覆盖着“生命之树”的大部分的大型进化树是很难以很高的精度计算。该项目将开发可以实现高度准确的物种树估计的方法。关键方法是开发新颖的分裂策略，从而将数据集分为重叠的子集，物种树在子集上构造，然后将子集的树木融合在一起，并将其合并为完整数据集的树。这些方法将与强大的统计估计方法结合使用，以改变进化生物学家分析其数据的能力。该项目还将为开发的新方法提供开源软件，并在国家会议上为生物学家提供对软件使用的培训。该项目还将为两名博士生，一名在伊利诺伊州和伯克利的一名博士学位培训做出贡献，计算生物学课程材料将在线提供。了解进化及其在物种上和基因上的运作方式是生物数据分析的主要部分。统计估计方法通常提供最佳准确性，但不能扩展到现代生物学所需的数据集大小。此外，物种树估计受到整个基因组进化树的异质性的挑战，并且没有当前的方法能够为基因组规模数据提供高度准确的物种树。这些挑战使得开发新方法至关重要，以便在这些复杂的进化场景下进行高度准确的大规模进化树估计。 该项目将开发新的算法策略来解决三个关键问题：超级树的估计，存在基因树异质性的物种估计以及将统计方法扩展到大型数据集。除了开发图理论算法外，项目团队还将在基因和序列进化的随机模型下，使用和弦图理论和概率分析为这些方法建立数学保证。