Skip to main content
SpringerLink
Log in

Computational methods in noncoding RNA research

  • Published:
Journal of Mathematical Biology Aims and scope Submit manuscript

Abstract

Non protein-coding RNAs (ncRNAs) are a research hotspot in bioinformatics. Recent discoveries have revealed new ncRNA families performing a variety of roles, from gene expression regulation to catalytic activities. It is also believed that other families are still to be unveiled. Computational methods developed for protein coding genes often fail when searching for ncRNAs. Noncoding RNAs functionality is often heavily dependent on their secondary structure, which makes gene discovery very different from protein coding RNA genes. This motivated the development of specific methods for ncRNA research. This article reviews the main approaches used to identify ncRNAs and predict secondary structure.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abrahams J.P., van den Berg M., van Batenburg E., Pleij C. (1990). Prediction of RNA secondary structure, including pseudoknotting, by computer simulation. Nucleic Acids Res. 18(10): 3035–3044

    Google Scholar 

  2. Akmaev V.R., Kelley S.T., Stormo G.D. (2000). Phylogenetically enhanced statistical tools for RNA structure prediction. Bioinformatics 16(6): 501–512

    Google Scholar 

  3. Allali J., Sagot M.F. (2005). A new distance for high level RNA secondary structure comparison. Trans. Comput. Biol. Bioinform. 2(1): 3–14

    Google Scholar 

  4. Bafna V., Tang H., Zhang S. (2006). Consensus folding of unaligned RNA sequences revisited. J. Comput. Biol. 13(2): 283–295

    MathSciNet  Google Scholar 

  5. Bafna, V., Zhang, S.: Fast, R.: Fast database search tool for non-coding RNA. In: Proceedings of the 2004 IEEE Computational Systems Bioinformatics Conference (CSB2004) (2004)

  6. Barash D. (2004). Second eigenvalue of the Laplacian matrix for predicting RNA conformational switch by mutation. Bioinformatics 20(12): 1861–1869

    Google Scholar 

  7. di Bernardo D., Down T., Hubbard T. (2003). ddbRNA: detection of conserved secondary structures in multiple alignments. Bioinformatics 19(13): 1606–1611

    Google Scholar 

  8. Bernhart S.H., Hofacker I.L., Stadler P.F. (2006). Local RNA base pairing probabilities in large sequences. Bioinformatics 22(5): 614–615

    Google Scholar 

  9. Blackburn, E.H.: Telomerase (1993) The RNA World. Cold Spring Harbor Laboratory Press, New York

  10. Bonhoeffer S., McCaskill J.S., Stadler P.F., Schuster P. (1993). RNA multi-structure landscapes—a study based on temperature dependent partition functions. Eur. Biophys. J. 22(1): 13–24

    Google Scholar 

  11. Bonnet E., Wuyts J., Rouze P., de Peer Y.V. (2004). Evidence that microRNA precursors, unlike other non-coding RNAs, have lower folding free energies than random sequences. Bioinformatics 20(17): 2911–2917

    Google Scholar 

  12. Bouthinon D., Soldano H. (1999). A new method to predict the consensus secondary structure of a set of unaligned RNA sequences. Bioinformatics 15(10): 785–798

    Google Scholar 

  13. Brown J.W. (1999). The ribonuclease P database. Nucleic Acids Res. 27(1): 314

    Google Scholar 

  14. Brown M.P.S. (2000). Small subunit ribosomal RNA modeling using stochastic context-free grammars. Proc. Int. Conf. Intell. Syst. Mol. Biol. 8: 57–66

    Google Scholar 

  15. Brown, M.P.S., Wilson, C.: RNA pseudoknot modeling using intersections of stochastic context free grammars with applications to database search. Pacif Symposium on Biocomputing, pp. 109–125 (1996)

  16. Chan C.Y., Lawrence C.E., Ding Y. (2005). Structure clustering features on the Sfold web server. Bioinformatics 21(20): 3926–3928

    Google Scholar 

  17. Chen J.H., Le S.Y., Maizel J.V. (2000). Prediction of common secondary structures of RNAs: a genetic algorithm approach. Nucleic Acids Res. 28(4): 991–999

    Google Scholar 

  18. Chen S.J., Dill K.A. (2000). RNA folding energy landscapes. Proc. Natl Acad. Sci. 97(2): 646–651

    Google Scholar 

  19. Chiang, D., Joshi, A.K.: Formal grammars for estimating partition functions of double-stranded chain molecules. In: Proceedings of HLT 2002, San Diego, March, pp. 63–67 (2002)

  20. Churkin, A., Barash, D.: RNAmute: RNA secondary structure mutation analysis tool. BMC Bioinformatics 7(221) (2006)

  21. Clote P. (2005). An efficient algorithm to compute the landscape of locally optimal RNA secondary structures with respect to the Nussinov–Jacobson energy model. J. Comput. Biol. 12(1): 83–101

    MathSciNet  Google Scholar 

  22. Clote P. (2005). RNALOSS: a web server for RNA locally optimal secondary structures. Nucleic Acids Res. 33: 600–604

    Google Scholar 

  23. Clote P., Ferre F., Kranakis E., Krizanc D. (2005). Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency. RNA 11: 578–591

    Google Scholar 

  24. Cole J.R., Chai B., Marsh T.L., Farris R.J., Wang Q., Kulam S.A., Chandra S., McGarell D.M., Schmidt T.M., Garrity G.M., Tiedje J.M. (2003). The Ribosomal Database Project (RDP-II): previewing a new autoaligner that allows regular updates and the new prokaryotic taxonomy. Nucleic Acids Res. 31(1): 442–443

    Google Scholar 

  25. Cormen T.H., Leiserson C.E., Rivest R.L. (1990). Introduction to Algorithms. MIT Press, Cambridge

    Google Scholar 

  26. Coventry, A., Kleitman, D.J., Berger, B.: MSARI: multiple sequence alignments for statistical detection of RNA secondary structure. Proc. Natl Acad. Sci. 101(33), 12, 102–12, 107 (2004)

    Google Scholar 

  27. Cupal J., Hofacker I.L., Stadler P.F. (1996). Dynamic programming algorithm for the density of states of RNA secondary structures. Comput. Sci. Biol. 96: 184–186

    Google Scholar 

  28. Danilova L.V., Pervouchine D.D., Favorov A.V., Mironov A.A. (2006). RNAKINETICS: a web server that models secondary structure kinetics of an elongating RNA. J. Bioinform. Comput. Biol. 4(2): 589–596

    Google Scholar 

  29. Ding Y. (2006). Statistical and bayesian approaches to RNA secondary structure prediction. RNA 12: 323–331

    Google Scholar 

  30. Ding Y., Chan C.Y., Lawrence C.E. (2004). Sfold web server for statistical folding and rational design of nucleic acids. Nucleic Acids Res. 32(Web Server issue): W135–W141

    Google Scholar 

  31. Ding Y., Lawrence C.E. (2003). A statistical sampling algorithm for RNA secondary structure prediction. Nucleic Acids Res. 31(24): 7280–7301

    Google Scholar 

  32. Dirks R.M., Pierce N.A. (2003). A partition function algorithm for nucleic acids secondary structure including pseudoknots. J. Comput. Chem. 24(13): 1664–1677

    Google Scholar 

  33. Dirks R.M., Pierce N.A. (2004). An algorithm for computing nucleic acid base-pairing probabilities including pseudoknots. J. Comput. Chem. 25: 1295–1304

    Google Scholar 

  34. Do C.B., Woods D.A., Batzoglou S. (2006). CONTRAfold: RNA secondary structure prediction without physics-based models. Bioinformatics 22(14): e90–e98

    Google Scholar 

  35. Dowell, R.D.: RNA structural alignment using stochastic context-free grammars. Ph.D. Thesis (2004)

  36. Dowell R.D., Eddy S.R. (2006). Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints. BMC Bioinformatics 7: 400

    Google Scholar 

  37. Eddy S.R. (2001). Non-coding RNA genes and the modern RNA world. Nat. Rev. 2: 919–929

    Google Scholar 

  38. Eddy S.R. (2002). Computational genomics of noncoding RNA genes. Cell 109: 137–140

    Google Scholar 

  39. Eddy S.R. (2002). A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure. BMC Bioinformatics 3(1): 18

    Google Scholar 

  40. Eddy S.R. (2004). How do RNA folding algorithms work. Nat. Biotechnol. 22(11): 1457–1458

    Google Scholar 

  41. Eddy, S.R., Durbin, R.: RNA sequence analysis using covariance models. Nucleic Acids Res., 2079–2088 (1994)

  42. Fichant G.A., Burks C. (1991). Identifying potential tRNA genes in genomic DNA sequences. J. Mol. Biol. 220: 659–671

    Google Scholar 

  43. Flamm C., Fontana W., Hofacker I.L., Schuster P. (2000). RNA folding at elementary step resolution. RNA 6: 325–338

    Google Scholar 

  44. Higgings D.G., Thompson J.D., Gibson T.J. (1996). Using CLUSTAL for multiple sequence alignments. Methods Enzymol. 266: 383–402

    Google Scholar 

  45. Gan H.H., Fera D., Zorn J., Shiffeldrim N., Tang M., Laserson U., Kim N., Schlick T. (2004). RAG: RNA-As-Graphs database—concepts, analysis, and features. Bioinformatics 20(8): 1285–1291

    Google Scholar 

  46. Gorodkin J., Heyer L.J., Stormo G.D. (1997). Finding the most significant common sequence and structure motifs in a set of RNA sequences. Nucleic Acids Res. 25(18): 3724–3732

    Google Scholar 

  47. Gorodkin J., Stricklin S.L., Stormo G.D. (2001). Discovering common stem-loop motifs in unaligned RNA sequences. Nucleic Acids Res. 29(10): 2135–2144

    Google Scholar 

  48. Greider, C.: Telomerase biochemistry and regulation (1995) In: Telomeres. Cold Spring Harbor Laboratory Press, New York

  49. Griffiths-Jones S., Bateman A., Marshall M., Khanna A., Eddy S.R. (2003). Rfam: an RNA family database. Nucleic Acids Res. 31(1): 439–441

    Google Scholar 

  50. Griffiths-Jones S., Moxon S., Marshall M., Khanna A., Eddy S.R., Bateman A. (2005). Rfam: annotating non-coding RNAs in complete genomes. Nucleic Acids Res. 33: D121–D124

    Google Scholar 

  51. Gulko, B., Haussler, D.: Using multiple alignment and phylogenetic trees to detect RNA secondary structure. Pacific Symposium on Biocomputing, pp. 350–367 (1996)

  52. Haebel P., Gutmann S., Ban N. (2004). Dial tm for rescue: tmRNA engages ribosomes stalled on defective mRNAs. Curr. Opin. Struct. Biol. 14: 58–65

    Google Scholar 

  53. Hannon G.J. (2002). RNA interference. Nature 418: 244–251

    Google Scholar 

  54. Havgaard J.H., Lyngso R., Stormo G.D., Gorodkin J. (2005). Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%. Bioinformatics 21(9): 1815–1824

    Google Scholar 

  55. Herbel J., Stadler P.F. (2006). Hairpins in a haystack: recognizing microRNA precursors in comparative genomics data. Bioinformatics 22(14): 197–202

    Google Scholar 

  56. Higgs P.G. (2000). RNA secondary structure: physical and computational aspects. Q. Rev. Biophys. 33(3): 199–253

    Google Scholar 

  57. Hochsmann, M., Toller, T., Giegerich, R., Kurtz, S.: Local similarity in RNA secondary structures. In: Proceedings of the Computational Systems Bioinformatics (CSB 2003), 159–168 (2003)

  58. Hochsmann M., Voss B., Giegerich R. (2004). Pure multiple RNA secondary structure alignments: a progressive profile approach. IEEE Trans. Comput. Biol. Bioinform. 1(1): 53–62

    Google Scholar 

  59. Hofacker I.L. (2003). Vienna RNA secondary structure server. Nucleic Acids Res. 31(13): 3429–3431

    Google Scholar 

  60. Hofacker I.L., Benhart S.H.F., Stadler P.F. (2004). Alignment of RNA base pairing probability matrices. Bioinformatics 20(14): 2222–2227

    Google Scholar 

  61. Hofacker I.L., Fekete M., Stadler P.F. (2002). Secondary structure prediction for aligned RNA sequences. J. Mol. Biol. 319: 1059–1066

    Google Scholar 

  62. Hofacker I.L., Fontana W., Stadler P.F., Bonhoeffer L.S., Tacker M., Schuster P. (1994). Fast folding and comparison of RNA secondary structures. Monatsh. Chem. 125: 167–188

    Google Scholar 

  63. Holmes, I.: Accelerated probabilistic inference of RNA struture evolution. BMC Bioinformatics 6(73) (2005). doi:10.1186/1471-2105-6-73

  64. Holmes, I., Rubin, G.M.: Pairwise RNA structure comparison with SCFGs. Pacif Symposium on Biocomputing, pp. 163–174 (2002)

  65. Huttenhofer A., Schattner P., Polacek N. (2005). Non-coding RNAs: hope or hype. Trends Genet. 21(5): 289–297

    Google Scholar 

  66. James B.D., Olsen G.J., Pace N.R. (1989). Phylogenetic comparative analysis of RNA secondary structure. Methods Enzymol. 180: 227–239

    Article  Google Scholar 

  67. Ji Y., Xu X., Stormo G.D. (2004). A graph theoretical approach for predicting common RNA secondary structure motifs including psudoknots in unaligned sequences. Bioinformatics 20(10): 1591–1602

    Google Scholar 

  68. Jiang T., Lin G., Ma B., Zhang K. (2002). A general edit distance between RNA structures. J. Comput. Biol. 9: 371–388

    Google Scholar 

  69. Jiang T., Wang L., Zhang K. (1995). Alignment of trees—an alternative to tree edit. Theor. Comput. Sci. 143: 137–148

    MATH  MathSciNet  Google Scholar 

  70. Juan V., Wilson C. (1999). RNA secondary structure prediction based on free energy and phylogenetic analysis. J. Mol. Biol. 289: 935–947

    Google Scholar 

  71. Just W. (2001). Computational complexity of multiple sequence alignment with SP-score. J. Comput. Biol. 8(6): 615–623

    MathSciNet  Google Scholar 

  72. Keenan R.J., Freymann D.M., Stroud R.M., Walter P. (2001). The signal recognition particle. Annu. Rev. Biochem. 70: 755–775

    Google Scholar 

  73. Klein R.J., Eddy S.R. (2003). RSEARCH: finding homologs of single structured RNA sequences. BMC Bioinformatics 4(1): 44

    Google Scholar 

  74. Klein R.J., Misulovin Z., Eddy S.E. (2002). Noncoding RNA genes identified in AT-rich hyperthermophiles. Proc. Natl Acad. Sci. 99(11): 7542–7547

    Google Scholar 

  75. Knight R., Birmingham A., Yarus M. (2004). BayesFold: rational 2o folds that combine thermodynamic, covariation, and chemical data for aligned RNA sequences. RNA 10: 1323–1336

    Google Scholar 

  76. Knudsen B., Hein J. (1999). RNA secondary structure prediction using stochastic context-free grammars and evolutionary history. Bioinformatics 15(6): 446–454

    Google Scholar 

  77. Knudsen B., Hein J. (2003). Pfold: RNA secondary structure prediction using stochastic context-free grammars. Nucleic Acids Res. 31(13): 3423–3428

    Google Scholar 

  78. Krogh A., Brown M., Mian I.S., Sjolander K., Haussler D. (1994). Hidden markov models in computational biology—applications to protein modeling. J. Mol. Biol. 235: 1501–1531

    Google Scholar 

  79. Lagos-Quintana M., Rauhut R., Lendeckel W., Tuschl T. (2001). Identification of novel genes coding for small expressed RNAs. Science 294: 853–858

    Google Scholar 

  80. Lai E.C., Tomancak P., Williams R.W., Rubin G.M. (2003). Computational identification of Drosophila microRNA genes. Genome Biol. 4: R42.1–R42.20

    Google Scholar 

  81. Laslett D., Canback B. (2004). ARAGORN, a program to detect tRNA genes and tmRNA genes in nucleotide sequences. Nucleic Acids Res. 32(1): 11–16

    Google Scholar 

  82. Laslett D., Canback B., Andersson S. (2002). BRUCE: a program for the detection of transfer-messenger RNA genes in nucleotide sequences. Nucleic Acids Res. 30(15): 3449–3453

    Google Scholar 

  83. Le S.V., Chen J.H., Currey K.M., Maizel J.V.J. (1988). A program for predicting significant RNA secondary structures. Comput. Appl. Biosci. 4(1): 153–159

    Google Scholar 

  84. Lim L.P., Lau N.C., Weinstein E.G., Abdelhakim A., Yekta S., Rhoades M.W., Burge C.B., Bartel D.P. (2003). The microRNAs of Caenorhabditis elegans. Genes Dev. 17: 991–1008

    Google Scholar 

  85. Liu C., Bai B., Skogerbo G., Cai L., Deng W., Zhang Y., Bu D., Zhao Y., Chen R. (2005). NONCODE: an integrated knowledge database of non-coding RNAs. Nucleic Acids Res. 33: D112–D115

    Google Scholar 

  86. Liu J., Gough J., Rost B. (2006). Distinguishing protein-coding from non-coding RNAs through support vector machines. PLoS Genet. 2(4): e29

    Google Scholar 

  87. Lowe T.M., Eddy S.R. (1997). tRNAscan-SE: a program for improved detection of transfer RNA genes in genomic sequence. Nucleic Acids Res. 25(5): 955–964

    Google Scholar 

  88. Lowe T.M., Eddy S.R. (1999). A computational screen for methylation guide snoRNAs in yeast. Science 283: 1168–1171

    Google Scholar 

  89. Lowe, T.M.J.: Combining new computational and traditional experimental methods to identify tRNA and snoRNA gene families. Master’s thesis, Washington University (1999)

  90. Luck R., Graf S., Steger G. (1999). ConStruct: a tool for thermodynamic controlled prediction of conserved structure. Nucleic Acids Res. 27(21): 4208–4217

    Google Scholar 

  91. Lyngso R.B., Pedersen C.N. (2000). RNA pseudoknot prediction in energy-based models. J. Comput. Biol. 7: 409–427

    Google Scholar 

  92. Mathews D.H. (2005). Predicting a set of minimal free energy RNA secondary structures common to two sequences. Bioinformatics 21(10): 2246–2253

    Google Scholar 

  93. Mathews D.H., Disney M.D., Childs J.L., Schroeder S.J., Zuker M., Turner D.H. (2004). Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure. Proc. Natl Acad. Sci. 101(19): 7287–7292

    Google Scholar 

  94. Mathews D.H., Turner D.H. (2002). Dynalign: an algorithm for finding the secondary structure common to two RNA sequences. J. Mol. Biol. 317: 191–203

    Google Scholar 

  95. Mattick, J.S., Makunin, I.V.: Non-coding RNA. Human Mol. Genet. 15(1), 17–29 (2006)

    Google Scholar 

  96. McCaskill J.S. (1990). The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers 29: 1105–1119

    Google Scholar 

  97. Meyer, I.M., Miklos, I.: Co-transcriptional folding is encoded within RNA genes. BMC Mol. Biol. 5(10) (2004). doi:10.1186/1471-2199-5-10

  98. Militello, K.T., Patel, V., Chessler, A.D., Fisher, J.K., Kasper, J.M., Gunasekera, A., Wirth, D.F.: RNA polymerase II synthesizes antisense RNA in Plasmodium falciparum. RNA 11 (2005)

  99. Moulton V. (2005). Tracking down noncoding RNAs. Proc. Natl Acad. Sci. 102(7): 2269–2270

    Google Scholar 

  100. Nam J.W., Kim J., Kim S.K., Zhang B.T. (2006). ProMIR II: a web server for the probabilistic prediction of clustered, nonclustered, conserved and nonconserved microRNAs. Nucleic Acids Res. 34: 455–458

    Google Scholar 

  101. Notredame C., Brien E.A.O., Higgins D.G. (1997). RAGA: RNA sequence alignment by genetic algorithm. Nucleic Acids Res. 25(22): 4570–4580

    Google Scholar 

  102. Notredame C., Higgins D.G., Heringa J. (2000). T-Coffee: a novel method for fast and accurate multiple sequence alignment. J. Mol. Biol. 302(1): 205–217

    Google Scholar 

  103. de Novoa P.G., Williams K.P. (2004). The tmRNA website: reductive evolution of tmRNA in plastids and other endosymbionts. Nucleic Acids Res. 32: D104–D108

    Google Scholar 

  104. Nussinov R., Pieczenik G., Griggs J.R., Kleitman D.J. (1978). Algorithms for loop matchings. SIAM J. Appl. Math. 35(1): 68–82

    MATH  MathSciNet  Google Scholar 

  105. Pavesi A., Conterio F., Bolchi A., Dieci G., Ottonello S. (1994). Identification of new eukaryotic tRNA genes in genomic DNA databases by a multistep weight matrix analysis of transcriptional control regions. Nucleic Acids Res. 22(7): 1247–1256

    Google Scholar 

  106. Pedersen J.S., Meyer I.M., Forsberg R., Simmonds P., Hein J. (2004). A comparative method for finding and folding RNA secondary structures withing protein-coding regions. Nucleic Acids Res. 32(16): 4925–4936

    Google Scholar 

  107. Perriquet O., Touzet H., Dauchet M. (2003). Finding the common structure shared by two homologous RNAs. Bioinformatics 19(1): 108–116

    Google Scholar 

  108. Piccinelli P., Rosenblad M.A., Samuelsson T. (2005). Identification and analysis of ribonuclease P and MRP RNA in a broad range of eukaryotes. Nucleic Acids Res. 33(14): 4485–4495

    Google Scholar 

  109. Pipas J.M., McMahon J.E. (1975). Method for predicting RNA secondary structure. Proc. Natl Acad. Sci. 72(6): 2017–2021

    Google Scholar 

  110. Reeder, J., Giegerich, R.: Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics 5(104) (2004)

  111. Reeder J., Hochsmann M., Rehmsmeier M., Voss B., Giegerich R. (2006). Beyond mfold: recent advances in RNA bioinformatics. J. Biotechnol. 124(1): 41–55

    Google Scholar 

  112. Regalia M., Rosenblad M.A., Samuelsson T. (2002). Prediction of signal recognition particle RNA genes. Nucleic Acids Res. 30(15): 3368–3377

    Google Scholar 

  113. Reis E.M., Louro R., Nakaya H.I., Verjovski-Almeida S. (2005). As antisense RNA gets intronic. OMICS 9(1): 2–12

    Google Scholar 

  114. Reis E.M., Nakaya H.I., Louro R., Canavez F.C., Flatschart A.V., Almeida G.T., Egidio C.M., Paquola A.C., Machado A.A., Festa F., Yamamoto D., Alvarenga R., da Silva C.C., Brito G.C., Simon S.D., Moreira-Filho C.A., Leite K.R., Camara-Lopes L.H., Campos F.S., Gimba E., Vignal G.M., El-Dorry H., Sogayar M.C., Barcinski M.A., da Silva A.M., Verjovski-Almeida S. (2004). Antisense intronic non-coding RNA levels correlate to the degree of tumor differentiation in prostate cancer. Oncogene 23(39): 6684–6692

    Google Scholar 

  115. Ren J., Rastegari B., Condon A., Hoos H. (2005). HotKnots: heuristic prediciton of RNA secondary structures including pseudoknots. RNA 11: 1419–1504

    Google Scholar 

  116. Rivas E. (2005). Evolutionary models for insertions and deletions in a probabilistic modeling framework. BMC Bioinformatics 6: 63

    Google Scholar 

  117. Rivas E., Eddy S.R. (1999). A dynamic programming algorithm for RNA structure prediction including pseudoknots. J. Mol. Biol. 285: 2053–2068

    Google Scholar 

  118. Rivas E., Eddy S.R. (2000). Secondary structure alone is generally not statistically significant for the detection of noncoding RNAs. Bioinformatics 16(7): 583–605

    Google Scholar 

  119. Rivas E., Eddy S.R. (2001). Noncoding RNA gene detection using comparative sequence analysis. BMC Bioinformatics 2(1): 8

    Google Scholar 

  120. Rosenblad M.A., Gorodkin J., Knudsen B., Zwieb C., Samuelsson T. (2003). SRPDB: signal recognition particle database. Nucleic Acids Res. 31(1): 363–364

    Google Scholar 

  121. Ruan J., Stormo G.D., Zhang W. (2004). ILM: a web server for predicting RNA secondary structures with pseudoknots. Nucleic Acids Res. 32(Web Server issue): W146–W149

    Google Scholar 

  122. Ruan J., Stormo G.D., Zhang W. (2004). An iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots. Bioinformatic 20(1): 58–66

    Google Scholar 

  123. Sakakibara, Y., Brown, M.: The application of stochastic context-free grammars to folding, aligning and modeling homologous RNA sequences (1993). Techn. Rep. UCSC-CRL-94-14

  124. Sakakibara, Y., Brown, M., Hughey, R., Mian, I.S., Sjolander, K., Underwood, R.C., Haussler, D.: Stochastic context-free grammars for tRNA modeling. Nucleic Acids Res., 5112–5120 (1994)

  125. Sankoff D. (1985). Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM J. Appl. Math. 45(5): 810–825

    MATH  MathSciNet  Google Scholar 

  126. Schattner P. (2002). Searching for RNA genes using base-composition statistics. Nucleic Acids Res. 30(9): 2076–2082

    Google Scholar 

  127. Schattner P., Brooks A.N., Lowe T.M. (2005). The tRNAscan-SE, snoscan and snoGPS web servers for the detection of tRNAs and snoRNAs. Nucleic Acids Res. 33: 686–689

    Google Scholar 

  128. Schattner P., Decatur W.A., Davis C.A., Ares M.J., Fournier M.J., Lowe T.M. (2004). Genome-wide searching for pseudouridylation guide snoRNAs: analysis of Saccharomyces cerevisiae genome. Nucleic Acids Res. 32(14): 4281–4296

    Google Scholar 

  129. Schmitz M., Steger G. (1996). Description of RNA folding by simulated annealing. J. Mol. Biol. 255: 254–266

    Google Scholar 

  130. Sczyrba A., Kruger J., Mersch H., Kurtz S., Giegerich R. (2003). RNA-related tools on the Bielefeld bioinformatics server. Nucleic Acids Res. 31(13): 3767–3770

    Google Scholar 

  131. Searls D.B. (2002). The language of genes. Nature 420: 211–217

    Google Scholar 

  132. Shapiro B.A., Zhang K. (1990). Comparing multiple RNA secondary structures using tree comparisons. Comput. Appl. Biosci. 6(4): 309–318

    Google Scholar 

  133. Siebert S., Backofen R. (2005). MARNA: multiple alignment and consensus structure prediction of RNAs based on sequence structure comparisons. Bioinformatics 21(16): 3352–3359

    Google Scholar 

  134. Steffen P., Voss B., Rehmsmeier M., Reeder J., Giegerich R. (2006). RNAshapes: an integrated RNA analysis package based on abstract shapes. Bioinformatics 22(4): 500–503

    Google Scholar 

  135. Storz G. (2002). An expandind universe of noncoding RNAs. Science 296: 1260–1263

    Google Scholar 

  136. Tabaska J.E., Cary R.B., Gabow H.N., Stormo G.D. (1998). An RNA folding method capable of identifying pseudoknots and base triples. Bioinformatics 14(8): 691–699

    Google Scholar 

  137. Taneda A. (2005). Cofolga: a genetic algotithm for finding the common folding of two RNAs. Comput. Biol. Chem. 29: 111–119

    MATH  Google Scholar 

  138. Tinoco I.J., Uhlenbeck O.C., Levine M.D. (1971). Estimation of secondary structure in ribonucleic acids. Nature 230(5293): 362–367

    Google Scholar 

  139. Touzet H., Perriquet O. (2004). CARNAC: folding families of related RNAs. Nucleic Acids Res. 32: W142–W145

    Google Scholar 

  140. Tsui V., Macke T., Case D.A. (2003). A novel method for finding tRNA genes. RNA 9: 507–517

    Google Scholar 

  141. Turner D.H., Sugimoto N. (1988). RNA structure prediction. Annu. Rev. Biophys. Biophys. Chem. 17: 167–192

    Google Scholar 

  142. Underwood, R.C.: Stochastic Context-Free Grammars for Modeling Three Spliceosomal Small Nuclear Ribonucleic Acids. Master’s thesis, Baskin Center for Computer Engineering and Information Sciences, University of California (1994)

  143. Uzilov, A.V., Keegan, J.M., Mathews, D.H.: Detection of non-coding RNAs on the basis of predicted secondary structure formation free energy change. BMC Bioinformatics 7 (2006). doi:10.1186/1417-2105-7-173

  144. Voss, B., Giegerich, R., Rehmsmeier, M.: Complete probabilistic analysis of RNA shapes. BMC Biology 4(5) (2006)

  145. Wang C., Ding C., Meraz R.F., Holbrook S.R. (2006). PSoL: a positive sample only learning algorithm for finding ncRNA genes. Bioinformatics 22(21): 2590–2596

    Google Scholar 

  146. Wang X., Zhang J., Li F., Gu J., He T., Zhang X., Li Y. (2005). MicroRNA identification based on sequence and structure alignment. Bioinformatics 21(18): 3610–3614

    Google Scholar 

  147. Washiet S., Hofacker I.L. (2004). Consensus folding of aligned sequences as a new measure for the detection of functional RNAs by comparative genomics. J. Mol. Biol. 342: 19–30

    Google Scholar 

  148. Washietl S., Hofacker I.L., Stadler P.F. (2005). Fast and reliable prediction of noncoding RNAs. Proc. Natl Acad. Sci. 102(7): 2454–2459

    Google Scholar 

  149. Waterman M.S., Smith T.F. (1978). RNA secondary structure: a complete mathematical analysis. Math. Biosci. 42: 257–266

    MATH  Google Scholar 

  150. Weinberg Z., Ruzzo W.L. (2004). Exploiting conserved structure for faster annotation of non-coding RNAs without loss of accuracy. Bioinformatics 20(suppl 1): i334–i341

    Google Scholar 

  151. Weinberg Z., Ruzzo W.L. (2006). Sequence-based heuristics for faster annotation of non-coding RNA families. Bioinformatics 22(1): 35–39

    Google Scholar 

  152. Workman C., Krogh A. (1999). No evidence that mRNAs have lower folding free energies than random sequences with the same dinucleotide distribution. Nucleic Acids Res. 27(24): 4816–4822

    Google Scholar 

  153. Wuchty S., Fontana W., Hofacker I.L., Schuster P. (1999). Complete suboptimal folding of RNA and the stability of secondary structure. Biopolymers 49: 145–165

    Google Scholar 

  154. Yang, J.H., Zhang, X.C., Huang, Z.P., Zhou, H., Huang, M.B., Zhang, S., Chen, Y.Q., Qu, L.H.: snoSeeker: an advanced computational package for screening of guide and orphan sno RNA genes in the human genome. Nucleic Acids Res (2006). doi:10.1093/nar/gkl672

  155. Yang Z., Zhu Q., Luo K., Zhou Q. (2001). The 7SK small nuclear RNA inhibits the CDK9/cyclin T1 kinase to control transcription. Nature 414: 317–322

    Google Scholar 

  156. Ying X., Luo H., Luo J., Li W. (2004). RDfolder: a web server for prediction of RNA secondary structure. Nucleic Acids Res. 32(Web Server issue): W150–W153

    Google Scholar 

  157. Zuker M. (1989). On finding all suboptimal foldings of an RNA molecule. Science 244: 48–52

    MathSciNet  Google Scholar 

  158. Zuker M. (2003). Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res. 31(13): 3406–3415

    Google Scholar 

  159. Zuker, M., Mathews, D.H., Turner, D.H.: Algorithms and thermodynamics for RNA secondary structure prediction: a practical guide. RNA Biochem. Biotechnol. 11–43 (1999)

  160. Zuker M., Stiegler P. (1981). Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res. 9(1): 133–148

    Google Scholar 

Download references

Author information

Author notes

  1. Hernando A. del Portillo

    Present address: Barcelona Centre for International Health Research CRESIB, Barcelona, Spain

Authors and Affiliations

  1. Institute of Mathematics and Statistics, University of Sao Paulo, Sao Paulo, SP, Brazil

    Ariane Machado-Lima & Alan Mitchell Durham

  2. Institute of Biomedical Sciences, University of Sao Paulo, Sao Paulo, SP, Brazil

    Hernando A. del Portillo

Authors
  1. Ariane Machado-Lima
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hernando A. del Portillo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alan Mitchell Durham
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ariane Machado-Lima.

Additional information

During the execution of this work, AML was supported by CAPES fellowship.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Machado-Lima, A., del Portillo, H.A. & Durham, A.M. Computational methods in noncoding RNA research. J. Math. Biol. 56, 15–49 (2008). https://doi.org/10.1007/s00285-007-0122-6

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00285-007-0122-6

Keywords

Search

Navigation