Hidden Markov Models for Non-sequential Alignments

0343206 BystroffRensselaer Polytechnic Institute获得了一笔赠款，用于开发蛋白质结构的预测模型。蛋白质是氨基酸链，折叠成复杂的形式（三维）以发挥功能。Bystroff及其同事编写了一个名为SCALI（Structural Core ALIgnation）的程序，该程序将共享其折叠排列的某一部分（无论其顺序如何）的蛋白质对齐，然后将这些对齐进行聚类以找到重复的主题。结果表明，所有的蛋白质折叠可以被描述为一个小的折叠排列，或核心，每个核心具有氨基酸偏好的特征模式。为了对这些进行建模，将比对转换为一组隐马尔可夫模型（HMM）。在这个项目中，将开发新的算法来处理与“自我避免”障碍相关的特定问题。一个启发式的方法将被用来找到最可能的路径（根据模型），而一个精确的解决方案，提出了所有的自我避免路径的总和。该精确解对其他使用Hynomial的方法有许多潜在的应用。

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.