Local similarity in RNA secondary structures.

Area of Science:

• Computational Biology
• Bioinformatics
• Structural Bioinformatics

Background:

• Accurate comparison of RNA secondary structures is crucial for understanding their function and evolution.
• Existing algorithms for tree and forest alignment have limitations for local similarity detection in complex biological structures.
• Identifying regulatory motifs often relies on sequence conservation, overlooking structurally conserved elements.

Purpose of the Study:

• To develop and present a systematic treatment of alignment distance and local similarity algorithms for trees and forests.
• To extend existing tree alignment methods for calculating local forest alignments, specifically for RNA secondary structures.
• To enable the discovery of regulatory motifs based on structural preservation, irrespective of sequence conservation and position.

Main Methods:

• Building upon Jiang et al.'s (1995) ordered tree alignment algorithm to compute local forest alignments.
• Developing optimized dynamic programming implementations using dense, two-dimensional tables to reduce space requirements.
• Proposing a new forest representation for RNA secondary structures to facilitate reasonable scoring of edit operations.

Main Results:

• An efficient algorithm for local forest alignment with a time complexity of O(|F(1)| |F(2) deg(F(1)) deg(F(2)) (deg(F(1)) + deg(F(2))) was developed.
• Engineered dynamic programming implementations significantly reduced space complexity.
• A novel visualization technique for RNA secondary structure alignments was introduced, aiding comparison.

Conclusions:

• The proposed algorithms provide a robust framework for local similarity analysis in RNA secondary structures.
• The new representation and scoring system enable more accurate comparison of RNA structures.
• The study demonstrates the potential for discovering functionally relevant regulatory motifs through structural analysis alone.