Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

RNA Secondary Structure Prediction Via Energy Density Minimization

  • Conference paper

Abstract

There is a resurgence of interest in RNA secondary structure prediction problem (a.k.a. the RNA folding problem) due to the discovery of many new families of non-coding RNAs with a variety of functions. The vast majority of the computational tools for RNA secondary structure prediction are based on free energy minimization. Here the goal is to compute a non-conflicting collection of structural elements such as hairpins, bulges and loops, whose total free energy is as small as possible. Perhaps the most commonly used tool for structure prediction,mfold/RNAfold, is designed to fold a single RNA sequence. More recent methods, such asRNAscf andalifold are developed to improve the prediction quality of this tool by aiming to minimize the free energy of a number of functionally similar RNA sequences simultaneously. Typically, the (stack) prediction quality of the latter approach improves as the number of sequences to be folded and/or the similarity between the sequences increase. If the number of available RNA sequences to be folded is small then the predictive power of multiple sequence folding methods can deteriorate to that of the single sequence folding methods or worse.

In this paper we show that delocalizing the thermodynamic cost of forming an RNA substructure by considering theenergy density of the substructure can significantly improve on secondary structure prediction via free energy minimization. We describe a new algorithm and a software tool that we callDensityfold, which aims to predict the secondary structure of an RNA sequence by minimizing the sum of energy densities of individual substructures. We show that when only one or a small number of input sequences are available,Densityfold can outperform all available alternatives. It is our hope that this approach will help to better understand the process of nucleation that leads to the formation of biologically relevant RNA substructures.

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

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Mapping RNA Form & Function. Science 309(5740) (September 2, 2005)

    Google Scholar 

  2. RNA_align tool,http://www.csd.uwo.ca/faculty/kzhang/rna/

  3. Akutsu, T.: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discr. Appl. Math. 104(1-3), 45–62 (2000)

    Article MATH MathSciNet  Google Scholar 

  4. Arslan, A.N., Egecioglu, O., Pevzner, P.A.: A New Approach to Sequence Comparison: Normalized Sequence Alignment. In: Proc. RECOMB, pp. 2–11. ACM, New York (2001)

    Google Scholar 

  5. Bafna, V., Tang, H., Zhang, S.: Consensus Folding of Unaligned RNA Sequences Revisited. In: Miyano, S., Mesirov, J., Kasif, S., Istrail, S., Pevzner, P.A., Waterman, M. (eds.) RECOMB 2005. LNCS (LNBI), vol. 3500, pp. 172–187. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  6. Condon, A., Davy, B., Rastegari, B., Zhao, S., Tarrant, F.: Classifying RNA pseudoknotted structures. Theor. Comput. Sci. 320(1), 35–50 (2004)

    Article MATH MathSciNet  Google Scholar 

  7. Davydov, E., Batzoglou, S.: A Computational Model for RNA Multiple Structural Alignment. In: GECCO 2004. LNCS, vol. 3103, pp. 254–269. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  12. Lin, G., Ma, B., Zhang, K.: Edit distance between two RNA structures. In: Proc. RECOMB, pp. 211–220. ACM, New York (2001)

    Google Scholar 

  13. Lyngso, R.B., Zuker, M., Pedersen, C.N.S.: Fast evaluation of internal loops in RNA secondary structure prediction. Bioinformatics 15(6), 440–445 (1999)

    Article  Google Scholar 

  14. Ma, B., Wang, L., Zhang, K.: Computing similarity between RNA structures. Theoretical Computer Science 276(1-2), 111–132 (2002)

    Article MATH MathSciNet  Google Scholar 

  15. Mathews, D., Sabina, J., Zuker, M., Turner, D.: Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J. Mol. Biol. 288(5), 911–940 (1999)

    Article  Google Scholar 

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

    Article  Google Scholar 

  17. Nussinov, R., Jacobson, A.: Fast algorithm for predicting the secondary structure of single stranded RNA. Proc. Nat. Acad. Sci. USA 77(11), 6309–6313 (1980)

    Article  Google Scholar 

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

    Article  Google Scholar 

  19. Sankoff, D.: Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems. SIAM J. Appl. Math. 45, 810–825 (1985)

    Article MATH MathSciNet  Google Scholar 

  20. Thompson, J., Higgins, D., Gibson, T.: Clustal-W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position specific gap penalties and weight matrix choice. Nucl. Acids Res. 22, 4673–4680 (1994)

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Genome Sciences, University of Washington, USA

    Can Alkan

  2. School of Computing Science, Simon Fraser University, Canada

    Emre Karakoc & S. Cenk Sahinalp

  3. Department of Molecular Biology and Biochemistry, Simon Fraser University, Canada

    Peter Unrau & H. Alexander Ebhardt

  4. Department of Computer Science, University of Western Ontario, Canada

    Kaizhong Zhang

  5. Department of Computer Science, Washington University in St Louis, USA

    Jeremy Buhler

Authors
  1. Can Alkan

    You can also search for this author inPubMed Google Scholar

  2. Emre Karakoc

    You can also search for this author inPubMed Google Scholar

  3. S. Cenk Sahinalp

    You can also search for this author inPubMed Google Scholar

  4. Peter Unrau

    You can also search for this author inPubMed Google Scholar

  5. H. Alexander Ebhardt

    You can also search for this author inPubMed Google Scholar

  6. Kaizhong Zhang

    You can also search for this author inPubMed Google Scholar

  7. Jeremy Buhler

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Georgia Institute of Technology and Università di Padova,  

    Alberto Apostolico

  2. Topic Chairs, P.O. Box

    Concettina Guerra

  3. Center for Molecular Biology and Computer Sciecne Department, Brown University, 115 Waterman St., 02912, Providence, RI, USA

    Sorin Istrail

  4. University of California, San Diego, USA

    Pavel A. Pevzner

  5. Department of Molecular and Computational Biology, University of Southern California, 1050 Childs Way, 90089-2910, Los Angeles, CA, USA

    Michael Waterman

Rights and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Alkan, C.et al. (2006). RNA Secondary Structure Prediction Via Energy Density Minimization. In: Apostolico, A., Guerra, C., Istrail, S., Pevzner, P.A., Waterman, M. (eds) Research in Computational Molecular Biology. RECOMB 2006. Lecture Notes in Computer Science(), vol 3909. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11732990_12

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp