The algorithm applies graph-theoretical approaches to automatically detect common RNA secondary structure motifs in a group of functionally or evolutionarily related RNA sequences. The advantages of this method are that it:
does not require the presence of global sequence similarities (but can take advantage of it),
does not require prior structural alignment, and
is able to detect pseudoknot structures.
It finds sets of stable stems conserved across multiple sequences, and assembles compatible conserved stems to form consensus secondary structure motifs. It predicts common RNA secondary structures in three major steps:
1. Find all possible stable stems in each sequence and compare them pairwise between sequences,
2. Find all potential conserved stems shared by subsets of sequences,
3. Assemble best sets of conserved stems to construct consensus secondary structure profiles, and report a number of them after structure refinement.
To better understand how comRNA works, please read the paper.
Note: The format of my pseudocode for the maximum-clique-finding algorithm was messed-up in the final print of the paper. Here is the pseudocode in the correct format.
We have tested comRNA on some RNA sequences with known secondary structures, in which it is capable of detecting the real structures completely or partially correct and outperforms other existing programs for similar purposes.
Test sequence sets and prediction results:
Comparison with other RNA secondary structure predicting programs
If comRNA is used in work that is published, please cite:
Yongmei Ji, Xing Xu and Gary D. Stormo, A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences. Bioinformatics, 2004 Jul 10; 20(10):1591-1602.
Please send bug reports, requests, comments and suggestions to Yongmei Ji (yji A T genetics.wustl.edu), Xing Xu (xingxu A T genetics.wustl.edu)and Gary Stormo (stormo A T genetics.wustl.edu).
Source code for the latest version: comRNA 1.80
Instruction for installation and usage: README
comRNA development log: updates
Last updated May 20, 2004.
Last updated May 20, 2004.RoadRunnerSports.com