Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
The Trees in the Peaks Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Gibbs/MCMC Sampling for Multiple RNA Interaction with Sub-optimal Solutions

verfasst von : Saad Mneimneh, Syed Ali Ahmed

Erschienen in: Algorithms for Computational Biology

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The interaction of two RNA molecules involves a complex interplay between folding and binding that warranted the development of RNA-RNA interaction algorithms. However, these algorithms do not handle more than two RNAs. We note our recent successful formulation for the multiple (more than two) RNA interaction problem based on a combinatorial optimization called Pegs and Rubber Bands. Even then, however, the optimal solution obtained does not necessarily correspond to the actual biological structure. Moreover, a structure produced by interacting RNAs may not be unique to start with. Multiple solutions (thus sub-optimal ones) are needed. Here, a sampling approach that extends our previous formulation for multiple RNA interaction is developed. By clustering the sampled solutions, we are able to reveal representatives that correspond to realistic structures. Specifically, our results on the U2-U6 complex and its introns in the spliceosome of yeast, and the CopA-CopT complex in E. Coli are consistent with published biological structures.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel A New Multi-objective Approach for Molecular Docking Based on RMSD and Binding Energy
Nächstes Kapitel Accumulated Coalescence Rank and Excess Gene Count for Species Tree Inference
Fußnoten
1
We use “first time” because many solutions can represent the same candidate; for instance, a window can split in different ways, but we still refer to it as a window split.
 
