1
|
Kühnl F, Stadler PF, Findeiß S. Assessing the Quality of Cotranscriptional Folding Simulations. Methods Mol Biol 2024; 2726:347-376. [PMID: 38780738 DOI: 10.1007/978-1-0716-3519-3_14] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 05/25/2024]
Abstract
Structural changes in RNAs are an important contributor to controlling gene expression not only at the posttranscriptional stage but also during transcription. A subclass of riboswitches and RNA thermometers located in the 5' region of the primary transcript regulates the downstream functional unit - usually an ORF - through premature termination of transcription. Not only such elements occur naturally, but they are also attractive devices in synthetic biology. The possibility to design such riboswitches or RNA thermometers is thus of considerable practical interest. Since these functional RNA elements act already during transcription, it is important to model and understand the dynamics of folding and, in particular, the formation of intermediate structures concurrently with transcription. Cotranscriptional folding simulations are therefore an important step to verify the functionality of design constructs before conducting expensive and labor-intensive wet lab experiments. For RNAs, full-fledged molecular dynamics simulations are far beyond practical reach because of both the size of the molecules and the timescales of interest. Even at the simplified level of secondary structures, further approximations are necessary. The BarMap approach is based on representing the secondary structure landscape for each individual transcription step by a coarse-grained representation that only retains a small set of low-energy local minima and the energy barriers between them. The folding dynamics between two transcriptional elongation steps is modeled as a Markov process on this representation. Maps between pairs of consecutive coarse-grained landscapes make it possible to follow the folding process as it changes in response to transcription elongation. In its original implementation, the BarMap software provides a general framework to investigate RNA folding dynamics on temporally changing landscapes. It is, however, difficult to use in particular for specific scenarios such as cotranscriptional folding. To overcome this limitation, we developed the user-friendly BarMap-QA pipeline described in detail in this contribution. It is illustrated here by an elaborate example that emphasizes the careful monitoring of several quality measures. Using an iterative workflow, a reliable and complete kinetics simulation of a synthetic, transcription-regulating riboswitch is obtained using minimal computational resources. All programs and scripts used in this contribution are free software and available for download as a source distribution for Linux® or as a platform-independent Docker® image including support for Apple macOS® and Microsoft Windows®.
Collapse
Affiliation(s)
- Felix Kühnl
- Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, Leipzig University, Leipzig, Germany
| | - Peter F Stadler
- Bioinformatics Group, Department of Computer Science, Interdisciplinary Center of Bioinformatics, German Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig, Competence Center for Scalable Data Services and Solutions, and Leipzig Research Center for Civilization Diseases, Leipzig University, Leipzig, Germany
- Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany
- Institute for Theoretical Chemistry, University of Vienna, Vienna, Austria
- Facultad de Ciencias, Universidad Nacional de Colombia, Bogotá, D.C., Colombia
- Santa Fe Institute, Santa Fe, NM, USA
| | - Sven Findeiß
- Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, Leipzig University, Leipzig, Germany.
| |
Collapse
|
2
|
Takizawa H, Iwakiri J, Terai G, Asai K. Finding the direct optimal RNA barrier energy and improving pathways with an arbitrary energy model. Bioinformatics 2020; 36:i227-i235. [PMID: 32657400 PMCID: PMC7355307 DOI: 10.1093/bioinformatics/btaa469] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 12/03/2022] Open
Abstract
Motivation RNA folding kinetics plays an important role in the biological functions of RNA molecules. An important goal in the investigation of the kinetic behavior of RNAs is to find the folding pathway with the lowest energy barrier. For this purpose, most of the existing methods use heuristics because the number of possible pathways is huge even if only the shortest (direct) folding pathways are considered. Results In this study, we propose a new method using a best-first search strategy to efficiently compute the exact solution of the minimum barrier energy of direct pathways. Using our method, we can find the exact direct pathways within a Hamming distance of 20, whereas the previous methods even miss the exact short pathways. Moreover, our method can be used to improve the pathways found by existing methods for exploring indirect pathways. Availability and implementation The source code and datasets created and used in this research are available at https://github.com/eukaryo/czno. Supplementary information Supplementary data are available at Bioinformatics online.
Collapse
Affiliation(s)
- Hiroki Takizawa
- Department of Computational Biology and Medical Sciences, Graduate School of Frontier Sciences, University of Tokyo, Tokyo, Chiba 277-8561 Japan
| | - Junichi Iwakiri
- Department of Computational Biology and Medical Sciences, Graduate School of Frontier Sciences, University of Tokyo, Tokyo, Chiba 277-8561 Japan
| | - Goro Terai
- Department of Computational Biology and Medical Sciences, Graduate School of Frontier Sciences, University of Tokyo, Tokyo, Chiba 277-8561 Japan
| | - Kiyoshi Asai
- Department of Computational Biology and Medical Sciences, Graduate School of Frontier Sciences, University of Tokyo, Tokyo, Chiba 277-8561 Japan.,Artificial Intelligence Research Center (AIRC), National Institute of Advanced Science and Technology (AIST), Tokyo135-0064, Japan
| |
Collapse
|
3
|
Takitou S, Taneda A. Ant colony optimization for predicting RNA folding pathways. Comput Biol Chem 2019; 83:107118. [PMID: 31698162 DOI: 10.1016/j.compbiolchem.2019.107118] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/22/2019] [Revised: 06/10/2019] [Accepted: 08/26/2019] [Indexed: 12/30/2022]
Abstract
RNA folding dynamics plays important roles in various functions of RNAs. To date, coarse-grained modeling has been successfully employed to simulate RNA folding dynamics on the energy landscape composed of secondary structures. In such a modeling, the energy barrier height between metastable structures is a key parameter that crucially affects the simulation results. Although a number of approaches ranging from the exact method to heuristic ones are available to predict the barrier heights, developing an efficient heuristic for this purpose is still an algorithmic challenge. We developed a novel RNA folding pathway prediction method, ACOfoldpath, based on Ant Colony Optimization (ACO). ACO is a widely used powerful combinatorial optimization algorithm inspired from the food-seeking behavior of ants. In ACOfoldpath, to accelerate the folding pathway prediction, we reduce the search space by utilizing originally devised structure generation rules. To evaluate the performance of the proposed method, we benchmarked ACOfoldpath on the known nineteen conformational RNA switches. As a result, ACOfoldpath successfully predicted folding pathways better than or comparable to the previous heuristics. The results of RNA folding dynamics simulations and pseudoknotted pathway predictions are also presented.
Collapse
Affiliation(s)
- Seira Takitou
- Course of Electronics and Information Technology, Graduate School of Science and Technology, Hirosaki University, Hirosaki, Aomori 036-8561, Japan
| | - Akito Taneda
- Graduate School of Science and Technology, Hirosaki University, Hirosaki, Aomori 036-8561, Japan.
| |
Collapse
|
4
|
Fukunaga T, Hamada M. Computational approaches for alternative and transient secondary structures of ribonucleic acids. Brief Funct Genomics 2018; 18:182-191. [PMID: 30689706 DOI: 10.1093/bfgp/ely042] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/13/2022] Open
Abstract
Transient and alternative structures of ribonucleic acids (RNAs) play essential roles in various regulatory processes, such as translation regulation in living cells. Because experimental analyses for RNA structures are difficult and time-consuming, computational approaches based on RNA secondary structures are promising. In this article, we review computational methods for detecting and analyzing transient/alternative secondary structures of RNAs, including static approaches based on probabilistic distributions of RNA secondary structures and dynamic approaches such as kinetic folding and folding pathway predictions.
Collapse
|
5
|
Mann M, Kucharík M, Flamm C, Wolfinger MT. Memory-efficient RNA energy landscape exploration. Bioinformatics 2014; 30:2584-91. [PMID: 24833804 PMCID: PMC4155248 DOI: 10.1093/bioinformatics/btu337] [Citation(s) in RCA: 9] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/31/2014] [Revised: 04/25/2014] [Accepted: 05/08/2014] [Indexed: 02/01/2023] Open
Abstract
MOTIVATION Energy landscapes provide a valuable means for studying the folding dynamics of short RNA molecules in detail by modeling all possible structures and their transitions. Higher abstraction levels based on a macro-state decomposition of the landscape enable the study of larger systems; however, they are still restricted by huge memory requirements of exact approaches. RESULTS We present a highly parallelizable local enumeration scheme that enables the computation of exact macro-state transition models with highly reduced memory requirements. The approach is evaluated on RNA secondary structure landscapes using a gradient basin definition for macro-states. Furthermore, we demonstrate the need for exact transition models by comparing two barrier-based approaches, and perform a detailed investigation of gradient basins in RNA energy landscapes. AVAILABILITY AND IMPLEMENTATION Source code is part of the C++ Energy Landscape Library available at http://www.bioinf.uni-freiburg.de/Software/.
Collapse
Affiliation(s)
- Martin Mann
- Bioinformatics Group, Department of Computer Science, University of Freiburg, 79110 Freiburg, Germany, Institute for Theoretical Chemistry, University of Vienna, 1090 Vienna, Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, University of Vienna, Medical University of Vienna, and Department of Biochemistry and Molecular Cell Biology, Max F. Perutz Laboratories, University of Vienna, A-1030 Vienna, Austria
| | - Marcel Kucharík
- Bioinformatics Group, Department of Computer Science, University of Freiburg, 79110 Freiburg, Germany, Institute for Theoretical Chemistry, University of Vienna, 1090 Vienna, Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, University of Vienna, Medical University of Vienna, and Department of Biochemistry and Molecular Cell Biology, Max F. Perutz Laboratories, University of Vienna, A-1030 Vienna, Austria
| | - Christoph Flamm
- Bioinformatics Group, Department of Computer Science, University of Freiburg, 79110 Freiburg, Germany, Institute for Theoretical Chemistry, University of Vienna, 1090 Vienna, Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, University of Vienna, Medical University of Vienna, and Department of Biochemistry and Molecular Cell Biology, Max F. Perutz Laboratories, University of Vienna, A-1030 Vienna, Austria
| | - Michael T Wolfinger
- Bioinformatics Group, Department of Computer Science, University of Freiburg, 79110 Freiburg, Germany, Institute for Theoretical Chemistry, University of Vienna, 1090 Vienna, Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, University of Vienna, Medical University of Vienna, and Department of Biochemistry and Molecular Cell Biology, Max F. Perutz Laboratories, University of Vienna, A-1030 Vienna, Austria Bioinformatics Group, Department of Computer Science, University of Freiburg, 79110 Freiburg, Germany, Institute for Theoretical Chemistry, University of Vienna, 1090 Vienna, Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, University of Vienna, Medical University of Vienna, and Department of Biochemistry and Molecular Cell Biology, Max F. Perutz Laboratories, University of Vienna, A-1030 Vienna, Austria Bioinformatics Group, Department of Computer Science, University of Freiburg, 79110 Freiburg, Germany, Institute for Theoretical Chemistry, University of Vienna, 1090 Vienna, Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, University of Vienna, Medical University of Vienna, and Department of Biochemistry and Molecular Cell Biology, Max F. Perutz Laboratories, University of Vienna, A-1030 Vienna, Austria
| |
Collapse
|
6
|
Huang J, Voß B. Analysing RNA-kinetics based on folding space abstraction. BMC Bioinformatics 2014; 15:60. [PMID: 24575751 PMCID: PMC3974018 DOI: 10.1186/1471-2105-15-60] [Citation(s) in RCA: 10] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/09/2013] [Accepted: 02/24/2014] [Indexed: 11/23/2022] Open
Abstract
BACKGROUND RNA molecules, especially non-coding RNAs, play vital roles in the cell and their biological functions are mostly determined by structural properties. Often, these properties are related to dynamic changes in the structure, as in the case of riboswitches, and thus the analysis of RNA folding kinetics is crucial for their study. Exact approaches to kinetic folding are computationally expensive and, thus, limited to short sequences. In a previous study, we introduced a position-specific abstraction based on helices which we termed helix index shapes (hishapes) and a hishape-based algorithm for near-optimal folding pathway computation, called HiPath. The combination of these approaches provides an abstract view of the folding space that offers information about the global features. RESULTS In this paper we present HiKinetics, an algorithm that can predict RNA folding kinetics for sequences up to several hundred nucleotides long. This algorithm is based on RNAHeliCes, which decomposes the folding space into abstract classes, namely hishapes, and an improved version of HiPath, namely HiPath2, which estimates plausible folding pathways that connect these classes. Furthermore, we analyse the relationship of hishapes to locally optimal structures, the results of which strengthen the use of the hishape abstraction for studying folding kinetics. Finally, we show the application of HiKinetics to the folding kinetics of two well-studied RNAs. CONCLUSIONS HiKinetics can calculate kinetic folding based on a novel hishape decomposition. HiKinetics, together with HiPath2 and RNAHeliCes, is available for download at http://www.cyanolab.de/software/RNAHeliCes.htm.
Collapse
Affiliation(s)
- Jiabin Huang
- Genetics & Experimental Bioinformatics, Faculty of Biology, University of Freiburg, Schänzlestr. 1, 79104, Freiburg, Germany
| | - Björn Voß
- Genetics & Experimental Bioinformatics, Faculty of Biology, University of Freiburg, Schänzlestr. 1, 79104, Freiburg, Germany
| |
Collapse
|
7
|
Senter E, Dotu I, Clote P. RNA folding pathways and kinetics using 2D energy landscapes. J Math Biol 2014; 70:173-96. [PMID: 24515409 DOI: 10.1007/s00285-014-0760-4] [Citation(s) in RCA: 8] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/19/2013] [Revised: 09/26/2013] [Indexed: 11/27/2022]
Abstract
RNA folding pathways play an important role in various biological processes, such as (i) the hok/sok (host-killing/suppression of killing) system in E. coli to check for sufficient plasmid copy number, (ii) the conformational switch in spliced leader (SL) RNA from Leptomonas collosoma, which controls trans splicing of a portion of the '5 exon, and (iii) riboswitches--portions of the 5' untranslated region of messenger RNA that regulate genes by allostery. Since RNA folding pathways are determined by the energy landscape, we describe a novel algorithm, FFTbor2D, which computes the 2D projection of the energy landscape for a given RNA sequence. Given two metastable secondary structures A, B for a given RNA sequence, FFTbor2D computes the Boltzmann probability p(x, y) = Z(x,y)/Z that a secondary structure has base pair distance x from A and distance y from B. Using polynomial interpolationwith the fast Fourier transform,we compute p(x, y) in O(n(5)) time and O(n(2)) space, which is an improvement over an earlier method, which runs in O(n(7)) time and O(n(4)) space. FFTbor2D has potential applications in synthetic biology, where one might wish to design bistable switches having target metastable structures A, B with favorable pathway kinetics. By inverting the transition probability matrix determined from FFTbor2D output, we show that L. collosoma spliced leader RNA has larger mean first passage time from A to B on the 2D energy landscape, than 97.145% of 20,000 sequences, each having metastable structures A, B. Source code and binaries are freely available for download at http://bioinformatics.bc.edu/clotelab/FFTbor2D. The program FFTbor2D is implemented in C++, with optional OpenMP parallelization primitives.
Collapse
Affiliation(s)
- Evan Senter
- Department of Biology, Boston College, Chestnut Hill, MA, 02467, USA
| | | | | |
Collapse
|
8
|
Kirkpatrick B, Hajiaghayi M, Condon A. A new model for approximating RNA folding trajectories and population kinetics. ACTA ACUST UNITED AC 2013. [DOI: 10.1088/1749-4699/6/1/014003] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/12/2022]
|