A branch-and-bound algorithm for the inference of ancestral amino-acid sequences when the replacement rate varies among sites: Application to the evolution of five gene families
A branch-and-bound algorithm for the inference of ancestral amino-acid sequences when the replacement rate varies among sites: Application to the evolution of five gene families
复制标题
DOI：
10.1093/bioinformatics/18.8.1116
复制
发表时间：
2002-08-01
期刊：
影响因子：
5.8
通讯作者：
Friedman, N
中科院分区：
文献类型：
--
作者：
Pupko, T;Pe'er, I;Friedman, N
动机：我们开发了一种重建祖先序列的算法，考虑到蛋白质序列位点之间的速率变化。我们的算法最大化祖先序列的联合概率，假设该概率是伽玛分布在站点之间的。我们的算法可以证明找到了全局最大值。使用“联合”重建的动机是使用系统发育树中所有内部节点的序列进行的研究，例如氨基酸替换模式的推断，或追踪给定蛋白质家族进化过程中发生的生化变化。结果：我们给出了一种保证找到全局最大值的算法。高效的搜索方法使我们的方法适用于具有大量数字序列的数据集。我们分析了五个基因家族的祖先序列，探索位点间速率变异量的影响以及序列分歧程度对最终祖先状态的影响。
Motivation: We developed an algorithm to reconstruct ancestral sequences, taking into account the rate variation among sites of the protein sequences. Our algorithm maximizes the joint probability of the ancestral sequences, assuming that the rate is gamma distributed among sites. Our algorithm provably finds the global maximum. The use of 'joint' reconstruction is motivated by studies that use the sequences at all the internal nodes in a phylogenetic tree, such as, for instance, the inference of patterns of amino-acid replacement, or tracing the biochemical changes that occurred during the evolution of a given protein family.Results: We give an algorithm that guarantees finding the global maximum. The efficient search method makes our method applicable to datasets with large number sequences. We analyze ancestral sequences of five gene families, exploring the effect of the amount of among-site-rate-variation, and the degree of sequence divergence on the resulting ancestral states.