Document Open Access Logo

BPPart: RNA-RNA Interaction Partition Function in the Absence of Entropy

Authors Ali Ebrahimpour-Boroojeny, Sanjay Rajopadhye, Hamidreza Chitsaz

PDF
Thumbnail PDF

File

LIPIcs.WABI.2021.14.pdf
  • Filesize: 1.78 MB
  • 24 pages

Document Identifiers

Author Details

Ali Ebrahimpour-Boroojeny
  • Department of Computer Science, Columbia University, New York, NY, USA
  • New York Genome Center, NY, USA
Sanjay Rajopadhye
  • Department of Computer Science, Colorado State University, Fort Collins, CO, USA
Hamidreza Chitsaz
  • Waymo, Mountain View, CA, USA

Cite As Get BibTex

Ali Ebrahimpour-Boroojeny, Sanjay Rajopadhye, and Hamidreza Chitsaz. BPPart: RNA-RNA Interaction Partition Function in the Absence of Entropy. In 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 201, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.WABI.2021.14

Abstract

A few classes of RNA-RNA interaction (RRI) with complex roles in cellular functions, such as miRNA-target and lncRNAs, have already been studied. Accordingly, RRI bioinformatics tools proposed in the last decade are tailored for those specific classes. Interestingly, there are somewhat unnoticed mRNA-mRNA interactions in the literature with potentially drastic biological roles. Hence, there is a need for high-throughput generic RRI bioinformatics tools that can be used in more comprehensive settings. In this work, we revisit two of the RRI partition function algorithms, piRNA and rip. These are equivalent methods that implement the most comprehensive and computationally intensive thermodynamic model for RRI. We propose simpler models that are shown to retain the vast majority of the thermodynamic information that the more complex models capture. Specifically, we simplify the energy model by ignoring the system’s entropy and show its equivalency to a base-pair counting model. We allow different weights for base-pairs to maximize the correlations with the full thermodynamic model. Our newly developed algorithm, BPPart, is 225× faster than piRNA and is more expressive and easier to analyze due to its simplicity and order of magnitude reduction in the number of dynamic programming tables. Still, based on our analysis of both the real and randomly generated data, its scores achieve a correlation of 0.855 with piRNA at 37^{∘}C. Finally, we illustrate one use-case of such simpler models to generate hypotheses about the roles of specific RNAs in various diseases. We have made our tool publicly available and believe that this faster and more expressive model will make the incorporation of physics-guided information in complex RRI analysis and prediction models more accessible.

Subject Classification

ACM Subject Classification
  • Applied computing → Computational biology
