Identification of consensus RNA secondary structures using suffix arrays.

Area of Science:

• Bioinformatics
• Computational Biology
• Molecular Biology

Background:

• Identifying conserved RNA secondary structures typically requires aligned sequences.
• Obtaining accurate sequence alignments is challenging without prior structural knowledge.
• Automated tools are needed to facilitate RNA motif discovery.

Purpose of the Study:

• To present a novel algorithm, Seed, for identifying conserved RNA secondary structure motifs.
• To enable motif discovery in sets of unaligned RNA sequences.
• To evaluate the algorithm's effectiveness in uncovering known RNA structures.

Main Methods:

• Developed the Seed algorithm to define and search the space of inducible secondary structure motifs from a seed sequence.
• Employed a general-to-specific search strategy for motif identification.
• Utilized suffix arrays for efficient enumeration of biological palindromes and matching of RNA secondary structure expressions.
• Evaluated twelve free energy-based objective functions for motif discrimination.

Main Results:

• The Seed algorithm successfully identified conserved RNA secondary structure motifs in unaligned sequences.
• The search space induced from a seed sequence was shown to contain known motifs.
• Suffix arrays provided efficient computational methods for motif discovery.
• Objective functions combining free energy demonstrated high positive predictive value and sensitivity in identifying known motifs.

Conclusions:

• Support and exclusion constraints enable a feasible exhaustive search of the RNA secondary structure space.
• The Seed algorithm's search space effectively encompasses known RNA motifs.
• Simple, free energy-based objective functions can reliably identify conserved RNA motifs.