Back to Search
Start Over
Thermodynamics of RNA structures by Wang-Landau sampling
- Source :
- Bioinformatics, Bioinformatics, Oxford University Press (OUP), 2010, 26, pp.278-286. ⟨10.1093/bioinformatics/btq218⟩, Bioinformatics, 2010, 26, pp.278-286. ⟨10.1093/bioinformatics/btq218⟩
- Publication Year :
- 2010
- Publisher :
- HAL CCSD, 2010.
-
Abstract
- Motivation: Thermodynamics-based dynamic programming RNA secondary structure algorithms have been of immense importance in molecular biology, where applications range from the detection of novel selenoproteins using expressed sequence tag (EST) data, to the determination of microRNA genes and their targets. Dynamic programming algorithms have been developed to compute the minimum free energy secondary structure and partition function of a given RNA sequence, the minimum free-energy and partition function for the hybridization of two RNA molecules, etc. However, the applicability of dynamic programming methods depends on disallowing certain types of interactions (pseudoknots, zig-zags, etc.), as their inclusion renders structure prediction an nondeterministic polynomial time (NP)-complete problem. Nevertheless, such interactions have been observed in X-ray structures. Results: A non-Boltzmannian Monte Carlo algorithm was designed by Wang and Landau to estimate the density of states for complex systems, such as the Ising model, that exhibit a phase transition. In this article, we apply the Wang-Landau (WL) method to compute the density of states for secondary structures of a given RNA sequence, and for hybridizations of two RNA sequences. Our method is shown to be much faster than existent software, such as RNAsubopt. From density of states, we compute the partition function over all secondary structures and over all pseudoknot-free hybridizations. The advantage of the WL method is that by adding a function to evaluate the free energy of arbitary pseudoknotted structures and of arbitrary hybridizations, we can estimate thermodynamic parameters for situations known to be NP-complete. This extension to pseudoknots will be made in the sequel to this article; in contrast, the current article describes the WL algorithm applied to pseudoknot-free secondary structures and hybridizations. Availability: The WL RNA hybridization web server is under construction at http://bioinformatics.bc.edu/clotelab/. Contact: clote@bc.edu
- Subjects :
- Statistics and Probability
Phase transition
Computer science
Protein Structure and Function
Monte Carlo method
Thermodynamics
Biochemistry
Nucleic acid secondary structure
03 medical and health sciences
0302 clinical medicine
microRNA
Molecule
Molecular Biology
Gene
Protein secondary structure
Monte Carlo algorithm
030304 developmental biology
0303 health sciences
Partition function (statistical mechanics)
Partition function (quantum field theory)
Computational Biology
RNA
Function (mathematics)
Ismb 2010 Conference Proceedings July 11 to July 13, 2010, Boston, Ma, Usa
Original Papers
[SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM]
NP
Computer Science Applications
Dynamic programming
Computational Mathematics
Computational Theory and Mathematics
RNA Sequence
Nucleic Acid Conformation
Ising model
[INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM]
Monte Carlo Method
Algorithm
Algorithms
030217 neurology & neurosurgery
Subjects
Details
- Language :
- English
- ISSN :
- 13674803 and 13674811
- Database :
- OpenAIRE
- Journal :
- Bioinformatics, Bioinformatics, Oxford University Press (OUP), 2010, 26, pp.278-286. ⟨10.1093/bioinformatics/btq218⟩, Bioinformatics, 2010, 26, pp.278-286. ⟨10.1093/bioinformatics/btq218⟩
- Accession number :
- edsair.doi.dedup.....38626bc5e7e1ad0f405f5fff47052e4f