Tree-based maximal likelihood substitution matrices and hidden Markov models
Tree-based maximal likelihood substitution matrices and hidden Markov models
复制标题
DOI：
10.1007/bf00173195
复制
发表时间：
1995-12-01
影响因子：
3.9
通讯作者：
Durbin, R
中科院分区：
文献类型：
--
作者：
Mitchison, G;Durbin, R
有相当大的兴趣，在问题的最大似然（ML）进化树，允许插入和删除。这个问题部分是一个公式化：如何定义一个概率模型，这样的树，治疗插入和删除在生物学上合理的方式？这个问题的一个可能的答案是在这里提出的隐马尔可夫模型（HMM）的概念扩展到进化树。该模型，称为树HMM，允许什么可能被松散地视为可学习的仿射型缺口罚分的比对。这些惩罚用Hyns表示为状态之间转换的概率。在树隐马尔可夫模型中，通过定义变迁树，这一思想得到了进化的体现。正如通过Felsenstein的方法计算由无空位序列组成的树的概率一样，使用表示沿着树边缘的残基替换概率的矩阵，因此树-隐马尔可夫模型中的概率是通过残基和转换的替换矩阵来计算的。这里展示了如何使用从蛋白质序列数据库学习的算法通过ML过程来定义这些矩阵。给定这些矩阵，可以为一组序列定义树HMM似然，假设特定的树拓扑和序列与模型的比对。如果可以有效地找到使这种可能性最大化（或接近最大化）的比对，则可以搜索序列的最优树拓扑。这里定义了一个对齐算法，给定一个特定的树拓扑结构，保证增加模型的可能性。不幸的是，它无法找到现实序列集的全局最优解。因此，需要进一步的研究，把树HMM成为一个实用的系统发育工具。
There has been considerable interest in the problem of making maximum likelihood (ML) evolutionary trees which allow insertions and deletions. This problem is partly one of formulation: how does one define a probabilistic model for such trees which treats insertion and deletion in a biologically plausible manner? A possible answer to this question is proposed here by extending the concept of a hidden Markov model (HMM) to evolutionary trees. The model, called a tree-HMM, allows what may be loosely regarded as learnable affine-type gap penalties for alignments. These penalties are expressed in HMMs as probabilities of transitions between states. In the tree-HMM, this idea is given an evolutionary embodiment by defining trees of transitions. Just as the probability of a tree composed of ungapped sequences is computed, by Felsenstein's method, using matrices representing the probabilities of substitutions of residues along the edges of the tree, so the probabilities in a tree-HMM are computed by substitution matrices for both residues and transitions. How to define these matrices by a ML procedure using an algorithm that learns from a database of protein sequences is shown here. Given these matrices, one can define a tree-HMM likelihood for a set of sequences, assuming a particular tree topology and an alignment of the sequences to the model. If one could efficiently find the alignment which maximizes (or comes close to maximizing) this likelihood, then one could search for the optimal tree topology for the sequences. An alignment algorithm is defined here which, given a particular tree topology, is guaranteed to increase the likelihood of the model. Unfortunately, it fails to find global optima for realistic sequence sets. Thus further research is needed to turn the tree-HMM into a practical phylogenetic tool.