III: Small: Collaborative: Novel Techniques for Understanding Convergence in Large-Scale Markov Chain Monte Carlo Phylogenetic Analyses

III：小：协作：理解大规模马尔可夫链蒙特卡罗系统发育分析中收敛性的新技术

• 批准号: 1018311
• 负责人: Marc Smith
• 金额: $ 10.3万
• 依托单位: Vassar College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1018311&HistoricalAwards=false
• 关键词: III; Small; Collaborative; Novel; Techniques

Inferring the true evolutionary history for a group of organisms, taxa, is a difficult problem. For a given set of taxa, there is an exponential number of ways to depict their family tree. Hence, an exhaustive exploration of all possible trees is infeasible. As a result, the most popular techniques sample tree space in order to obtain an estimate of the true evolutionary tree. The challenge is to know when a an estimate of an evolutionary tree for a group of taxa has converged, which is important because non-convergence leads to inaccurate estimation of the true evolutionary tree.The team will develop a suite of convergence detection algorithms for large-scale Markov Chain Monte Carlo phylogenetic analyses, one of the most popular techniques for reconstructing large-scale evolutionary trees that can handle hundreds of thousands of trees on hundreds to thousands of taxa. Convergence detection changes the framework for how these evolutionary trees are reconstructed. For example, analyses that have not yet converged, rather than be terminated based on some arbitrary specification (e.g., elapsed time), could be allowed to continue as long as progress toward convergence is detected. If progress is still not made, the phylogenetic analysis would be terminated saving significant time and computational resources. The approach arms life scientists with information for why their analysis did not converge. The team will develop convergence detection techniques that are based on the topological structure (i.e., the evolutionary relationships contained in a tree) of the underlying phylogenetic tree instead of relying solely on its score. To address the above issues, the novel integrated framework consists of: (i) designing and analyzing new algorithms for convergence detection, (ii) identifying the causes for non-convergence in a phylogenetic analysis, (iii) performing real-time convergence analysis, and (iv) developing new visualization tools that provide informative views of convergence data.There are many benefits that exist between the collaboration of a research university and an undergraduate liberal arts college. Both undergraduate and graduate students in both biology and computer science have an opportunity to design and implement algorithms and run computational experiments on large data sets that would otherwise be unavailable to them. The large trees that can be considered have applications in improving global agriculture and protecting ecosystems from invasive species. The results of this work will be presented and disseminated at scientific conferences, workshops, and journals. Tools and software developed will be made publicly available.

推断一组生物（分类群）的真实进化历史是一个难题。对于一组给定的分类群，有指数数量的方法来描述它们的家谱。因此，对所有可能的树进行详尽的探索是不可行的。因此，最流行的技术采样树空间，以获得真正的进化树的估计。挑战是要知道一组分类群的进化树的估计何时收敛，这很重要，因为不收敛会导致对真实进化树的不准确估计。该团队将开发一套收敛检测算法，用于大规模马尔可夫链蒙特卡罗系统发育分析，这是重建大规模进化树的最流行技术之一，可以处理数百到数千个分类群上的数十万棵树。收敛检测改变了这些进化树如何重建的框架。例如，尚未收敛的分析，而不是基于一些任意规范（例如，经过的时间），只要检测到朝向收敛的进展，就可以允许继续。如果仍然没有取得进展，系统发育分析将被终止，从而节省大量的时间和计算资源。这种方法为生命科学家提供了为什么他们的分析没有收敛的信息。该团队将开发基于拓扑结构的收敛检测技术（即，包含在树中的进化关系）而不是仅仅依赖于其得分。为解决上述问题，新的综合框架包括：（i）设计和分析用于收敛检测的新算法，（ii）在系统发育分析中识别不收敛的原因，（iii）执行实时收敛分析，和（四）开发新的可视化工具，提供融合数据的信息视图。与研究型大学合作有很多好处，和一所文科大学。生物学和计算机科学的本科生和研究生都有机会设计和实现算法，并在大型数据集上运行计算实验，否则他们将无法使用。 可以考虑的大型树木在改善全球农业和保护生态系统免受入侵物种的影响方面具有应用价值。 这项工作的结果将在科学会议、讲习班和期刊上介绍和传播。开发的工具和软件将向公众提供。