Alignments of biomolecular contact maps

Area of Science:

• Computational Biology
• Bioinformatics
• Structural Biology

Background:

• Alignments of discrete objects are fundamental in computational biology.
• Contact maps, representing RNA and protein structures, are undirected graphs with ordered vertices.
• General alignment of vertex-ordered graphs is computationally complex (NP-complete).

Purpose of the Study:

• To develop an efficient algorithm for aligning RNA secondary structures.
• To leverage the recursive structure of RNA secondary structure alignments.
• To provide a general framework for discrete object alignment.

Main Methods:

• Utilizing contact maps as graph representations of molecular structures.
• Exploiting the crossing-free matching property of RNA secondary structures.
• Adapting the Sankoff algorithm for polynomial-time RNA alignment.

Main Results:

• Demonstrated that RNA secondary structure alignment has a recursive structure.
• Developed a polynomial-time algorithm for RNA secondary structure alignment.
• Showed that tree/forest alignments of RNA secondary structures correspond to ordered edge set alignments.

Conclusions:

• RNA secondary structure alignment can be solved efficiently due to its specific properties.
• The proposed method offers a significant advancement over general graph alignment approaches.
• This work provides a foundation for understanding and aligning complex biological structures.