An algorithm for computing the gene tree probability under the multispecies coalescent and its application in the inference of population tree.
An algorithm for computing the gene tree probability under the multispecies coalescent and its application in the inference of population tree.
复制标题
一种用于计算多物种合并下基因树概率的算法及其在人口树的推断中的应用。
DOI：
10.1093/bioinformatics/btw261
复制
发表时间：
2016-06-15
期刊：
影响因子：
--
通讯作者：
Wu Y
中科院分区：
文献类型：
--
作者：
Wu Y
动机：基因树代表了起源于多个相关群体的基因谱系的进化历史。在多物种合并模型下，谱系可能在物种（种群）边界之外合并。给定一个物种树（具有分支长度），基因树概率是在多物种合并模型下观察到特定基因树拓扑的概率。现有两种算法可用于计算精确的基因树概率。第一个算法是由Degnan和Salter提出的，他们列举了给定物种树和基因树拓扑的所有所谓的合并历史。他们的算法一般在基因谱系数量的指数时间内运行。第二个算法是STELLS算法（2012），它通常更快，但在几乎所有情况下都是指数时间运行。结果：在这篇文章中，我们提出了一种新的算法，称为CompactCH，用于计算精确的基因树概率。这种新算法是基于紧凑的合并历史的概念：多个合并历史由一个紧凑的合并历史表示。我们的新算法的主要优点是，它运行在多项式时间的基因谱系的数量，如果人口数量是固定的是一个常数。当种群数量较少且每个种群有多个基因谱系时，新算法在理论和实践上都比STELLS算法更有效。作为一个应用，我们表明，CompactCH可以应用于人口树的推断（即人口的分歧历史）从人口单倍型。模拟结果表明，CompactCH算法能够有效和准确的推断人口树与更多的单倍型比以前的方法。可用性：CompactCH算法在STELLS软件包中实现，该软件包可从http://www.engr.uconn.edu/ywu/STELLS.html下载。联系方式：ywu@engr.uconn.edu补充信息：补充数据可在生物信息学在线获得。
Motivation: Gene tree represents the evolutionary history of gene lineages that originate from multiple related populations. Under the multispecies coalescent model, lineages may coalesce outside the species (population) boundary. Given a species tree (with branch lengths), the gene tree probability is the probability of observing a specific gene tree topology under the multispecies coalescent model. There are two existing algorithms for computing the exact gene tree probability. The first algorithm is due to Degnan and Salter, where they enumerate all the so-called coalescent histories for the given species tree and the gene tree topology. Their algorithm runs in exponential time in the number of gene lineages in general. The second algorithm is the STELLS algorithm (2012), which is usually faster but also runs in exponential time in almost all the cases. Results: In this article, we present a new algorithm, called CompactCH, for computing the exact gene tree probability. This new algorithm is based on the notion of compact coalescent histories: multiple coalescent histories are represented by a single compact coalescent history. The key advantage of our new algorithm is that it runs in polynomial time in the number of gene lineages if the number of populations is fixed to be a constant. The new algorithm is more efficient than the STELLS algorithm both in theory and in practice when the number of populations is small and there are multiple gene lineages from each population. As an application, we show that CompactCH can be applied in the inference of population tree (i.e. the population divergence history) from population haplotypes. Simulation results show that the CompactCH algorithm enables efficient and accurate inference of population trees with much more haplotypes than a previous approach. Availability: The CompactCH algorithm is implemented in the STELLS software package, which is available for download at http://www.engr.uconn.edu/ywu/STELLS.html. Contact: ywu@engr.uconn.edu Supplementary information: Supplementary data are available at Bioinformatics online.