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

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

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.