Reconciliation with Non-Binary Species Trees
Reconciliation with Non-Binary Species Trees
复制标题
DOI：
10.1089/cmb.2008.0092
复制
发表时间：
2008-10-01
影响因子：
1.7
通讯作者：
Durand, Dannie
中科院分区：
文献类型：
--
作者：
Vernot, Benjamin;Stolzer, Maureen;Durand, Dannie
和解从基因树和物种树之间的拓扑不一致中提取信息，以推断基因家族历史中的重复和丢失。推断的重复损失的历史提供了有价值的信息，广泛的生物学应用，包括直系同源物鉴定，估计基因重复次数，生根和纠正基因树。虽然二叉树的和解是一个易于处理且研究得很好的问题，但没有与非二叉物种树和解的算法。然而，一个惊人的比例的树木物种是非二元的。例如，NCBI分类中64%的分支点有三个或更多的子节点。当应用于非二元物种树时，当前的算法高估了重复的数量，因为它们不能区分重复和不完整的谱系排序。我们提出了第一个算法，用于调和二进制基因树与非二进制物种树下的重复损失简约模型。我们的算法利用一个有效的映射从基因到物种树推断O（\V-G\）中的最小重复数。(k(S)+ h（S）））时间，其中\V-G\是基因树中的节点数，h（S）是物种树的高度，k（S）是其最大多分性的大小。我们提出了一个动态规划算法，也最大限度地减少了损失的总数。虽然这个算法是指数的最大的多分割的大小，它在实践中表现良好的多分割与outdegree为12或less. We还提出了一个启发式估计的最小数量的损失在多项式时间。在实证测试中，该算法在99%的时间内找到最佳损失历史。我们的算法已经在NOTONG中实现，NOTONG是一个强大的，生产质量，树拟合程序，它提供了一个图形用户界面，用于探索性分析，并支持自动化，高通量分析大型数据集。
Reconciliation extracts information from the topological incongruence between gene and species trees to infer duplications and losses in the history of a gene family. The inferred duplication-loss histories provide valuable information for a broad range of biological applications, including ortholog identification, estimating gene duplication times, and rooting and correcting gene trees. While reconciliation for binary trees is a tractable and well studied problem, there are no algorithms for reconciliation with non-binary species trees. Yet a striking proportion of species trees are non-binary. For example, 64% of branch points in the NCBI taxonomy have three or more children. When applied to non-binary species trees, current algorithms overestimate the number of duplications because they cannot distinguish between duplication and incomplete lineage sorting. We present the first algorithms for reconciling binary gene trees with non-binary species trees under a duplication-loss parsimony model. Our algorithms utilize an efficient mapping from gene to species trees to infer the minimum number of duplications in O(\V-G\ . (k(S) + h(S))) time, where \V-G\ is the number of nodes in the gene tree, h(S) is the height of the species tree and k(S) is the size of its largest polytomy. We present a dynamic programming algorithm which also minimizes the total number of losses. Although this algorithm is exponential in the size of the largest polytomy, it performs well in practice for polytomies with outdegree of 12 or less. We also present a heuristic which estimates the minimal number of losses in polynomial time. In empirical tests, this algorithm finds an optimal loss history 99% of the time. Our algorithms have been implemented in NOTUNG, a robust, production quality, tree-fitting program, which provides a graphical user interface for exploratory analysis and also supports automated, high-throughput analysis of large data sets.