Literatur
1.
Ahmed, S.A., Mneimneh, S.: Multiple RNA interaction with sub-optimal solutions. In: Basu, M., Pan, Y., Wang, J. (eds.) ISBRA 2014. LNCS, vol. 8492, pp. 149–162. Springer, Heidelberg (2014)CrossRef
2.
Ahmed, S.A., Mneimneh, S., Greenbaum, N.L.: A combinatorial approach for multiple RNA interaction: formulations, approximations, and heuristics. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 421–433. Springer, Heidelberg (2013)CrossRefMATH
3.
Alkan, C., Karakoc, E., Nadeau, J.H., Sahinalp, S.C., Zhang, K.: RNA-RNA interaction prediction and antisense RNA target search. J. Comput. Biol. 13(2), 267–282 (2006)MathSciNetCrossRefMATH
4.
Andronescu, M., Zhang, Z.C., Condon, A.: Secondary structure prediction of interacting RNA molecules. J. Mol. Biol. 345(5), 987–1001 (2005)CrossRef
5.
Cao, S., Chen, S.J.: Free energy landscapes of RNA/RNA complexes: with applications to snRNA complexes in spliceosomes. J. Mol. Biol. 357(1), 292–312 (2006)CrossRef
6.
Chen, H.L., Condon, A., Jabbari, H.: An \(o(n^5)\) algorithm for MFE prediction of kissing hairpins and 4-chains in nucleic acids. J. Comput. Biol. 16(6), 803–815 (2009)MathSciNetCrossRef
7.
Chitsaz, H., Backofen, R., Sahinalp, S.C.: biRNA: fast RNA-RNA binding sites prediction. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol. 5724, pp. 25–36. Springer, Heidelberg (2009)CrossRef
8.
Chitsaz, H., Salari, R., Sahinalp, S.C., Backofen, R.: A partition function algorithm for interacting nucleic acid strands. Bioinformatics 25(12), i365–i373 (2009)CrossRef
9.
Ding, Y., Lawrence, C.E.: A statistical sampling algorithm for RNA secondary structure prediction. Nucleic Acids Res. 31(24), 7280–7301 (2003)CrossRef
10.
Dirks, R.M., Bois, J.S., Schaeffer, J.M., Winfree, E., Pierce, N.A.: Thermodynamic analysis of interacting nucleic acid strands. SIAM Rev. 49(1), 65–88 (2007)MathSciNetCrossRefMATH
11.
Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge (1998). Chap. 11CrossRefMATH
12.
Gallager, R.G.: Discrete Stochastic Processes, vol. 321. Springer Science & Business Media, Newyork (2012). Chap. 4MATH
13.
Geman, S., Geman, D.: Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. PAMI 6(6), 721–741 (1984)CrossRefMATH
14.
15.
Huang, F.W., Qin, J., Reidys, C.M., Stadler, P.F.: Partition function and base pairing probabilities for RNA-RNA interaction prediction. Bioinformatics 25(20), 2646–2654 (2009)CrossRef
16.
Jaccard, P.: Etude comparative de la distribution florale dans une portion des Alpes et du Jura. Impr. Corbaz (1901)
17.
Kolb, F.A., Engdahl, H.M., Slagter-Jäger, J.G., Ehresmann, B., Ehresmann, C., Westhof, E., Wagner, E.G.H., Romby, P.: Progression of a loop-loop complex to a four-way junction is crucial for the activity of a regulatory antisense RNA. EMBO J. 19(21), 5905–5915 (2000)CrossRef
18.
Kolb, F.A., Malmgren, C., Westhof, E., Ehresmann, C., Ehresmann, B., Wagner, E., Romby, P.: An unusual structure formed by antisense-target RNA binding involves an extended kissing complex with a four-way junction and a side-by-side helical alignment. RNA 6(3), 311–324 (2000)CrossRef
19.
Li, A.X., Marz, M., Qin, J., Reidys, C.M.: RNA-RNA interaction prediction based on multiple sequence alignments. Bioinformatics 27(4), 456–463 (2011)CrossRef
20.
Liu, J.S.: The collapsed gibbs sampler in bayesian computations with applications to a gene regulation problem. J. Am. Stat. Assoc. 89(427), 958–966 (1994)MathSciNetCrossRefMATH
21.
McCaskill, J.S.: The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers 29(6–7), 1105–1119 (1990)CrossRef
22.
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21(6), 1087–1092 (1953)CrossRefMATH
23.
Metzler, D., Nebel, M.E.: Predicting RNA secondary structures with pseudoknots by MCMC sampling. J. Math. Biol. 56(1–2), 161–181 (2008)MathSciNetMATH
24.
Meyer, I.M.: Predicting novel RNA-RNA interactions. Curr. Opin. Struct. Biol. 18(3), 387–393 (2008)CrossRef
25.
Mneimneh, S.: On the approximation of optimal structures for RNA-RNA interaction. IEEE/ACM Trans. Comput. Biol. Bioinf. (TCBB) 6(4), 682–688 (2009)MathSciNetCrossRef
26.
Mneimneh, S., Ahmed, S.A.: Multiple RNA interaction: beyond two. To appear in IEEE Trans. Nanobiosci. (2015)
27.
Mneimneh, S., Ahmed, S.A.: A sampling approach for multiple RNA interaction: finding sub-optimal solutions fast. In: BIOINFORMATICS 2015 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms, Rome, Italy, 21–23 February 2015
28.
Mneimneh, S., Ahmed, S.A., Greenbaum, N.L.: Multiple RNA interaction - formulations, approximations, and heuristics. In: BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms, Barcelona, Spain, 11–14 February 2013, pp. 242–249 (2013)
29.
Mückstein, U., Tafer, H., Hackermüller, J., Bernhart, S.H., Stadler, P.F., Hofacker, I.L.: Thermodynamics of RNA-RNA binding. Bioinformatics 22(10), 1177–1182 (2006)CrossRef
30.
Newby, M.I., Greenbaum, N.L.: A conserved pseudouridine modification in eukaryotic U2 snRNA induces a change in branch-site architecture. RNA 7(6), 833–845 (2001)CrossRef
31.
Pervouchine, D.D.: IRIS: intermolecular RNA interaction search. Genome Inform. Ser. 15(2), 92 (2004)MathSciNet
32.
Salari, R., Backofen, R., Sahinalp, S.C.: Fast prediction of RNA-RNA interaction. Algorithms Mol. Biol. 5(5) (2010)
33.
Sashital, D.G., Cornilescu, G., Butcher, S.E.: U2–U6 RNA folding reveals a group II intron-like domain and a four-helix junction. Nat. Struct. Mol. Biol. 11(12), 1237–1242 (2004)CrossRef
34.
Sun, J.S., Manley, J.L.: A novel U2–U6 snRNA structure is necessary for mammalian mRNA splicing. Genes Dev. 9(7), 843–854 (1995)CrossRef
35.
Tong, W., Goebel, R., Liu, T., Lin, G.: Approximation algorithms for the maximum multiple RNA interaction problem. In: Widmayer, P., Xu, Y., Zhu, B. (eds.) COCOA 2013. LNCS, vol. 8287, pp. 49–59. Springer, Heidelberg (2013)CrossRef
36.
Tong, W., Goebel, R., Liu, T., Lin, G.: Approximating the maximum multiple RNA interaction problem. Theoret. Comput. Sci. 556, 63–70 (2014)MathSciNetCrossRefMATH
37.
Wei, D., Alpert, L.V., Lawrence, C.E.: Rnag: a new gibbs sampler for predicting RNA secondary structure for unaligned sequences. Bioinformatics 27(18), 2486–2493 (2011)CrossRef
38.
Zhao, C., Bachu, R., Popović, M., Devany, M., Brenowitz, M., Schlatterer, J.C., Greenbaum, N.L.: Conformational heterogeneity of the protein-free human spliceosomal U2–U6 snRNA complex. RNA 19(4), 561–573 (2013)CrossRef
Metadaten
Titel
Gibbs/MCMC Sampling for Multiple RNA Interaction with Sub-optimal Solutions
verfasst von
Saad Mneimneh
Syed Ali Ahmed
Copyright-Jahr
2016
Buch
Algorithms for Computational Biology

Print ISBN: 978-3-319-38826-7

Electronic ISBN: 978-3-319-38827-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-38827-4_7