STRMS

STRMS identifies non-coding RNA (ncRNA) structural motifs in sequence databases using a structure-first search approach that emphasizes secondary structure and can accommodate potential pseudoknots.

Key Features:

• Structure-Based Search: STRMS accepts the secondary structure of the query as input, enabling searches that prioritize structural motifs over primary sequence.
• Flexibility and Customization: STRMS allows fine-tuning of search constraints to accommodate variability in structure rigidity and local sequence requirements.
• Subtree Homeomorphism Algorithm: STRMS represents RNA secondary structures as ordered, rooted trees and applies an O(mn) subtree-homeomorphism pattern-matching algorithm to locate query structures in targets.
• Pseudoknot Consideration: An extension implements handling of pseudoknots using an O(n² log n) approach relevant to motifs such as riboswitches.
• Ranking and Visualization: STRMS ranks candidate occurrences by similarity and outputs an HTML file visualizing predicted structures for query and hits.

Scientific Applications:

• Motif discovery: Searching for known and novel ncRNA motifs such as riboswitches and tRNAs within large sequence databases.
• Riboswitch discovery in bacteria: Identification of additional purine bacterial riboswitch candidates in newly sequenced bacterial genomes.

Methodology:

Combines pre-folding of sequences, representation of RNA secondary structures as ordered rooted trees, an O(mn) subtree-homeomorphism pattern-matching algorithm, and an O(n² log n) extension to handle pseudoknots.