Profiling and Searching for RNA Pseudoknot Structures in Genomes

  • Chunmei Liu
  • Yinglei Song
  • Russell L. Malmberg
  • Liming Cai
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3680)


We developed a new method that can profile and efficiently search for pseudoknot structures in noncoding RNA genes. It profiles interleaving stems in pseudoknot structures with independent Covariance Model (CM) components. The statistical alignment score for searching is obtained by combining the alignment scores from all CM components. Our experiments show that the model can achieve excellent accuracy on both random and biological data. The efficiency achieved by the method makes it possible to search for structures that contain pseudoknot in genomes of a variety of organisms.


Covariance Model Noncoding RNAs Neisseria Meningitidis Alignment Score Sequence Segment 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. 1.
    Akutsu, T.: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Applied Mathematics 104, 45–62 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Brown, M., Wilson, C.: RNA Pseudoknot Modeling Using Intersections of Stochastic Context Free Grammars with Applications to Database Search. In: Pacific Symposium on Biocomputing, pp. 109–125 (1995)Google Scholar
  3. 3.
    Brown, M.: Small subunit ribosomal RNA modeling using stochastic context-free grammars. In: Proc. of Int. Conf. Intel. Syst. Mol. Biol., vol. 56, pp. 57–66 (2000)Google Scholar
  4. 4.
    Cai, L., Malmberg, R.L., Wu, Y.: Stochastic Modeling of Pseudoknot Structures: A Grammatical Approach. Bioinformatics 19, I66-I73 (2003)CrossRefGoogle Scholar
  5. 5.
    Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.J.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge (1998)zbMATHCrossRefGoogle Scholar
  6. 6.
    Eddy, S., Durbin, R.: RNA sequence analysis using covariance models. Nucleic Acids Research 22, 2079–2088 (1994)CrossRefGoogle Scholar
  7. 7.
    Frank, D.N., Pace, N.R.: Ribonuclease P: unity and diversity in a tRNA processing ribozyme. Annu Rev. Biochem. 67, 153–180 (1998)CrossRefGoogle Scholar
  8. 8.
    Gautheret, D., Lambert, A.: Direct RNA motif definition and identification from multiple sequence alignments using secondary structure profiles. Journal of Molecular Biology 313, 1003–1011 (2001)CrossRefGoogle Scholar
  9. 9.
    Geobel, S.J., Hsue, B., Dombrowski, T.F., Masters, P.S.: Characterization of the RNA components of a Putative Molecular Switch in the 3’ Untranslated Region of the Murine Coronavirus Genome. Journal of Virology 78, 669–682 (2004)CrossRefGoogle Scholar
  10. 10.
    Griffiths-Jones, S., Bateman, A., Marshall, M., Khanna, A., Eddy, S.R.: Rfam: an RNA family database. Nucleic Acids Research 31, 439–441 (2003)CrossRefGoogle Scholar
  11. 11.
    Klein, R.J., Eddy, S.R.: RSEARCH: Finding Homologs of Single Structured RNA Sequences. BMC Bioinformatics 4, 44 (2003)CrossRefGoogle Scholar
  12. 12.
    Krogh, A., Brown, M., Mian, I.S., Sjolander, K., Haussler, D.: Hidden Markov models in computational biology. Applications to protein modeling. Journal of Molecular Biology 235, 1501–1531 (1994)CrossRefGoogle Scholar
  13. 13.
    Lee, D., Han, K.: Prediction of RNA Pseudoknots-Comparative Study of Genetic Algorithms. Genome Informatics 13, 414–415 (2002)Google Scholar
  14. 14.
    Lyngso, R.B., Pederson, C.N.S.: RNA pseudoknot prediction in energy based models. Journal of Computational Biology 7, 409–428 (2000)CrossRefGoogle Scholar
  15. 15.
    Macke, T., Ecker, D., Gutell, R., Gautheret, D., Case, D., Sampath, R.: RNAMotif, an RNA secondary structure definition and search algorithm. Nucleic Acids Research 29, 4724–4735 (2001)CrossRefGoogle Scholar
  16. 16.
    Nameki, N., Felden, B., Atkins, J.F., Gesteland, R.F., Himeno, H., Muto, A.: Functional and structural analysis of a pseudoknot upstream of the tag-encoded sequence in E. coli tmRNA. Journal of Molecular Biology 286(3), 733–744 (1999)CrossRefGoogle Scholar
  17. 17.
    Nguyen, V.T., Kiss, T., Michels, A.A., Bensaude, O.: 7SK small nuclear RNA binds to and inhibits the activity of CDK9/cyclin T complexes. Nature 414, 322–325 (2001)CrossRefGoogle Scholar
  18. 18.
    Reeder, J., Giegeritch, R.: Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics 5, 104 (2004)CrossRefGoogle Scholar
  19. 19.
    Rivas, E., Eddy, S.: The language of RNA: a formal grammar that includes pseudoknots. Bioinformatics 16, 334–340 (2000)CrossRefGoogle Scholar
  20. 20.
    Rivas, E., Eddy, S.: A Dynamic Programming Algorithm for RNA Structure Prediction Including Pseudoknots. Journal of Molecular Biology 285, 2053–2068 (1999)CrossRefGoogle Scholar
  21. 21.
    Ruan, J., Stormo, G.D., Zhang, W.: An iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots. Bioinformatics 20, 58–66 (2004)CrossRefGoogle Scholar
  22. 22.
    Sakakibara, Y., Brown, M., Hughey, R., Mian, I.S., Sjolander, K., Underwood, R.C., Maussler, D.: Stochastic Context-Free Grammars for tRNA Modeling. Nucleic Acids Research 22, 5112–5120 (1994)CrossRefGoogle Scholar
  23. 23.
    Storz, G.: An expanding universes of noncoding RNAs. Science 296(5571), 1260–1263 (2002)CrossRefGoogle Scholar
  24. 24.
    Uemura, Y., Hasegawa, A., Kobayashi, Y., Yokomori, T.: Tree adjoining grammars for RNA structure prediction. Theoretical Computer Science 210, 277–303 (1999)zbMATHCrossRefMathSciNetGoogle Scholar
  25. 25.
    Yang, Z., Zhu, Q., Luo, K., Zhou, Q.: The 7SK small nuclear RNA inhibits the Cdk9/cyclin T1 kinase to control transcription. Nature 414, 317–322 (2001)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Chunmei Liu
    • 1
  • Yinglei Song
    • 1
  • Russell L. Malmberg
    • 2
  • Liming Cai
    • 1
  1. 1.Department of Computer ScienceUniversity of GeorgiaAthensUSA
  2. 2.Department of Plant BiologyUniversity of GeorgiaAthensUSA

Personalised recommendations