ABI Innovation: Algorithms and Models for Distributed Computation of Bayesian Phylogenetics

给定从许多生物体获得的一组分子（DNA， RNA或氨基酸）序列，系统发育推断的任务是重建序列之间的进化关系。当对遗传物质的水平或垂直传播进行建模时，这些关系被表示为进化树，或者更一般地表示为有向无环图（DAG）。该项目研究了流行的贝叶斯方法来进行系统发育推断。目前，所有流行的贝叶斯推理软件包都使用了马尔可夫链蒙特卡罗（MCMC）算法。问题是，这些算法可能需要几个月的时间才能收敛于大型推理问题。该项目的目标是为MCMC开发适合在现代集群计算环境中使用的并行算法，例如亚马逊的EC2服务。为了确保这项工作产生更广泛的影响，该软件以及用户手册和教程将是开源的，而pi将特别努力从代表性不足的群体中招募学生。为了将系统发育推断算法扩展到数千个生物体，并行化是必需的。例如，该项目将探索的一个想法是所谓的贝叶斯森林（BF）方法。在BF方法中，MCMC算法不是维护一个树或DAG，而是同时维护数十、数百或数千个树或DAG，其中所有树或DAG都在一起工作，并在算法运行时相互共享信息。这就避免了与趋同于糟糕的局部最优解决方案相关的问题，因为只要一棵树/DAG避免了问题配置，随着时间的推移，这棵树/DAG就可以将整个森林从糟糕的解决方案中拉出来。至关重要的是，由于单个树/ dag上最昂贵的计算是相互独立的，因此很容易将它们发送到不同的机器上。该项目还将考虑分布式算法来解决具有挑战性的问题变体，例如多位点数据集和遗传物质的垂直和水平传输，以及基因和物种树的共同估计。所有的软件，连同用户手册和教程，都将是开源的。该项目的网页将在http://cmj4.web.rice.edu/phylogenetics上提供。

Given a set of molecular (DNA, RNA, or amino acid) sequences obtained from a number of organisms, phylogenetic inference is the task of reconstructing the evolutionary relationships among the sequences. These relationships are represented as an evolutionary tree, or, more generally, a directed, acyclic graph (DAG) when horizontal or vertical transmission of genetic material is modeled. The proposed project investigates the popular Bayesian approach to phylogenetic inference. Currently, all popular software packages for Bayesian inference utilize Markov Chain Monte Carlo (MCMC) algorithms. The problem is that these algorithms can take months to converge on large inference problems.The project's aim is to develop parallel algorithms for MCMC that are suitable for use in a modern cluster compute environment, such as Amazon.com's EC2 service. To ensure broader impacts of this work, the software, along with a user's manual and tutorial, will be open-sourced and the PIs will make special effort in recruiting students from underrepresented groupsFor a phylogenetic inference algorithm to scale to thousands of organisms, parallelization is mandatory. For example, one idea that the project will expore is the so-called Bayesian Forest (BF) approach. In the BF approach, the MCMC algorithm maintains not one tree or DAG, but dozens, hundreds, or thousands of trees or DAGs at the same time, where all of them work together and share information with one another as the algorithm runs. This tends to avoid problems associated with converging to poor, locally optimal solutions because as long as one tree/DAG has avoided a problem configuration, over time, that tree/DAG can pull the entire forest away from the poor solution. Crucially, since the most expensive computations over the individual trees/DAGs are independent of one another, it is easy to send them to different machines. The project will also consider distributed algorithms for challenging variants of the problem, such as multi-loci data sets and vertical and horizontal transmission of genetic material, as well as co-estimation of gene and species trees. All software, along with a user's manual and tutorial, will be open-sourced. The project web page will be available at http://cmj4.web.rice.edu/phylogenetics.