Grammar String

Grammar String encodes noncoding RNA (ncRNA) sequences and their secondary structures into a context-free grammar (CFG)-based string representation to enable alignment and consensus secondary structure derivation.

Key Features:

• Novel Representation: Encodes ncRNA sequence and secondary structure within a context-free grammar (CFG) framework using a specialized alphabet, transforming structural alignment into a sequence alignment problem.
• Incorporation of Pseudoknots: Implements full RNA grammar capabilities to represent and align pseudoknot-containing secondary structures.
• Consensus Structure Derivation: Derives consensus secondary structures from homologous ncRNA families by aligning grammar-based strings.
• Benchmarking: Performance was benchmarked against Murlet and RNASampler, showing competitive consensus structure quality.

Scientific Applications:

• ncRNA secondary structure analysis: Supports understanding and prediction of ncRNA secondary structures, including pseudoknotted motifs.
• Homologous ncRNA family analysis: Applied to hundreds of ncRNA families from BraliBase 2.1 for consensus structure derivation.

Methodology:

Encodes both sequence and secondary structure into a grammar-based string format, leverages the parameter space of context-free grammars to perform alignment and derive consensus structures, and was benchmarked against Murlet and RNASampler.