Implementations

RNA secondary structure implementations based on PCFG approaches can be utilized in :

• Finding consensus structure by optimizing structure joint probabilities over MSA.^[20][21]
• Modeling base-pair covariation to detecting homology in database searches.^[4]
• pairwise simultaneous folding and alignment.^[22][23]

Different implementation of these approaches exist. For example, Pfold is used in secondary structure prediction from a group of related RNA sequences,^[20] covariance models are used in searching databases for homologous sequences and RNA annotation and classification,^[4][24] RNApromo, CMFinder and TEISER are used in finding stable structural motifs in RNAs.^[25][26][27]

Design considerations

PCFG design impacts the secondary structure prediction accuracy. Any useful structure prediction probabilistic model based on PCFG has to maintain simplicity without much compromise to prediction accuracy. Too complex a model of excellent performance on a single sequence may not scale.^[9] A grammar based model should be able to:

• Find the optimal alignment between a sequence and the PCFG.
• Score the probability of the structures for the sequence and subsequences.
• Parameterize the model by training on sequences/structures.
• Find the optimal grammar parse tree (CYK algorithm).
• Check for ambiguous grammar (Conditional Inside algorithm).

The resulting of multiple parse trees per grammar denotes grammar ambiguity. This may be useful in revealing all possible base-pair structures for a grammar. However an optimal structure is the one where there is one and only one correspondence between the parse tree and the secondary structure.

Two types of ambiguities can be distinguished. Parse tree ambiguity and structural ambiguity. Structural ambiguity does not affect thermodynamic approaches as the optimal structure selection is always on the basis of lowest free energy scores.^[11] Parse tree ambiguity concerns the existence of multiple parse trees per sequence. Such an ambiguity can reveal all possible base-paired structures for the sequence by generating all possible parse trees then finding the optimal one.^[28][29][30] In the case of structural ambiguity multiple parse trees describe the same secondary structure. This obscures the CYK algorithm decision on finding an optimal structure as the correspondence between the parse tree and the structure is not unique.^[31] Grammar ambiguity can be checked for by the conditional-inside algorithm.^[9][11]

Building a PCFG model

A probabilistic context free grammar consists of terminal and nonterminal variables. Each feature to be modeled has a production rule that is assigned a probability estimated from a training set of RNA structures. Production rules are recursively applied until only terminal residues are left.

A starting non-terminal ${\displaystyle \mathbf {\mathit {S}} }$ produces loops. The rest of the grammar proceeds with parameter ${\displaystyle \mathbf {\mathit {L}} }$ that decide whether a loop is a start of a stem or a single stranded region s and parameter ${\displaystyle \mathbf {\mathit {F}} }$ that produces paired bases.

The formalism of this simple PCFG looks like:

${\displaystyle {\mathit {S\to LS|L}}}$

${\displaystyle {\mathit {L\to s|dFd}}}$

${\displaystyle {\mathit {F\to dFd|LS}}}$

The application of PCFGs in predicting structures is a multi-step process. In addition, the PCFG itself can be incorporated into probabilistic models that consider RNA evolutionary history or search homologous sequences in databases. In an evolutionary history context inclusion of prior distributions of RNA structures of a structural alignment in the production rules of the PCFG facilitates good prediction accuracy.^[21]

A summary of general steps for utilizing PCFGs in various scenarios:

• Generate production rules for the sequences.
• Check ambiguity.
• Recursively generate parse trees of the possible structures using the grammar.
• Rank and score the parse trees for the most plausible sequence.^[9]

Algorithms

Several algorithms dealing with aspects of PCFG based probabilistic models in RNA structure prediction exist. For instance the inside-outside algorithm and the CYK algorithm. The inside-outside algorithm is a recursive dynamic programming scoring algorithm that can follow expectation-maximization paradigms. It computes the total probability of all derivations that are consistent with a given sequence, based on some PCFG. The inside part scores the subtrees from a parse tree and therefore subsequences probabilities given an PCFG. The outside part scores the probability of the complete parse tree for a full sequence.^[32][33] CYK modifies the inside-outside scoring. Note that the term 'CYK algorithm' describes the CYK variant of the inside algorithm that finds an optimal parse tree for a sequence using a PCFG. It extends the actual CYK algorithm used in non-probabilistic CFGs.^[9]

