Covariance Model

A covariance model is fundamentally a stochastic context-free grammar (SCFG) that generates RNA sequences with a specified secondary structure. Unlike hidden Markov models, which are regular grammars, SCFGs can model nested dependencies—the hallmark of RNA base pairing. Each production rule in the grammar corresponds to a structural state: pair states emit two correlated nucleotides, while single states emit unpaired bases. The model assigns probabilities to both the sequence conservation at each position and the correlated mutations that preserve base pairing (e.g., a C-G pair mutating to U-A). This dual emission model is what gives CMs their power to detect remote homologs where primary sequence identity has eroded but structural constraints remain.

Every covariance model encodes a consensus secondary structure derived from a multiple sequence alignment of an RNA family. The structure is represented as a binary tree of nodes, where each node corresponds to a position in the alignment:

• Match (MATP) nodes: Model base-paired columns with 16 possible emission probabilities for the 16 canonical and wobble base pairs
• Match (MATL/MATR) nodes: Model unpaired columns with 4 emission probabilities
• Insert (INS) nodes: Model insertions relative to the consensus with position-independent emission probabilities
• Delete (DEL) nodes: Silent states that allow skipping consensus positions This explicit structural encoding allows CMs to simultaneously align new sequences and score them against the family model.

The defining advantage of covariance models over sequence-only profiles is their ability to detect covarying mutations—compensatory base changes that preserve secondary structure. For example, if a helix position mutates from G-C to A-U in one lineage and G-C to C-G in another, a sequence profile sees noise, but a CM recognizes these as correlated events consistent with the base-pairing constraint. This makes CMs dramatically more sensitive for detecting structured RNAs like tRNAs, rRNAs, riboswitches, and snoRNAs in genomic searches. In benchmark studies, CMs can identify RNA homologs at sequence identities below 40%, where BLAST and HMM-based methods fail entirely.

Infernal (INFERence of RNA ALignment) is the canonical software implementation of covariance models, developed by Sean Eddy's lab. It implements the CYK (Cocke-Younger-Kasami) algorithm adapted for SCFGs to align sequences to a CM and compute their log-odds scores. Key features include:

• CM construction from a structural alignment using maximum likelihood parameter estimation
• Database searching with acceleration heuristics (HMM banded filters) to make genome-scale searches tractable
• Rfam database integration: Infernal powers the Rfam RNA family database, which curates over 4,000 RNA families with their corresponding CMs
• Bit score reporting: Statistical significance is reported as bit scores with E-values, analogous to BLAST output

Covariance model parameters are estimated from a seed alignment of trusted family members with annotated secondary structure. The training process estimates:

• Transition probabilities: The probability of moving between structural states (e.g., from a pair state to a bulge state)
• Emission probabilities: For pair states, a 16-dimensional multinomial distribution over base pair types; for single states, a 4-dimensional distribution over nucleotides
• Insert state distributions: Background nucleotide frequencies for modeling insertions Maximum likelihood estimation uses observed counts from the seed alignment, often with Dirichlet priors or mixture priors to regularize parameters and prevent overfitting when seed alignments are small. The quality of the seed alignment directly determines CM specificity and sensitivity.

Despite their power, covariance models have significant limitations:

• Computational complexity: The CYK alignment algorithm scales as O(N³) with sequence length for unrestricted SCFGs, making naive CM searches prohibitively slow for genomes. Infernal mitigates this with HMM-based pre-filters that rapidly eliminate most of the search space
• Pseudoknot blindness: Standard SCFG-based CMs cannot model pseudoknots—non-nested base pairs that violate context-free grammar constraints. Specialized extensions like pseudoknot CMs or grammar-based approaches are required
• Structure annotation dependency: Building a CM requires a curated structural alignment, which demands expert knowledge and is not automatable from sequence alone
• Model size: CMs for large RNAs like 23S rRNA can contain thousands of states, requiring significant memory for database searches