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

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

• 批准号: 1018785
• 负责人: Tiffani Williams
• 金额: $ 39.7万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1018785&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）执行实时收敛分析，以及（iv）开发新的可视化工具，提供收敛数据的信息视图。研究型大学和本科自由学院的合作有很多好处 艺术学院。生物学和计算机科学专业的本科生和研究生都有机会设计和实现算法，并在大型数据集上运行计算实验，否则他们将无法获得这些数据。 可以考虑的大型树木可用于改善全球农业和保护生态系统免受入侵物种的侵害。 这项工作的结果将在科学会议、研讨会和期刊上展示和传播。开发的工具和软件将公开提供。