Fast online and index-based algorithms for approximate search of RNA sequence-structure patterns

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Searching for homologous RNAs is enhanced by incorporating both sequence and structural information.
• Current tools struggle with mutations on both sequence and structure levels or are too slow for large databases due to high computational costs.

Purpose of the Study:

• To develop fast algorithms for approximate matching of RNA sequence-structure patterns.
• To handle mutations on both sequence and structure levels efficiently.
• To enable fast searching in large sequence databases.

Main Methods:

• Introduced new fast index-based and online algorithms for approximate RNA sequence-structure pattern matching.
• Developed a new computing scheme for dynamic programming matrices and a technique to avoid non-matching substring alignments.
• Utilized suffix arrays for sublinear running times and chaining algorithms for local/global pattern matching.

Main Results:

• Achieved significant speedups, with the online algorithm up to 45x faster and the index-based algorithm up to 560x faster than previous methods.
• Demonstrated efficient computation of semi-global alignments with user-defined edit distance thresholds.
• Successfully applied methods to the Rfam database, showing practical applicability.

Conclusions:

• The new methods offer considerable speedups, enabling approximate RNA sequence-structure pattern matching in large databases for the first time.
• The RaligNAtor software package provides a robust, well-documented, open-source implementation of these algorithms.
• These advancements facilitate more effective identification of homologous RNAs by combining sequence and structure data.