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

给定一组从许多生物体中获得的分子（DNA、RNA或氨基酸）序列，系统发育推断是重建序列之间进化关系的任务。这些关系被表示为进化树，或者更一般地，当遗传物质的水平或垂直传递被建模时，表示为有向无环图（DAG）。拟议的项目调查流行的贝叶斯方法的系统发育推断。目前，所有流行的软件包贝叶斯推理利用马尔可夫链蒙特卡罗（MCMC）算法。该项目的目标是为MCMC开发适用于现代集群计算环境（如Amazon.com的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.