用于模拟符号字符串的语法理论源于计算语言学中旨在理解自然语言的结构[1][2]。概率上下文无关文法（PCFGs）在差不多引入计算语言学40年后，被应用于RNA结构的概率建模[3][4][5]。
PCFG扩展了上下文无关文法，类似于隐马尔可夫模型扩展常规语法的方式。每个生产被赋予一个概率。推导（解析）的概率是该推导中使用的产生概率的乘积。这些概率可以被视为模型的参数，对于大问题，通过机器学习来学习这些参数是方便的。 概率语法的有效性受其训练数据集的上下文约束。
PCFGs可应用于自然语言处理等多种领域，以研究RNA分子的结构和程序设计语言。设计高效的PCFGs必须权衡可扩展性和通用性。诸如语法歧义之类的问题必须被解决。语法设计会影响结果的准确性。语法分析算法具有各种时间和内存要求。
派生: 从语法中递归生成字符串的过程。
解析以下内容: 使用自动机寻找有效的推导。
解析树: 语法与序列的对齐。
下推自动机是一个PCFG语法的解析器的示例。该算法以类似堆栈的方式从左到右解析语法非终结符。这种蛮力方法效率不高。在RNA二级结构中，科克-杨格尔-卡萨米（CYK）算法算法的预测变体提供了比下推自动机更有效的语法分析替代方案。另一个PCFG解析器的例子是斯坦福统计解析器，它已经使用Treebank进行了训练[6]。
类似于 CFG，概率上下文无关语法G可以由五元组定义：
其中
PCFGs模型扩展了上下文无关文法，与隐马尔可夫模型扩展常规语法的方式相同。
Inside-Outside算法是前向-后向算法的模拟。它根据某些PCFG计算与给定序列一致的所有推导的总概率。这相当于PCFG生成序列的概率，并且直观地衡量序列与给定语法的一致性。Inside-Outside算法用于模型参数化，以估计在RNA的情况下从训练序列观察到的先前频率。
CYK算法的动态编程变体找到PCFG模型的RNA序列的维特比解析。该解析是给定PCFG最可能的序列推导。
上下文无关文法被表示为一组从模拟自然语言的尝试中得到启发的规则。[7] 这些规则是绝对的，有一个典型的语法表示，称为 巴克斯-诺尔形式。生产规则由终端组成 和非终端 S 符号和空白 也可以用作端点。 在CFG和PCFG的生产规则中，左侧只有一个非终端，而右侧可以是任何终端或非终端串。在PCFG，明渠被排除在外。[7] 语法的一个例子:
该语法可以用“|(”或“)”字符缩短为:
语法中的终端是单词，并且通过语法规则，非终端符号被转换成终端和/或非终端的串。上述语法被理解为“从非终端开始” S 排放物可以产生 a 或者 b 或者 “。 它的推导是:
如果应用于同形异义字，模糊语法可能导致解析模糊，因为相同的单词序列可以具有多于一种的解释。如报纸头条“伊拉克头寻求武器”之类的双关语是解析模糊的一个例子。
处理模棱两可的解析（最早源于语法学家 Pāṇini）的一种策略是添加更多规则，或者对它们进行优先级排序，以便一条规则优先于其他规则。然而，这样做的缺点是规则激增，通常达到难以管理的程度。另一个困难是过度生成，其中还生成未经许可的结构。
概率语法通过对频率进行权重来排序从而避免这些问题，从而产生“最有可能”（赢者通吃）的解释。随着使用模式在历时的变换中被改变，可以重新学习这些概率规则，从而更新语法。
将概率分配给生产规则就是PCFG。通过观察与要建模的语言类似组成的训练集上的分布来通知这些概率。在大多数广义语言样本中，从数据估计概率的概率语法通常优于手工制作的语法。与PCFG相比，CFGs不适用于RNA结构预测，因为虽然它们包含序列 - 结构关系，但缺乏显示序列结构潜力的评分指标[7]。
给生产规则分配概率就是PCFG。这些概率是通过观察与要建模的语言的成分相似的训练集上的分布来通知的。在大多数广义语言的样本中，概率语法(概率是从数据中估计出来的)的表现通常优于手工编写的语法。CFG与PCFGs相比不适用于RNA结构预测，因为当它们结合序列-结构关系时，它们缺乏显示序列结构潜力的评分标准[7]。
能量最小化[12][13]和PCFG提供了预测RNA二级结构的方法，具有相当的性能[14][14][14]。 然而，PCFGs的结构预测是概率性评分而不是最小自由能计算。PCFG模型参数直接来源于RNA结构数据库中观察到的不同特征的频率[14]，而不是像能量最小化方法那样通过实验确定[14][15]。
可以由PCFG建模的各种结构的类型包括长程交互，成对结构和其他嵌套结构。然而，假结无法被建模[4][5][9]。PCFGs通过为每个生产规则分配概率来扩展CFG。语法的最大概率解析树意味着最大概率结构。由于RNAs保留其主要序列的结构; RNA结构预测可以通过将来自比较序列分析的进化信息与基于这种概率的结构合理性的生物物理知识相结合来得到。此外，根据PCFG推导概率对使用PCFG规则的结构同系物的搜索结果进行评分。因此，为了建立语法来模拟碱基对和单链区的行为，首先要探索相关RNA结构多序列比对的特征[14]。
上述语法以外向内的方式生成一个字符串，即首先导出终端的最远端基础对。因此，通过在向内移动之前首先在两侧生成远端 a来导出诸如 通过在向内移动之前首先在两侧生成远端a来导出:
PCFG模型的可扩展性允许通过结合RNA的不同特征的期望来约束结构预测。这种期望可能反映了例如RNA假定某种结构的倾向[14]。然而，加入太多信息可能会增加PCFG空间和内存复杂性，但基于PCFG的模型应尽可能简单[14][16]。
语法生成的每个可能的字符串x都被赋予一个概率权重 给定PCFG模型 . 由此得出，所有可能的语法结果的所有概率之和为 . 每个配对和未配对残基的得分解释了二级结构形成的可能性。生产规则还可以评估循环长度和碱基对堆叠的顺序，因此可以探索所有可能代的范围，包括来自语法的次优结构以及基于分数阈值的接受或拒绝结构[14][14]。
实现
基于PCFG方法的RNA二级结构实现可用于：
这些方法的实现有很多。例如，Pfold用于预测来自一组相关RNA序列的二级结构[16]，协方差模型用于搜索数据库中的同源序列和RNA注释和分类[14][20]，RNApromo，CMFinder和TEISER用于在RNA中发现稳定的结构基序[21][22][23]。
设计注意事项
PCFG的设计影响二级结构预测的准确性。基于PCFG的任何有用的结构预测概率模型必须保持简单性并且不会对预测精度造成太大损害。太复杂的性能优秀的单个序列的模型可能无法扩展[14]。基于语法的模型应该能够：
每个语法产生多个解析树来表示语法歧义。这可能有助于揭示语法的所有可能的碱基对结构。然而，最佳结构是在解析树和二级结构之间存在唯一的对应结构。
两种类型的歧义可以被区分。解析树模糊度和结构模糊性。结构模糊不影响热力学方法，因为最优结构选择总是基于最低自由能分数[14]。解析树歧义涉及每个序列存在多个解析树。这种模糊性可以通过生成所有可能的解析树然后找到最佳解析树来揭示序列的所有可能的基础配对结构[24][25][26]。在结构模糊的情况下，多个解析树描述相同的二级结构。这模糊了CYK算法找到最优结构的结果，因为解析树和结构之间的对应关系不是唯一的[27]。检查语法歧义可以通过条件内部算法[14][14]。
构建PCFG模型
概率上下文无关语法由终端和非终端变量组成。要建模的每个特征都具有生产规则，该生产规则被分配概率，这个概率从RNA结构的训练集估计得到。生产规则被递归地应用，直到仅留下末端残基。
起始非终点 产生循环 . 语法的其余部分继续使用参数 决定一个环是茎的起点还是单链区域s和参数 产生成对碱基。
这个简单的PCFG的形式如下：
PCFGs在预测结构中的应用是一个多步骤的过程。此外，PCFG本身可以结合到概率模型中，该模型考虑RNA进化历史或在数据库中搜索同源序列。在进化历史背景中，在PCFG的生产规则中包含具有结构比对的RNA结构的先前分布，这有利于良好的预测准确性[17]。
在各种情况下使用PCFG的一般步骤：
算法
在RNA结构的预测中，存在几种基于PCFG的概率模型的处理算法。例如，内外算法和CYK算法。 内外算法是一种递归动态编程评分算法，可以遵循期望最大化范例。它基于某些PCFG计算与给定序列一致的所有推导的总概率。内部部分从解析树中对子树进行评分，从而给出了PCFG的子序列概率。外部部分对完整序列的完整解析树的概率进行评分[28][29] 。CYK修正了内外得分。注意，术语“CYK算法”描述了内部算法的CYK变体，其使用PCFG找到序列的最佳分析树。它扩展了非概率CFG中使用的实际CYK算法[14]。
内部算法计算 所有人的概率 解析子树的根在 对于子序列 。外部算法计算 序列完整解析树的概率 x 从根开始，不包括计算 。变量 α 和 β 改进PCFG概率参数的估计。通过对的所有乘积求和，可以找到一个状态在推导中使用的预期次数，从而重新估计PCFG算法 α 和 β 除以序列的概率 x 给定模型 。还可以找到期望最大化使用生产规则的预期次数，该期望最大化利用以下值 α 和 β。[28][29] CYK算法计算 为了找到最可能的解析树 和产量 。[14]
核糖核酸结构预测中一般PCFG算法的记忆和时间复杂度为 和 分别是。限制PCFG可能会改变这一要求，就像数据库搜索方法一样。
同源性搜索中的PCFG
协方差模型（CMs）是一种特殊类型的PCFG，其应用于在数据库中搜索同源物，注释和RNA分类。通过CMs，可以构建基于PCFG的RNA谱，其中相关的RNA可以通过共有二级结构来表示[14][14]。RNA分析包Infernal在RNA比对推断中使用此类谱[30]。Rfam数据库还使用CMs根据RNA结构和序列信息将其分为不同类[20]。
CMs从共有的RNA结构中设计。CM允许在indel对齐时长度不受限制。终端构成CM中的状态，如果不考虑indel，则状态之间的转移概率为1[14]。CM中的语法如下：
该模型具有6种可能的状态，并且每种状态语法包括不同类型的非终端二级结构概率。状态通过转换连接。 理想情况下，当前节点状态连接到所有插入状态，后续节点状态连接到非插入状态。为了允许插入多个基本插入状态，插入状态相互连接[14]。
为了给共模模型打分，使用了内外算法。CMs使用稍微不同的CYK实现。最佳解析树的对数优势发射分数- -是从发射状态中计算出来的 。因为这些分数是序列长度的函数，所以这是恢复最佳解析树概率分数的更有区别的度量 -通过限制要对齐的序列的最大长度并计算相对于null的对数优势来实现。该步骤的计算时间与数据库大小成线性关系，并且该算法的内存复杂性为 。[14]
示例:使用进化信息来指导结构预测
Knudsen和Hein的KH-99算法奠定了Pfold方法预测RNA二级结构的基础[16]。在该方法中，除了列和突变的概率之外，参数化还需要从比对树导出的进化历史信息。可以从训练数据集中来观察语法的概率。
估计成对和不成对碱基的列概率
在结构比对中，未配对碱基列和配对碱基列的概率独立于其他列。通过计算单个碱基位置和成对位置的碱基，可以获得环和茎中碱基的频率。对于碱基对 X 和 Y 出现 也被视为 。相同的碱基对，例如 被数了两次。
计算成对和不成对碱基的突变率
通过以所有可能方式配对序列，可以估计总体突变率。为了恢复可能合理的突变，应该使用序列同一性阈值，以便比较可以在相似序列之间进行。该方法在配对序列之间使用85％的同一性阈值。计算序列对之间的第一单碱基位置差异 - 除了有缺口的列 - 如果两个序列中的相同位置具有不同的碱基X，Y，则对于每个序列差异进行递增计数。
while first sequence pair second sequence pair
Calculate mutation rates.
Let
mutation of base X to base Y
Let
the negative of the rate of X mutation to other bases
the probability that the base is not paired.对于不成对碱基，使用4 X 4突变率矩阵，满足从X到Y的突变流是可逆的:[31]
对于碱基对，类似地生成16×16速率分布矩阵[32][33]。PCFG用于预测结构的先验概率分布，而后验概率由内外算法估计，最可能的结构由CYK算法找到[16]。
估计对齐概率
在计算列先验概率之后，通过对所有可能的二级结构求和来估计对准概率。任何列 C 在二级结构中 对于一个序列 D 长度 l 这样 可以相对于对齐树进行评分 T 突变模型 M。PCFG给出的先验分布是 。系统发育树， T 可以通过最大似然估计从模型中计算出来。请注意，缺口被视为未知的基数，求和可以通过 动态规划。[34]
为语法中的每个规则分配产生概率
语法中的每个结构都被分配了根据训练数据集的结构设计的生产概率。这些先验概率对于预测准确性具有重要性[17][28][29]。每个规则的使用次数取决于训练数据集中针对该特定语法特征的观察结果。这些概率在语法形式中用括号括起来，每条规则的概率总和是100％[16]。例如：
预测结构可能性
给定数据的先前对齐频率，然后可以通过最大化来计算语法预测的集合中最可能的结构 通过CYK算法。具有最高预测正确预测数的结构被报告为一致结构。[16]
KH-99算法的Pfold改进
基于PCFG的方法应该具有可扩展性和通用性。为了保证精度，需要尽可能降低速度。Pfold解决了KH-99算法在可扩展性，间隙，速度和准确性方面的局限性[16]。
尽管PCFG已被证明是预测RNA二级结构的有力工具，但蛋白质序列分析领域的用途受到限制。实际上，氨基酸字母表和蛋白质中的各种交互作用使得语法推理更具挑战性[35]。因此，大多数主要的形式语言理论蛋白质分析应用主要限于较低表现力的语法，以便基于局部相互作用对简单的功能模式进行建模[36][37] 。由于蛋白质结构通常显示高阶依赖性，包括嵌套和交叉关系，它们显然超过任何CFG的能力[35]。然而，PCFGs的开发允许表达一些依赖性，并提供了对更广泛的蛋白质模式建模的能力。
推断蛋白质语法的主要障碍之一是编码20种不同氨基酸的字母表的大小。通过使用氨基酸的物理化学性质来显着减少生产规则中右侧符号的可能组合的数量来解决这个问题的方案已经被提出：使用3个定量性质水平代替20个氨基酸类型，例如20个氨基酸类型。小型，中型或大型范德瓦尔斯体积[38]。基于这样的方案，已经使用PCFG来产生结合位点[42]和螺旋 - 螺旋接触位点描述符[39]。这些语法的一个重要特征是对其规则和解析树的分析可以提供具有生物学意义的信息[38][39]。
^Chomsky, Noam (1956). "Three models for the description of language". IRE Transactions on Information Theory. 2 (3): 113–124. doi:10.1109/TIT.1956.1056813..
^Chomsky, Noam (June 1959). "On certain formal properties of grammars". Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6..
^Grat, L. (1995). "Automatic RNA secondary structure determination with stochastic context-free grammars" (PDF). In Rawlings, C., Clark, D., Altman, R., Hunter, L., Lengauer, T and Wodak, S. Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology, AAAI Press: 136–144..
^Lefebvre, F (1995). "An optimized parsing algorithm well suited to RNA folding". In Rawlings, C.; Clark, D.; Altman, R.; Hunter, L.; Lengauer, T.; Wodak, S. Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology (PDF). AAAI Press. pp. 222–230..
^Lefebvre, F. (1996). "A grammar-based unification of several alignment and folding algorithms". In States, D. J.; Agarwal, P.; Gaasterlan, T.; Hunter, L.; Smith R. F. Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology (PDF). AAAI Press. pp. 143–153..
^Klein, Daniel; Manning, Christopher (2003). "Accurate Unlexicalized Parsing" (PDF). Proceedings of the 41st Meeting of the Association for Computational Linguistics: 423–430..
^Noam Chomsky, ed. (1957). Syntactic Structures. Mouton & Co. Publishers, Den Haag, Netherlands..
^Smith, Noah A.; Johnson, Mark (2007). "Weighted and Probabilistic Context-Free Grammars Are Equally Expressive". Computational Linguistics. 33 (4): 477. doi:10.1162/coli.2007.33.4.477..
^Katsirelos, George; Narodytska, Nina; Walsh, Toby (2008). "The Weighted Cfg Constraint". Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Lecture Notes in Computer Science. 5015. p. 323. CiteSeerX 10.1.1.150.1187. doi:10.1007/978-3-540-68155-7_31. ISBN 978-3-540-68154-0..
^Johnson, Mark (2005). "log linear or Gibbs models" (PDF)..
^Chi, Zhiyi (March 1999). "Statistical properties of probabilistic context-free grammars" (PDF). Computational Linguistics. 25 (1): 131–160. Archived from the original (PDF) on 2010-08-21..
^McCaskill J. S. (1990). "The Equilibrium Partition Function and Base Pair Binding Probabilities for RNA Secondary Structure". Biopolymers. 29 (6–7): 1105–19. doi:10.1002/bip.360290621. PMID 1695107..
^Juan V.; Wilson C. (1999). "RNA Secondary Structure Prediction Based on Free Energy and Phylogenetic Analysis". J. Mol. Biol. 289 (4): 935–947. doi:10.1006/jmbi.1999.2801. PMID 10369773..
^Eddy S. R. & Durbin R. (1994). "RNA sequence analysis using covariance models". Nucleic Acids Research. 22 (11): 2079–2088. doi:10.1093/nar/22.11.2079. PMC 308124. PMID 8029015..
^Mathews D. H.; Sabina J.; Zuker M.; Turner D. H. (1999). "Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure". J. Mol. Biol. 288 (5): 911–940. doi:10.1006/jmbi.1999.2700. PMID 10329189..
^B. Knudsen & J. Hein. (2003). "Pfold: RNA secondary structure prediction using stochastic context-free grammars". Nucleic Acids Research. 31 (13): 3423–3428. doi:10.1093/nar/gkg614. PMC 169020. PMID 12824339..
^Knudsen B.; Hein J. (1999). "RNA Secondary Structure Prediction Using Stochastic Context-Free Grammars and Evolutionary History". Bioinformatics. 15 (6): 446–454. doi:10.1093/bioinformatics/15.6.446. PMID 10383470..
^Rivas E.; Eddy S. R. (2001). "Noncoding RNA Gene Detection Using Comparative Sequence Analysis". BMC Bioinformatics. 2 (1): 8. doi:10.1186/1471-2105-2-8. PMC 64605. PMID 11801179..
^Holmes I.; Rubin G. M. (2002). Pairwise RNA Structure Comparison with Stochastic Context-Free Grammars. In. Pac. Symp. Biocomput. pp. 163–174. doi:10.1142/9789812799623_0016. ISBN 978-981-02-4777-5..
^P. P. Gardner; J. Daub; J. Tate; B. L. Moore; I. H. Osuch; S. Griffiths-Jones; R. D. Finn; E. P. Nawrocki; D. L. Kolbe; S. R. Eddy; A. Bateman. (2011). "Rfam: Wikipedia, clans and the "decimal" release". Nucleic Acids Research. 39 (Suppl 1): D141–D145. doi:10.1093/nar/gkq1129. PMC 3013711. PMID 21062808..
^Yao Z.; Weinberg Z.; Ruzzo W. L. (2006). "CMfinder-a covariance model based RNA motif finding algorithm". Bioinformatics. 22 (4): 445–452. doi:10.1093/bioinformatics/btk008. PMID 16357030..
^Rabani M.; Kertesz M.; Segal E. (2008). "Computational prediction of RNA structural motifs involved in post-transcriptional regulatory processes". Proc. Natl. Acad. Sci. USA. 105 (39): 14885–14890. doi:10.1073/pnas.0803169105. PMC 2567462. PMID 18815376..
^Goodarzi H.; Najafabadi H. S.; Oikonomou P.; Greco T. M.; Fish L.; Salavati R.; Cristea I. M.; Tavazoie S. (2012). "Systematic discovery of structural elements governing stability of mammalian messenger RNAs". Nature. 485 (7397): 264–268. doi:10.1038/nature11013. PMC 3350620. PMID 22495308..
^Sipser M. (1996). Introduction to Theory of Computation. Brooks Cole Pub Co..
^Michael A. Harrison (1978). Introduction to Formal Language Theory. Addison-Wesley..
^Hopcroft J. E.; Ullman J. D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley..
^Giegerich R. (2000). "Explaining and Controlling Ambiguity in Dynamic Programming" (PDF). In Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching 1848 Edited By: Giancarlo R., Sankoff D. Montréal, Canada: Springer-Verlag, Berlin: 46–59..
^Lari K.; Young S. J. (1990). "The estimation of stochastic context-free grammars using the inside-outside algorithm". Computer Speech and Language. 4: 35–56. doi:10.1016/0885-2308(90)90022-X..
^Lari K.; Young S. J. (1991). "Applications of stochastic context-free grammars using the inside-outside algorithm". Computer Speech and Language. 5 (3): 237–257. doi:10.1016/0885-2308(91)90009-F..
^Nawrocki E. P., Eddy S. R. (2013). "Infernal 1.1:100-fold faster RNA homology searches". Bioinformatics. 29 (22): 2933–2935. doi:10.1093/bioinformatics/btt509. PMC 3810854. PMID 24008419..
^Tavaré S. (1986). "Some probabilistic and statistical problems in the analysis of DNA sequences". Lectures on Mathematics in the Life Sciences. American Mathematical Society. 17: 57–86..
^Muse S. V. (1995). "Evolutionary analyses of DNA sequences subject to constraints of secondary structure". Genetics. 139 (3): 1429–1439. PMC 1206468. PMID 7768450..
^Schöniger M.; von Haeseler A. (1994). "A stochastic model for the evolution of autocorrelated DNA sequences". Mol. Phylogenet. Evol. 3 (3): 240–7. doi:10.1006/mpev.1994.1026. PMID 7529616..
^J. K. Baker (1979). "Trainable grammars for speech recognition". In D. Klatt and J. Wolf, Editors, Speech Communication Papers for the 97th Meeting of the Acoustical Society of America. 36 (20): 545–550..
^Searls, D (2013). "Review: A primer in macromolecular linguistics". Biopolymers. 99 (3): 203–217. doi:10.1002/bip.22101. PMID 23034580..
^Krogh, A; Brown, M; Mian, I; Sjolander, K; Haussler, D (1994). "Hidden Markov models in computational biology: Applications to protein modeling". J Mol Biol. 235 (5): 1501–1531. doi:10.1006/jmbi.1994.1104. PMID 8107089..
^Sigrist, C; Cerutti, L; Hulo, N; Gattiker, A; Falquet, L; Pagni, M; Bairoch, A; Bucher, P (2002). "PROSITE: a documented database using patterns and profiles as motif descriptors". Brief Bioinform. 3 (3): 265–274. doi:10.1093/bib/3.3.265. PMID 12230035..
^Dyrka, W; Nebel, J-C (2009). "A Stochastic Context Free Grammar based Framework for Analysis of Protein Sequences". BMC Bioinformatics. 10: 323. doi:10.1186/1471-2105-10-323. PMC 2765975. PMID 19814800..
^Dyrka, W; Nebel J-C, Kotulska M (2013). "Probabilistic grammatical model of protein language and its application to helix-helix contact site classification". Algorithms for Molecular Biology. 8 (1): 31. doi:10.1186/1748-7188-8-31. PMC 3892132. PMID 24350601..
暂无