Structator

Structator performs RNA sequence-structure pattern matching to identify RNAs with conserved secondary-structure motifs within large sequence databases.

Key Features:

• Index-Based Search: Employs affix arrays as an index data structure to enable bidirectional pattern search that incorporates structural constraints.
• Sublinear Running Time: Achieves sublinear expected running time by leveraging base-pairing information to reduce the search space, with benchmark experiments on the Rfam database showing up to two orders of magnitude speed improvement.
• Chaining Approach: Integrates a chaining method to assemble matches for RNAs with multiple ordered structural patterns and to eliminate spurious intermediate matches for low-specificity patterns.
• Handling Complex Structures: Matches complex secondary structures such as stem-loops using an inside-out strategy that matches loop regions first and then the corresponding base-pairing boundaries.

Scientific Applications:

• Functional Annotation: Identifying conserved structural motifs to support functional inference of RNA molecules.
• Comparative Genomics: Analyzing evolutionary conservation of RNA sequence-structure motifs across species.
• RNA Structure Prediction: Assisting prediction and validation of RNA secondary structures by locating known sequence-structure patterns.

Methodology:

Preprocesses target databases using affix arrays to enable efficient bidirectional pattern searches; leverages base-pairing information to reduce the search space and attain sublinear expected running time; applies a chaining method to combine ordered pattern matches and an inside-out matching strategy for stem-loops (matching loop then paired boundaries).