Rivas E, Eddy S R
Department of Genetics, Washington University, St. Louis, MO 63110, USA.
Bioinformatics. 2000 Apr;16(4):334-40. doi: 10.1093/bioinformatics/16.4.334.
In a previous paper, we presented a polynomial time dynamic programming algorithm for predicting optimal RNA secondary structure including pseudoknots. However, a formal grammatical representation for RNA secondary structure with pseudoknots was still lacking.
Here we show a one-to-one correspondence between that algorithm and a formal transformational grammar. This grammar class encompasses the context-free grammars and goes beyond to generate pseudoknotted structures. The pseudoknot grammar avoids the use of general context-sensitive rules by introducing a small number of auxiliary symbols used to reorder the strings generated by an otherwise context-free grammar. This formal representation of the residue correlations in RNA structure is important because it means we can build full probabilistic models of RNA secondary structure, including pseudoknots, and use them to optimally parse sequences in polynomial time.
在之前的一篇论文中，我们提出了一种多项式时间动态规划算法，用于预测包括假结在内的最优RNA二级结构。然而，仍然缺乏一种用于带有假结的RNA二级结构的形式语法表示。
在这里，我们展示了该算法与一种形式转换语法之间的一一对应关系。这个语法类包含上下文无关语法，并且超越了它以生成带有假结的结构。假结语法通过引入少量辅助符号来避免使用一般的上下文敏感规则，这些辅助符号用于对由其他方面上下文无关的语法生成的字符串进行重新排序。RNA结构中残基相关性的这种形式表示很重要，因为这意味着我们可以构建包括假结在内的RNA二级结构的完整概率模型，并使用它们在多项式时间内对序列进行最优解析。
