Hidden Markov Models for Non-sequential Alignments

0343206 Bystroff Rensselaer理工学院获得了开发蛋白质结构预测模型的资助。蛋白质是为了发挥功能而折叠成复杂形式(三维)的氨基酸链。Bystroff和他的同事编写了一个名为Scali(结构核心比对)的程序，该程序将具有相同折叠排列特定部分的蛋白质进行比对(无论其顺序如何)，然后对这些比对进行聚类，以找到反复出现的主题。结果表明，所有的蛋白质折叠都可以描述为一组小的折叠排列或核心，并且每个核心都有氨基酸偏好的特征模式。为了对这些进行建模，将比对转换为一组隐马尔可夫模型(HMM)。在这个项目中，将开发新的算法来处理与“自我避免”隐马尔可夫模型相关的具体问题。将使用启发式方法来寻找最可能的路径(根据模型)，同时给出所有自回避路径之和的精确解。精确解对于使用隐马尔可夫模型的其他方法有许多潜在的应用。

0343206 BystroffRensselaer Polytechnic Institute has been awarded a grant to develop predictive models for protein structures. Proteins are chains of amino acids that fold into complex forms (in three dimensions) in order to function. Bystroff and colleagues have written a program called SCALI (for Structural Core ALIgnment) that aligns proteins that share a certain part of their folding arrangement (regardless of their sequential ordering) and then clusters these alignments to find the recurrent themes. The results show that all protein folds can be described as a small set of folding arrangements, or cores, and that each core has characteristic patterns of amino acid preferences. To model these, the alignments are converted to a set of hidden Markov models (HMM). In this project new algorithms will be developed to deal with the specific problems associated with "self-avoiding" HMMs. A heuristic method will be used to find the most probable path (according to the models), while an exact solution is proposed for the sum over all self-avoiding paths. The exact solution has many potential applications for other methods using HMMs.