Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Whole genome sequencing necessitates advanced computational methods for RNA structure prediction and identification of non-coding RNAs.
• Existing methods like Pair Hidden Markov Models on Tree Structures (PHMMTSs) are limited as they cannot handle pseudoknots.
• Tree Adjoining Grammars (TAGs) are suitable for modeling pseudoknots, presenting an opportunity for extension.

Purpose of the Study:

• To extend PHMMTSs by incorporating TAGs to enable the handling of pseudoknots in RNA structural alignment.
• To develop a computational method for aligning and predicting RNA secondary structures that includes pseudoknots.

Main Methods:

• Proposed Pair Stochastic TAGs (PSTAGs) by extending PHMMTSs to align 'TAG trees', representing TAG derivation processes.
• Developed an efficient dynamic programming algorithm for PSTAGs to achieve optimal structural alignment including pseudoknots.
• Implemented the PSTAG algorithm for practical application.

Main Results:

• PSTAGs can align and predict RNA secondary structures with a simple type of pseudoknot, representing most known pseudoknot structures.
• Demonstrated the algorithm's properties using it to align and predict several small pseudoknot structures.
• Developed the first grammar-based, practically executable software for comparative analysis of RNA pseudoknot structures and non-coding RNAs.

Conclusions:

• PSTAGs offer a novel approach to RNA structural alignment, effectively incorporating pseudoknots.
• The implemented PSTAG algorithm provides a valuable tool for the comparative analysis of non-coding RNAs with pseudoknots.
• This work advances computational methods for RNA structure prediction and analysis in genomics.