The inside algorithm calculates ${\displaystyle \alpha (i,j,v)}$ probabilities for all ${\displaystyle i,j,v}$ of a parse subtree rooted at ${\displaystyle W_{v}}$ for subsequence ${\displaystyle x_{i},...,x_{j}}$. Outside algorithm calculates ${\displaystyle \beta (i,j,v)}$ probabilities of a complete parse tree for sequence x from root excluding the calculation of ${\displaystyle x_{i},...,x_{j}}$. The variables α and β refine the estimation of probability parameters of an PCFG. It is possible to reestimate the PCFG algorithm by finding the expected number of times a state is used in a derivation through summing all the products of α and β divided by the probability for a sequence x given the model ${\displaystyle P(x|\theta )}$. It is also possible to find the expected number of times a production rule is used by an expectation-maximization that utilizes the values of α and β.^[32][33] The CYK algorithm calculates ${\displaystyle \gamma (i,j,v)}$ to find the most probable parse tree ${\displaystyle {\hat {\pi }}}$ and yields ${\displaystyle \log P(x,{\hat {\pi }}|\theta )}$.^[9]

Memory and time complexity for general PCFG algorithms in RNA structure predictions are ${\displaystyle O(L^{2}M)}$ and ${\displaystyle O(L^{3}M^{3})}$ respectively. Restricting a PCFG may alter this requirement as is the case with database searches methods.

PCFG in homology search

Covariance models (CMs) are a special type of PCFGs with applications in database searches for homologs, annotation and RNA classification. Through CMs it is possible to build PCFG-based RNA profiles where related RNAs can be represented by a consensus secondary structure.^[4][5] The RNA analysis package Infernal uses such profiles in inference of RNA alignments.^[34] The Rfam database also uses CMs in classifying RNAs into families based on their structure and sequence information.^[24]

CMs are designed from a consensus RNA structure. A CM allows indels of unlimited length in the alignment. Terminals constitute states in the CM and the transition probabilities between the states is 1 if no indels are considered.^[9] Grammars in a CM are as follows:

${\displaystyle P\to aWb}$

probabilities of pairwise interactions between 16 possible pairs

${\displaystyle L\to aW}$

probabilities of generating 4 possible single bases on the left

${\displaystyle R\to Wa}$

probabilities of generating 4 possible single bases on the right

${\displaystyle B\to SS}$

bifurcation with a probability of 1

${\displaystyle S\to W}$

start with a probability of 1

${\displaystyle E\to \epsilon }$

end with a probability of 1

The model has 6 possible states and each state grammar includes different types of secondary structure probabilities of the non-terminals. The states are connected by transitions. Ideally current node states connect to all insert states and subsequent node states connect to non-insert states. In order to allow insertion of more than one base insert states connect to themselves.^[9]

In order to score a CM model the inside-outside algorithms are used. CMs use a slightly different implementation of CYK. Log-odds emission scores for the optimum parse tree - ${\displaystyle \log {\hat {e}}}$ - are calculated out of the emitting states ${\displaystyle P,~L,~R}$. Since these scores are a function of sequence length a more discriminative measure to recover an optimum parse tree probability score- ${\displaystyle \log {\text{P}}(x,{\hat {\pi }}|\theta )}$ - is reached by limiting the maximum length of the sequence to be aligned and calculating the log-odds relative to a null. The computation time of this step is linear to the database size and the algorithm has a memory complexity of ${\displaystyle O(M_{a}D+M_{b}D^{2})}$.^[9]

Example: Using evolutionary information to guide structure prediction

The KH-99 algorithm by Knudsen and Hein lays the basis of the Pfold approach to predicting RNA secondary structure.^[20] In this approach the parameterization requires evolutionary history information derived from an alignment tree in addition to probabilities of columns and mutations. The grammar probabilities are observed from a training dataset.

while ${\displaystyle X\neq Y}$
               ${\displaystyle C_{\text{XY}}+1}$ first sequence  pair
               ${\displaystyle C_{\text{YX}}+1}$ second sequence pair

Calculate mutation rates.
               Let  ${\displaystyle r_{\text{XY}}=}$ mutation of base X to base Y ${\displaystyle ={\frac {K~C_{\text{XY}}}{P_{x}P_{s}}}}$
               Let  ${\displaystyle r_{\text{XX}}=}$ the negative of the rate of X mutation to other bases ${\displaystyle =-\sum r_{\text{XY}}}$
               ${\displaystyle P_{s}=}$ the probability that the base is not paired.