Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints
Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints
复制标题
DOI：
10.1186/1471-2105-7-400
复制
发表时间：
2006-09-04
影响因子：
3
通讯作者：
Eddy, Sean R.
中科院分区：
文献类型：
--
作者：
D Dowell, Robin;Eddy, Sean R.
背景：我们感兴趣的问题是通过将有限的比较序列信息结合到RNA折叠模型中来预测小部分同源RNA的二级结构。同时进行RNA折叠和比对的Sankoff算法是解决这一问题的基础。在应用Sankoff算法时，存在两个有待解决的问题：建立一个良好的统一比对和折叠评分系统，以及开发实用的启发式算法来处理算法的计算复杂性。结果：我们使用概率模型(配对随机上下文无关文法，pairSCFGs)作为两个成对比对和折叠评分的统一框架。开发了一种约束版本的PairSCFG结构对齐算法，该算法假设已知几个确信对齐的位置(销)。这些PIN的选择是基于概率成对序列比对的后验概率。结论：成对RNA结构比对相对于单序列折叠提高了结构预测的准确性。约束对齐是减少算法的运行时间和内存需求的一种直接方法。配对Sankoff算法的五个实际实现--This Work(Consan)、David Mathews‘s dy Align、Ian Holmes’s Stemloc、Ivo Hofacker‘s PMcomp和Jan Gorodkin’s FOLDALIGN-具有类似的总体性能，但具有不同的优点和缺点。
Background: We are interested in the problem of predicting secondary structure for small sets of homologous RNAs, by incorporating limited comparative sequence information into an RNA folding model. The Sankoff algorithm for simultaneous RNA folding and alignment is a basis for approaches to this problem. There are two open problems in applying a Sankoff algorithm: development of a good unified scoring system for alignment and folding and development of practical heuristics for dealing with the computational complexity of the algorithm.Results: We use probabilistic models ( pair stochastic context- free grammars, pairSCFGs) as a unifying framework for scoring pairwise alignment and folding. A constrained version of the pairSCFG structural alignment algorithm was developed which assumes knowledge of a few confidently aligned positions ( pins). These pins are selected based on the posterior probabilities of a probabilistic pairwise sequence alignment.Conclusion: Pairwise RNA structural alignment improves on structure prediction accuracy relative to single sequence folding. Constraining on alignment is a straightforward method of reducing the runtime and memory requirements of the algorithm. Five practical implementations of the pairwise Sankoff algorithm - this work ( Consan), David Mathews' Dynalign, Ian Holmes' Stemloc, Ivo Hofacker's PMcomp, and Jan Gorodkin's FOLDALIGN - have comparable overall performance with different strengths and weaknesses.