An extended dual graph library and partitioning algorithm applicable to pseudoknotted RNA structures.

Area of Science:

• Computational Biology
• Structural Biology
• Bioinformatics

Background:

• Understanding RNA structure and topology is crucial for RNA research and design.
• Existing methods for representing RNA structures, like tree graphs, do not fully capture pseudoknotted RNAs.
• The RNA-As-Graphs (RAG) approach uses graph theory, specifically dual graphs, to represent RNA structures.

Purpose of the Study:

• To develop an expanded library of dual graph topologies for RNA structures.
• To identify all possible RNA subgraphs and substructures using dual graph partitioning.
• To update the RAG-3Dual database with new RNA fragments and graph IDs.

Main Methods:

• Developed a dual graph enumeration algorithm to generate an expanded library of dual graph topologies (2-9 vertices).
• Extended a dual graph partitioning algorithm to identify all possible RNA subgraphs, preserving pseudoknots and junctions.
• Applied the algorithms to existing RNA structures and updated the RAG-3Dual database.

Main Results:

• Generated an expanded library of 110,667 dual graph topologies, more than doubling the previous size.
• Identified all possible RNA substructures up to 9 vertices.
• Significantly increased the RAG-3Dual database size by over 50 times with new substructures and graph IDs.

Conclusions:

• The enlarged dual graph library and RAG-3Dual database offer a comprehensive resource for studying undiscovered RNA molecules.
• This work facilitates the design of RNA sequences with novel topologies, including complex pseudoknotted structures.
• The updated RAG approach provides a robust framework for RNA topology exploration and design.