Fast and accurate search for non-coding RNA pseudoknot structures in genomes

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Identifying non-coding RNAs (ncRNAs) by secondary structure is crucial in bioinformatics.
• Existing methods struggle with the computational complexity of RNA pseudoknots.
• Previous work proposed a graph model for RNA pseudoknots but required optimization for practical application.

Purpose of the Study:

• To develop a practical and efficient program for searching RNA pseudoknots in genomes.
• To overcome the limitations of previous graph-based methods for RNA structure-sequence alignment.
• To enable routine, fast, and accurate identification of ncRNAs with pseudoknots.

Main Methods:

• Developed preprocessing algorithms to reduce computational parameters (k and t).
• Introduced probabilistic profiling and distance penalty functions to identify plausible sequence regions for stem alignment.
• Devised a specialized tree decomposition algorithm for RNA structure graphs.

Main Results:

• Implemented the search method into a practical program named RNATOPS.
• RNATOPS identifies a small number of plausible regions (k <= 10) for each stem.
• Achieved tree decomposition with small tree width (t <= 4) for most RNA structure graphs.
• Demonstrated high sensitivity and specificity in searching prokaryotic and eukaryotic genomes for RNA structures, including pseudoknots.

Conclusions:

• RNATOPS enables routine, sensitive, and specific genome-wide searches for RNA structures with pseudoknots.
• The program offers a significant advancement in the speed and accuracy of ncRNA identification.
• This work facilitates the discovery of novel RNA structures in large-scale genomic data.