Keywords
  • RNA-RNA Interaction
  • Partition Function
  • RNA Secondary Structure

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Can Alkan, Emre Karakoc, Joseph H Nadeau, S Cenk Sahinalp, and Kaizhong Zhang. Rna-rna interaction prediction and antisense rna target search. Journal of Computational Biology, 13(2):267-282, 2006. Google Scholar
  2. Mirela Andronescu, Zhi Chuan Zhang, and Anne Condon. Secondary structure prediction of interacting rna molecules. Journal of molecular biology, 345(5):987-1001, 2005. Google Scholar
  3. Stephan H Bernhart, Hakim Tafer, Ulrike Mückstein, Christoph Flamm, Peter F Stadler, and Ivo L Hofacker. Partition function and base pairing probabilities of rna heterodimers. Algorithms for Molecular Biology, 1(1):1-10, 2006. Google Scholar
  4. Doron Betel, Anjali Koppal, Phaedra Agius, Chris Sander, and Christina Leslie. Comprehensive modeling of microrna targets predicts functional non-conserved and non-canonical sites. Genome biology, 11(8):R90, 2010. Google Scholar
  5. Anke Busch, Andreas S Richter, and Rolf Backofen. Intarna: efficient prediction of bacterial srna targets incorporating target site accessibility and seed regions. Bioinformatics, 24(24):2849-2856, 2008. Google Scholar
  6. Song Cao and Shi-Jie Chen. Predicting rna pseudoknot folding thermodynamics. Nucleic acids research, 34(9):2634-2652, 2006. Google Scholar
  7. Hamidreza Chitsaz, Rolf Backofen, and S Cenk Sahinalp. birna: Fast rna-rna binding sites prediction. In International Workshop on Algorithms in Bioinformatics, pages 25-36. Springer, 2009. Google Scholar
  8. Hamidreza Chitsaz, Raheleh Salari, S.Cenk Sahinalp, and Rolf Backofen. A partition function algorithm for interacting nucleic acid strands. Bioinformatics, 25(12):i365-i373, 2009. Also ISMB/ECCB proceedings. Google Scholar
  9. Ilaria Di Donato, Silvia Bianchi, Nicola De Stefano, Martin Dichgans, Maria Teresa Dotti, Marco Duering, Eric Jouvent, Amos D Korczyn, Saskia AJ Lesnik-Oberstein, Alessandro Malandrini, et al. Cerebral Autosomal Dominant Arteriopathy with Subcortical Infarcts and Leukoencephalopathy (CADASIL) as a model of small vessel disease: update on clinical, diagnostic, and management aspects. BMC medicine, 15(1):41, 2017. Google Scholar
  10. Laura DiChiacchio, Michael F Sloma, and David H Mathews. Accessfold: predicting rna-rna interactions with consideration for competing self-structure. Bioinformatics, 32(7):1033-1039, 2015. Google Scholar
  11. Roumen A Dimitrov and Michael Zuker. Prediction of hybridization and melting for double-stranded nucleic acids. Biophysical Journal, 87(1):215-226, 2004. Google Scholar
  12. Robert M Dirks, Justin S Bois, Joseph M Schaeffer, Erik Winfree, and Niles A Pierce. Thermodynamic analysis of interacting nucleic acid strands. SIAM review, 49(1):65-88, 2007. Google Scholar
  13. Robert M Dirks and Niles A Pierce. A partition function algorithm for nucleic acid secondary structure including pseudoknots. Journal of computational chemistry, 24(13):1664-1677, 2003. Google Scholar
  14. Ali Ebrahimpour-Boroojeny, Sanjay Rajopadhye, and Hamidreza Chitsaz. Bppart and bpmax: Rna-rna interaction partition function and structure prediction for the base pair counting model. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.01235.
  15. Dimos Gaidatzis, Erik van Nimwegen, Jean Hausser, and Mihaela Zavolan. Inference of mirna targets using evolutionary conservation and pathway analysis. BMC bioinformatics, 8(1):69, 2007. Google Scholar
  16. Jing Gong, Di Shao, Kui Xu, Zhipeng Lu, Zhi John Lu, Yucheng T Yang, and Qiangfeng Cliff Zhang. Rise: a database of rna interactome from sequencing experiments. Nucleic acids research, 46(D1):D194-D201, 2018. Google Scholar
  17. Mitchell Guttman, Ido Amit, Manuel Garber, Courtney French, Michael F Lin, David Feldser, Maite Huarte, Or Zuk, Bryce W Carey, John P Cassady, et al. Chromatin signature reveals over a thousand highly conserved large non-coding RNAs in mammals. Nature, 458(7235):223-227, 2009. Google Scholar
  18. Ivo L Hofacker, Walter Fontana, Peter F Stadler, L Sebastian Bonhoeffer, Manfred Tacker, and Peter Schuster. Fast folding and comparison of rna secondary structures. Monatshefte für Chemie/Chemical Monthly, 125(2):167-188, 1994. Google Scholar
  19. Justin Bo-Kai Hsu, Chih-Min Chiu, Sheng-Da Hsu, Wei-Yun Huang, Chia-Hung Chien, Tzong-Yi Lee, and Hsien-Da Huang. mirtar: an integrated system for identifying mirna-target interactions in human. BMC bioinformatics, 12(1):300, 2011. Google Scholar
  20. Hong Ming Hu, Karen O'Rourke, Mark S Boguski, and Vishua M Dixit. A novel RING finger protein interacts with the cytoplasmic domain of CD40. Journal of Biological Chemistry, 269(48):30069-30072, 1994. Google Scholar
  21. Fenix WD Huang, Jing Qin, Christian M Reidys, and Peter F Stadler. Partition function and base pairing probabilities for rna-rna interaction prediction. Bioinformatics, 25(20):2646-2654, 2009. Google Scholar
  22. Anne Joutel, Christophe Corpechot, Anne Ducros, Katayoun Vahedi, Hugues Chabriat, Philippe Mouton, Sonia Alamowitch, Valérie Domenga, Michaelle Cecillion, Emmanuelle Marechal, et al. Notch3 mutations in cerebral autosomal dominant arteriopathy with subcortical infarcts and leukoencephalopathy (CADASIL), a mendelian condition causing stroke and vascular dementia. Annals of the New York Academy of Sciences, 826(1):213-217, 1997. Google Scholar
  23. Yuki Kato, Tatsuya Akutsu, and Hiroyuki Seki. A grammatical approach to rna-rna interaction prediction. Pattern Recognition, 42(4):531-538, 2009. Google Scholar
  24. Stephanie Kehr, Sebastian Bartschat, Peter F Stadler, and Hakim Tafer. Plexy: efficient target prediction for box c/d snornas. Bioinformatics, 27(2):279-280, 2010. Google Scholar
  25. Michael Kertesz, Nicola Iovino, Ulrich Unnerstall, Ulrike Gaul, and Eran Segal. The role of site accessibility in microrna target recognition. Nature genetics, 39(10):1278, 2007. Google Scholar
  26. Azra Krek, Dominic Grün, Matthew N Poy, Rachel Wolf, Lauren Rosenberg, Eric J Epstein, Philip MacMenamin, Isabelle Da Piedade, Kristin C Gunsalus, Markus Stoffel, et al. Combinatorial microrna target predictions. Nature genetics, 37(5):495, 2005. Google Scholar
  27. Jan Krüger and Marc Rehmsmeier. Rnahybrid: microrna target prediction easy, fast and flexible. Nucleic acids research, 34(suppl_2):W451-W454, 2006. Google Scholar
  28. Almin I Lalani, Carissa R Moore, Chang Luo, Benjamin Z Kreider, Yan Liu, Herbert C Morse, and Ping Xie. Myeloid cell TRAF3 regulates immune responses and inhibits inflammation and tumor development in mice. The Journal of Immunology, 194(1):334-348, 2015. Google Scholar
  29. Ronny Lorenz, Stephan H Bernhart, Christian Hoener Zu Siederdissen, Hakim Tafer, Christoph Flamm, Peter F Stadler, and Ivo L Hofacker. Viennarna package 2.0. Algorithms for Molecular Biology, 6(1):26, 2011. Google Scholar
  30. Martin Mann, Patrick R Wright, and Rolf Backofen. Intarna 2.0: enhanced and customizable prediction of rna-rna interactions. Nucleic acids research, 45(W1):W435-W439, 2017. Google Scholar
  31. NR Markham, M Zuker, and JM Keith. Unafold: software for nucleic acid folding and hybridization., pp. 3-31, 2008. Google Scholar
  32. David H Mathews, Jeffrey Sabina, Michael Zuker, and Douglas H Turner. Expanded sequence dependence of thermodynamic parameters improves prediction of rna secondary structure. Journal of molecular biology, 288(5):911-940, 1999. Google Scholar
  33. John S McCaskill. The equilibrium partition function and base pair binding probabilities for rna secondary structure. Biopolymers: Original Research on Biomolecules, 29(6-7):1105-1119, 1990. Google Scholar
  34. Kevin C Miranda, Tien Huynh, Yvonne Tay, Yen-Sin Ang, Wai-Leong Tam, Andrew M Thomson, Bing Lim, and Isidore Rigoutsos. A pattern-based method for the identification of microrna binding sites and their corresponding heteroduplexes. Cell, 126(6):1203-1217, 2006. Google Scholar
  35. Ulrike Mückstein, Hakim Tafer, Jörg Hackermüller, Stephan H Bernhart, Peter F Stadler, and Ivo L Hofacker. Thermodynamics of rna-rna binding. Bioinformatics, 22(10):1177-1182, 2006. Google Scholar
  36. Jin-Wu Nam, Olivia S Rissland, David Koppstein, Cei Abreu-Goodger, Calvin H Jan, Vikram Agarwal, Muhammed A Yildirim, Antony Rodriguez, and David P Bartel. Global analyses of the effect of different cellular contexts on microrna targeting. Molecular cell, 53(6):1031-1043, 2014. Google Scholar
  37. Ruth Nussinov and Ann B Jacobson. Fast algorithm for predicting the secondary structure of single-stranded rna. Proceedings of the National Academy of Sciences, 77(11):6309-6313, 1980. Google Scholar
  38. Ruth Nussinov, George Pieczenik, Jerrold R Griggs, and Daniel J Kleitman. Algorithms for loop matchings. SIAM Journal on Applied mathematics, 35(1):68-82, 1978. Google Scholar
  39. Dmitri D Pervouchine. Iris: intermolecular rna interaction search. Genome Informatics, 15(2):92-101, 2004. Google Scholar
  40. Dmitri D Pervouchine. Iris: intermolecular rna interaction search. Genome Informatics, 15(2):92-101, 2004. Google Scholar
  41. Martin Reczko, Manolis Maragkakis, Panagiotis Alexiou, Ivo Grosse, and Artemis G Hatzigeorgiou. Functional microrna targets in protein coding sequences. Bioinformatics, 28(6):771-776, 2012. Google Scholar
  42. Marc Rehmsmeier, Peter Steffen, Matthias Höchsmann, and Robert Giegerich. Fast and effective prediction of microrna/target duplexes. Rna, 10(10):1507-1517, 2004. Google Scholar
  43. Ángela Riffo-Campos, Ismael Riquelme, and Priscilla Brebi-Mieville. Tools for sequence-based mirna target prediction: what to choose? International journal of molecular sciences, 17(12):1987, 2016. Google Scholar
  44. Elena Rivas and Sean R Eddy. A dynamic programming algorithm for rna structure prediction including pseudoknots. Journal of molecular biology, 285(5):2053-2068, 1999. Google Scholar
  45. Hakim Tafer, Stephanie Kehr, Jana Hertel, Ivo L Hofacker, and Peter F Stadler. Rnasnoop: efficient target prediction for h/aca snornas. Bioinformatics, 26(5):610-616, 2010. Google Scholar
  46. Brian Tjaden. Targetrna: a tool for predicting targets of small rna action in bacteria. Nucleic acids research, 36(suppl_2):W109-W113, 2008. Google Scholar
  47. Shoji Tsuji, Prabhakara V Choudary, Brian M Martin, Suzanne Winfield, John A Barranger, and Edward I Ginns. Nucleotide sequence of cdna containing the complete coding sequence for human lysosomal glucocerebrosidase. Journal of Biological Chemistry, 261(1):50-53, 1986. Google Scholar
  48. Sinan Uğur Umu and Paul P Gardner. A comprehensive benchmark of rna-rna interaction prediction tools for all domains of life. Bioinformatics, 33(7):988-996, 2017. Google Scholar
  49. S Patrick Walton, Gregory N Stephanopoulos, Martin L Yarmush, and Charles M Roth. Thermodynamic and kinetic characterization of antisense oligodeoxynucleotide binding to a structured mrna. Biophysical journal, 82(1):366-377, 2002. Google Scholar
  50. Michael S Waterman and Temple F Smith. Rna secondary structure: A complete mathematical analysis. Mathematical Biosciences, 42(3-4):257-266, 1978. Google Scholar
  51. Anne Wenzel, Erdinç Akbaşli, and Jan Gorodkin. Risearch: fast rna-rna interaction search using a simplified nearest-neighbor energy model. Bioinformatics, 28(21):2738-2746, 2012. Google Scholar
  52. Wenlong Xu, Anthony San Lucas, Zixing Wang, and Yin Liu. Identifying microrna targets in different gene regions. BMC bioinformatics, 15(7):S4, 2014. Google Scholar
  53. Yuanji Zhang. miru: an automated plant mirna target prediction server. Nucleic acids research, 33(suppl_2):W701-W704, 2005. Google Scholar
  54. Michael Zuker and Patrick Stiegler. Optimal computer folding of large rna sequences using thermodynamics and auxiliary information. Nucleic acids research, 9(1):133-148, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact