Format
Sort by
Items per page

Send to

Choose Destination

Search results

Items: 1 to 20 of 43

1.
Bioinformatics. 2018 Jun 1. doi: 10.1093/bioinformatics/bty420. [Epub ahead of print]

Knotty: Efficient and Accurate Prediction of Complex RNA Pseudoknot Structures.

Author information

1
Department of Computer Science, University of Vermont, Burlington, USA.
2
Ingenuity Lab, Department of Chemical and Materials Engineering, University of Alberta, Edmonton, Canada.
3
Department of Electrical and Computer Engineering, Southern Illinois University, Carbondale, USA.
4
Theoretical Biochemistry Group (TBI), Institute for Theoretical Chemistry, University of Vienna, Austria.

Abstract

Motivation:

The computational prediction of RNA secondary structure by free energy minimization has become an important tool in RNA research. However in practice, energy minimization is mostly limited to pseudoknot-free structures or rather simple pseudoknots, not covering many biologically important structures such as kissing hairpins. Algorithms capable of predicting sufficiently complex pseudoknots (for sequences of length n) used to have extreme complexities, e.g. Pknots (Rivas and Eddy, 1999) has O(n6) time and O(n4) space complexity. The algorithm CCJ (Chen et al., 2009) dramatically improves the asymptotic run time for predicting complex pseudoknots (handling almost all relevant pseudoknots, while being slightly less general than Pknots), but this came at the cost of large constant factors in space and time, which strongly limited its practical application (∼200 bases already require 256GB space).

Results:

We present a CCJ-type algorithm, Knotty, that handles the same comprehensive pseudoknot class of structures as CCJ with improved space complexity of Θ(n3 + Z)-due to the applied technique of sparsification, the number of "candidates", Z, appears to grow significantly slower than n4 on our benchmark set (which include pseudoknotted RNAs up to 400 nucleotides). In terms of run time over this benchmark, Knotty clearly outperforms Pknots and the original CCJ implementation, CCJ 1.0; Knotty's space consumption fundamentally improves over CCJ 1.0, being on a par with the space-economic Pknots. By comparing to CCJ 2.0, our unsparsified Knotty variant, we demonstrate the isolated effect of sparsification. Moreover, Knotty employs the state-of-the-art energy model of "HotKnots DP09", which results in superior prediction accuracy over Pknots.

Availability:

Our software is available at https://github.com/HosnaJabbari/Knotty.

Contact:

will@tbi.unvie.ac.at.

Supplementary information:

Supplementary data are available at Bioinformatics online.

2.
Nucleic Acids Res. 2018 Jul 2;46(W1):W25-W29. doi: 10.1093/nar/gky329.

Freiburg RNA tools: a central online resource for RNA-focused research and teaching.

Author information

1
Bioinformatics, Computer Science, University of Freiburg, Georges-Koehler-Allee 106, 79110 Freiburg, Germany.
2
Institute of Molecular Biology (IMB), Ackermannweg 4, 55128 Mainz, Germany.
3
Department of Computer Science, University of Exeter, Exeter EX4 4QF, UK.
4
Coreva Scientific, Kaiser-Joseph-Str 198-200, 79098 Freiburg, Germany.
5
Genetics and Experimental Bioinformatics, University of Freiburg, Schänzlestraße 1, 79104 Freiburg, Germany.
6
Max Planck Institute of Immunobiology and Epigenetics, Stübeweg 51, 79108 Freiburg, Germany.
7
Max Planck Institute of Molecular Cell Biology and Genetics, Dresden, Germany.
8
Max Planck Institute for the Physics of Complex Systems, Dresden, Germany.
9
Department of Haematology, University of Cambridge, Cambridge Biomedical Campus, Long Road, Cambridge CB2 0PT, UK.
10
Department of Human Genetics, The Wellcome Trust Sanger Institute, Hinxton Cambridge CB10 1HH, UK.
11
Genedata AG, Margarethenstrasse 38, 4053 Basel, Switzerland.
12
Theoretical Biochemistry Group, University of Vienna, Währingerstraße 17, 1090 Vienna, Austria.
13
Department of Clinical Research, Clinical Trial Unit, University of Basel Hospital, Schanzenstrasse 55, 4031 Basel, Switzerland.
14
Centre for Biological Signalling Studies (BIOSS), University of Freiburg, Schaenzlestr. 18, 79104 Freiburg, Germany.

Abstract

The Freiburg RNA tools webserver is a well established online resource for RNA-focused research. It provides a unified user interface and comprehensive result visualization for efficient command line tools. The webserver includes RNA-RNA interaction prediction (IntaRNA, CopraRNA, metaMIR), sRNA homology search (GLASSgo), sequence-structure alignments (LocARNA, MARNA, CARNA, ExpaRNA), CRISPR repeat classification (CRISPRmap), sequence design (antaRNA, INFO-RNA, SECISDesign), structure aberration evaluation of point mutations (RaSE), and RNA/protein-family models visualization (CMV), and other methods. Open education resources offer interactive visualizations of RNA structure and RNA-RNA interaction prediction as well as basic and advanced sequence alignment algorithms. The services are freely available at http://rna.informatik.uni-freiburg.de.

3.
BMC Bioinformatics. 2017 Oct 16;18(Suppl 12):424. doi: 10.1186/s12859-017-1823-5.

Tractable RNA-ligand interaction kinetics.

Kühnl F1, Stadler PF1,2,3,4,5,6,7, Will S8,9.

Author information

1
Department of Computer Science and Interdisciplinary Center for Bioinformatics, University Leipzig, Härtelstr. 16-18, Leipzig, D-04107, Germany.
2
MPI for Mathematics in the Sciences, Inselstr. 22, Leipzig, D-04103, Germany.
3
FHI Cell Therapy and Immunology, Perlickstr. 1, Leipzig, D-04103, Germany.
4
Department Theoretical Chemistry, University Vienna, Währingerstr. 17, Wien, A-1090, Austria.
5
Bioinformatics and Computational Biology Research Group, Währingerstr. 17, Wien, A-1090, Austria.
6
RTH, University Copenhagen, Grønnegårdsvej 3, Frederiksberg C, 1870, Denmark.
7
Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM, USA.
8
Department of Computer Science and Interdisciplinary Center for Bioinformatics, University Leipzig, Härtelstr. 16-18, Leipzig, D-04107, Germany. will@bioinf.uni-leipzig.de.
9
Department Theoretical Chemistry, University Vienna, Währingerstr. 17, Wien, A-1090, Austria. will@bioinf.uni-leipzig.de.

Abstract

BACKGROUND:

The binding of small ligands to RNA elements can cause substantial changes in the RNA structure. This constitutes an important, fast-acting mechanism of ligand-controlled transcriptional and translational gene regulation implemented by a wide variety of riboswitches. The associated refolding processes often cannot be explained by thermodynamic effects alone. Instead, they are governed by the kinetics of RNA folding. While the computational analysis of RNA folding can make use of well-established models of the thermodynamics of RNA structures formation, RNA-RNA interaction, and RNA-ligand interaction, kinetic effects pose fundamentally more challenging problems due to the enormous size of the conformation space. The analysis of the combined process of ligand binding and structure formation even for small RNAs is plagued by intractably large state spaces. Moreover, the interaction is concentration-dependent and thus is intrinsically non-linear. This precludes the direct transfer of the strategies previously used for the analysis of RNA folding kinetics.

RESULTS:

In our novel, computationally tractable approach to RNA-ligand kinetics, we overcome the two main difficulties by applying a gradient-based coarse graining to RNA-ligand systems and solving the process in a pseudo-first order approximation. The latter is well-justified for the most common case of ligand excess in RNA-ligand systems. We present the approach rigorously and discuss the parametrization of the model based on empirical data. The method supports the kinetic study of RNA-ligand systems, in particular at different ligand concentrations. As an example, we apply our approach to analyze the concentration dependence of the ligand response of the rationally designed, artificial theophylline riboswitch RS3.

CONCLUSION:

This work demonstrates the tractability of the computational analysis of RNA-ligand interaction. Naturally, the model will profit as more accurate measurements of folding and binding parameters become available. Due to this work, computational analysis is available to support tasks like the design of riboswitches; our analysis of RS3 suggests strong co-transcriptional effects for this riboswitch. The method used in this study is available online, cf. Section "Availability of data and materials".

KEYWORDS:

RNA interaction kinetics; RNA secondary structure prediction; RNA–ligand interaction; Riboswitches

PMID:
29072147
PMCID:
PMC5657077
DOI:
10.1186/s12859-017-1823-5
[Indexed for MEDLINE]
Free PMC Article
Icon for BioMed Central Icon for PubMed Central
4.
Sensors (Basel). 2017 Aug 30;17(9). pii: E1990. doi: 10.3390/s17091990.

Design of Artificial Riboswitches as Biosensors.

Findeiß S1,2,3, Etzel M4, Will S5,6,7, Mörl M7, Stadler PF8,9,10,11,12,13,14.

Author information

1
Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, University Leipzig, Härtelstraße 16-18, 04107 Leipzig, Germany. sven@bioinf.uni-leipzig.de.
2
Faculty of Computer Science, Research Group Bioinformatics and Computational Biology, University of Vienna, Währingerstraße 29, A-1090 Vienna, Austria. sven@bioinf.uni-leipzig.de.
3
Faculty of Chemistry, Department of Theoretical Chemistry, University of Vienna, Währingerstraße 17, A-1090 Vienna, Austria. sven@bioinf.uni-leipzig.de.
4
Institute for Biochemistry, Leipzig University, Brüderstraße 34, 04103 Leipzig, Germany. maja.etzel@uni-leipzig.de.
5
Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, University Leipzig, Härtelstraße 16-18, 04107 Leipzig, Germany. moerl@uni-leipzig.de.
6
Faculty of Chemistry, Department of Theoretical Chemistry, University of Vienna, Währingerstraße 17, A-1090 Vienna, Austria. moerl@uni-leipzig.de.
7
Institute for Biochemistry, Leipzig University, Brüderstraße 34, 04103 Leipzig, Germany. moerl@uni-leipzig.de.
8
Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, University Leipzig, Härtelstraße 16-18, 04107 Leipzig, Germany. studla@bioinf.uni-leipzig.de.
9
Faculty of Chemistry, Department of Theoretical Chemistry, University of Vienna, Währingerstraße 17, A-1090 Vienna, Austria. studla@bioinf.uni-leipzig.de.
10
German Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig, 04103 Leipzig, Germany. studla@bioinf.uni-leipzig.de.
11
Max Planck Institute for Mathematics in the Sciences, Inselstraße 22, 04103 Leipzig, Germany. studla@bioinf.uni-leipzig.de.
12
Fraunhofer Institute for Cell Therapy and Immunology, Perlickstrasse 1, 04103 Leipzig, Germany. studla@bioinf.uni-leipzig.de.
13
Center for RNA in Technology and Health, University of Copenhagen, Grønnegårdsvej 3, 1870 Frederiksberg , Denmark. studla@bioinf.uni-leipzig.de.
14
Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, USA. studla@bioinf.uni-leipzig.de.

Abstract

RNA aptamers readily recognize small organic molecules, polypeptides, as well as other nucleic acids in a highly specific manner. Many such aptamers have evolved as parts of regulatory systems in nature. Experimental selection techniques such as SELEX have been very successful in finding artificial aptamers for a wide variety of natural and synthetic ligands. Changes in structure and/or stability of aptamers upon ligand binding can propagate through larger RNA constructs and cause specific structural changes at distal positions. In turn, these may affect transcription, translation, splicing, or binding events. The RNA secondary structure model realistically describes both thermodynamic and kinetic aspects of RNA structure formation and refolding at a single, consistent level of modelling. Thus, this framework allows studying the function of natural riboswitches in silico. Moreover, it enables rationally designing artificial switches, combining essentially arbitrary sensors with a broad choice of read-out systems. Eventually, this approach sets the stage for constructing versatile biosensors.

KEYWORDS:

RNA structure; aptamer; folding kinetics; ligand binding; rational design; refolding; thermodynamics

PMID:
28867802
PMCID:
PMC5621056
DOI:
10.3390/s17091990
[Indexed for MEDLINE]
Free PMC Article
Icon for Multidisciplinary Digital Publishing Institute (MDPI) Icon for PubMed Central
5.
Science. 2017 Jul 28;357(6349):372-375. doi: 10.1126/science.aal5066.

Second-scale nuclear spin coherence time of ultracold 23Na40K molecules.

Author information

1
Massachusetts Institute of Technology-Harvard Center for Ultracold Atoms, Research Laboratory of Electronics, Department of Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA.
2
Center for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543, Singapore.
3
Massachusetts Institute of Technology-Harvard Center for Ultracold Atoms, Research Laboratory of Electronics, Department of Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA. zwierlein@mit.edu.

Abstract

Coherence, the stability of the relative phase between quantum states, is central to quantum mechanics and its applications. For ultracold dipolar molecules at sub-microkelvin temperatures, internal states with robust coherence are predicted to offer rich prospects for quantum many-body physics and quantum information processing. We report the observation of stable coherence between nuclear spin states of ultracold fermionic sodium-potassium (NaK) molecules in the singlet rovibrational ground state. Ramsey spectroscopy reveals coherence times on the scale of 1 second; this enables high-resolution spectroscopy of the molecular gas. Collisional shifts are shown to be absent down to the 100-millihertz level. This work opens the door to the use of molecules as a versatile quantum memory and for precision measurements on dipolar quantum matter.

6.
J Biotechnol. 2017 Nov 10;261:97-104. doi: 10.1016/j.jbiotec.2017.07.007. Epub 2017 Jul 8.

Recent advances in RNA folding.

Author information

1
Bioinformatics Group, Department of Computer Science; and Interdisciplinary Center for Bioinformatics, University of Leipzig, Härtelstraße 16-18, D-04107 Leipzig, Germany.
2
Institute for Theoretical Chemistry, University of Vienna, Währingerstraße 17, A-1090 Wien, Austria.
3
Bioinformatics, University of Freiburg, Georges-Köhler-Allee 106, 79110 Freiburg, Germany.
4
Bioinformatics Group, Department of Computer Science; and Interdisciplinary Center for Bioinformatics, University of Leipzig, Härtelstraße 16-18, D-04107 Leipzig, Germany; Institute for Theoretical Chemistry, University of Vienna, Währingerstraße 17, A-1090 Wien, Austria; RNomics Group, Fraunhofer Institute for Cell Therapy and Immunology, Perlickstraße 1, 04103, Leipzig, Germany; Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501, USA. Electronic address: studla@bioinf.uni-leipzig.de.

Abstract

In the realm of nucleic acid structures, secondary structure forms a conceptually important intermediate level of description and explains the dominating part of the free energy of structure formation. Secondary structures are well conserved over evolutionary time-scales and for many classes of RNAs evolve slower than the underlying primary sequences. Given the close link between structure and function, secondary structure is routinely used as a basis to explain experimental findings. Recent technological advances, finally, have made it possible to assay secondary structure directly using high throughput methods. From a computational biology point of view, secondary structures have a special role because they can be computed efficiently using exact dynamic programming algorithms. In this contribution we provide a short overview of RNA folding algorithms, recent additions and variations and address methods to align, compare, and cluster RNA structures, followed by a tabular summary of the most important software suites in the fields.

KEYWORDS:

RNA analysis; RNA constraint folding; RNA interactions; RNA secondary structure; RNA secondary structure comparison

PMID:
28690134
DOI:
10.1016/j.jbiotec.2017.07.007
[Indexed for MEDLINE]
Free full text
Icon for Elsevier Science
7.
Nucleic Acids Res. 2017 Jul 3;45(W1):W560-W566. doi: 10.1093/nar/gkx409.

The RNA workbench: best practices for RNA and high-throughput sequencing bioinformatics in Galaxy.

Author information

1
Bioinformatics Group, Department of Computer Science, University of Freiburg, Georges-Koehler-Allee 106, D-79110 Freiburg, Germany.
2
Center for Biological Systems Analysis (ZBSA), University of Freiburg, Habsburgerstr. 49, D-79104 Freiburg, Germany.
3
Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, University of Leipzig, Härtelstr. 16-18, D-04107 Leipzig, Germany.
4
Berlin Institute for Medical Systems Biology, Max-Delbrück Center for Molecular Medicine, Robert-Rössle-Str. 10, D-13125, Berlin, Germany.
5
Institute for Theoretical Chemistry, University of Vienna, Währingerstrasse 17, A-1090 Vienna, Austria.
6
Department of Systems Biology and Bioinformatics, University of Rostock, Ulmenstr. 69, D-18051 Rostock, Germany.
7
Genetics and Experimental Bioinformatics, Faculty of Biology, University of Freiburg, Schänzlestr. 1, D-79104 Freiburg, Germany.
8
Department of Urology, Erasmus University Medical Center, Wytemaweg 80, 3015 CN Rotterdam, Netherlands.
9
Departments of Biology and Computer Science, Humboldt University, Unter den Linden 6, D-10099 Berlin.
10
Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, D-04103 Leipzig, Germany.
11
Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501, USA.
12
BIOSS Centre for Biological Signaling Studies, University of Freiburg, Schänzlestr. 18, D-79104 Freiburg, Germany.

Abstract

RNA-based regulation has become a major research topic in molecular biology. The analysis of epigenetic and expression data is therefore incomplete if RNA-based regulation is not taken into account. Thus, it is increasingly important but not yet standard to combine RNA-centric data and analysis tools with other types of experimental data such as RNA-seq or ChIP-seq. Here, we present the RNA workbench, a comprehensive set of analysis tools and consolidated workflows that enable the researcher to combine these two worlds. Based on the Galaxy framework the workbench guarantees simple access, easy extension, flexible adaption to personal and security needs, and sophisticated analyses that are independent of command-line knowledge. Currently, it includes more than 50 bioinformatics tools that are dedicated to different research areas of RNA biology including RNA structure analysis, RNA alignment, RNA annotation, RNA-protein interaction, ribosome profiling, RNA-seq analysis and RNA target prediction. The workbench is developed and maintained by experts in RNA bioinformatics and the Galaxy framework. Together with the growing community evolving around this workbench, we are committed to keep the workbench up-to-date for future standards and needs, providing researchers with a reliable and robust framework for RNA data analysis.

AVAILABILITY:

The RNA workbench is available at https://github.com/bgruening/galaxy-rna-workbench.

8.
Nucleic Acids Res. 2017 Apr 20;45(7):4108-4119. doi: 10.1093/nar/gkw1267.

Applicability of a computational design approach for synthetic riboswitches.

Author information

1
Leipzig University, Institute for Biochemistry, 04103 Leipzig, Germany.
2
University of Vienna, Research Group Bioinformatics and Computational Biology, Faculty of Computer Science, A-1090 Vienna, Austria.
3
University of Vienna, Institute for Theoretical Chemistry, A-1090 Vienna, Austria.
4
Leipzig University, Bioinformatics Group, Department of Computer Science and Interdisciplinary Center for Bioinformatics, 04107 Leipzig, Germany.
5
Max Planck Institute for Mathematics in the Science, 04103 Leipzig, Germany.
6
Fraunhofer Institute for Cell Therapy and Immunology, 04103 Leipzig, Germany.
7
Santa Fe Institute, Santa Fe NM 87501, USA.

Abstract

Riboswitches have gained attention as tools for synthetic biology, since they enable researchers to reprogram cells to sense and respond to exogenous molecules. In vitro evolutionary approaches produced numerous RNA aptamers that bind such small ligands, but their conversion into functional riboswitches remains difficult. We previously developed a computational approach for the design of synthetic theophylline riboswitches based on secondary structure prediction. These riboswitches have been constructed to regulate ligand-dependent transcription termination in Escherichia coli. Here, we test the usability of this design strategy by applying the approach to tetracycline and streptomycin aptamers. The resulting tetracycline riboswitches exhibit robust regulatory properties in vivo. Tandem fusions of these riboswitches with theophylline riboswitches represent logic gates responding to two different input signals. In contrast, the conversion of the streptomycin aptamer into functional riboswitches appears to be difficult. Investigations of the underlying aptamer secondary structure revealed differences between in silico prediction and structure probing. We conclude that only aptamers adopting the minimal free energy (MFE) structure are suitable targets for construction of synthetic riboswitches with design approaches based on equilibrium thermodynamics of RNA structures. Further improvements in the design strategy are required to implement aptamer structures not corresponding to the calculated MFE state.

PMID:
27994029
PMCID:
PMC5397205
DOI:
10.1093/nar/gkw1267
[Indexed for MEDLINE]
Free PMC Article
Icon for Silverchair Information Systems Icon for PubMed Central
9.
Phys Rev Lett. 2016 Jun 3;116(22):225306. doi: 10.1103/PhysRevLett.116.225306. Epub 2016 Jun 3.

Coherent Microwave Control of Ultracold ^{23}Na^{40}K Molecules.

Author information

1
MIT-Harvard Center for Ultracold Atoms, Research Laboratory of Electronics, and Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA.
2
Center for Quantum Technologies, National University of Singapore, 3 Science Drive 2, 117543, Singapore.

Abstract

We demonstrate coherent microwave control of rotational and hyperfine states of trapped, ultracold, and chemically stable ^{23}Na^{40}K molecules. Starting with all molecules in the absolute rovibrational and hyperfine ground state, we study rotational transitions in combined magnetic and electric fields and explain the rich hyperfine structure. Following the transfer of the entire molecular ensemble into a single hyperfine level of the first rotationally excited state, J=1, we observe lifetimes of more than 3 s, comparable to those in the rovibrational ground state, J=0. Long-lived ensembles and full quantum state control are prerequisites for the use of ultracold molecules in quantum simulation, precision measurements, and quantum information processing.

10.
Proc Natl Acad Sci U S A. 2016 Jun 28;113(26):7237-42. doi: 10.1073/pnas.1523004113. Epub 2016 Jun 13.

Temperature-responsive in vitro RNA structurome of Yersinia pseudotuberculosis.

Author information

1
Department of Microbial Biology, Ruhr University Bochum, 44801 Bochum, Germany;
2
Department of Molecular Infection Biology, Helmholtz Centre for Infection Research, 38124 Braunschweig, Germany;
3
Department of Computer Science, University of Leipzig, 04107 Leipzig, Germany; Interdisciplinary Center for Bioinformatics, University of Leipzig, 04107 Leipzig, Germany;
4
Department of Computer Science, University of Leipzig, 04107 Leipzig, Germany; Interdisciplinary Center for Bioinformatics, University of Leipzig, 04107 Leipzig, Germany; Max Planck Institute Mathematics in the Sciences, 04103 Leipzig, Germany; Santa Fe Institute, Santa Fe, NM 87501; Fraunhofer Institute Cell Therapy and Immunology, 04103 Leipzig, Germany.
5
Department of Microbial Biology, Ruhr University Bochum, 44801 Bochum, Germany; franz.narberhaus@rub.de.

Abstract

RNA structures are fundamentally important for RNA function. Dynamic, condition-dependent structural changes are able to modulate gene expression as shown for riboswitches and RNA thermometers. By parallel analysis of RNA structures, we mapped the RNA structurome of Yersinia pseudotuberculosis at three different temperatures. This human pathogen is exquisitely responsive to host body temperature (37 °C), which induces a major metabolic transition. Our analysis profiles the structure of more than 1,750 RNAs at 25 °C, 37 °C, and 42 °C. Average mRNAs tend to be unstructured around the ribosome binding site. We searched for 5'-UTRs that are folded at low temperature and identified novel thermoresponsive RNA structures from diverse gene categories. The regulatory potential of 16 candidates was validated. In summary, we present a dynamic bacterial RNA structurome and find that the expression of virulence-relevant functions in Y. pseudotuberculosis and reprogramming of its metabolism in response to temperature is associated with a restructuring of numerous mRNAs.

KEYWORDS:

RNA structure; RNA thermometer; temperature; translational control; virulence

PMID:
27298343
PMCID:
PMC4932938
DOI:
10.1073/pnas.1523004113
[Indexed for MEDLINE]
Free PMC Article
Icon for HighWire Icon for PubMed Central
11.
Algorithms Mol Biol. 2016 Apr 23;11:7. doi: 10.1186/s13015-016-0071-y. eCollection 2016.

Sparse RNA folding revisited: space-efficient minimum free energy structure prediction.

Author information

1
Bioinformatics/IZBI, University Leipzig, Härtelstrasse 16-18, Leipzig, Germany.
2
Ingenuity Lab, 11421 Saskatchewan Drive NW, Edmonton, Canada ; National Institute for Nanotechnology, 11421 Saskatchewan Drive NW, Edmonton, Canada ; Department of Chemical and Materials Engineering, University of Alberta, Edmonton, Canada.

Abstract

BACKGROUND:

RNA secondary structure prediction by energy minimization is the central computational tool for the analysis of structural non-coding RNAs and their interactions. Sparsification has been successfully applied to improve the time efficiency of various structure prediction algorithms while guaranteeing the same result; however, for many such folding problems, space efficiency is of even greater concern, particularly for long RNA sequences. So far, space-efficient sparsified RNA folding with fold reconstruction was solved only for simple base-pair-based pseudo-energy models.

RESULTS:

Here, we revisit the problem of space-efficient free energy minimization. Whereas the space-efficient minimization of the free energy has been sketched before, the reconstruction of the optimum structure has not even been discussed. We show that this reconstruction is not possible in trivial extension of the method for simple energy models. Then, we present the time- and space-efficient sparsified free energy minimization algorithm SparseMFEFold that guarantees MFE structure prediction. In particular, this novel algorithm provides efficient fold reconstruction based on dynamically garbage-collected trace arrows. The complexity of our algorithm depends on two parameters, the number of candidates Z and the number of trace arrows T; both are bounded by [Formula: see text], but are typically much smaller. The time complexity of RNA folding is reduced from [Formula: see text] to [Formula: see text]; the space complexity, from [Formula: see text] to [Formula: see text]. Our empirical results show more than 80 % space savings over RNAfold [Vienna RNA package] on the long RNAs from the RNA STRAND database (≥2500 bases).

CONCLUSIONS:

The presented technique is intentionally generalizable to complex prediction algorithms; due to their high space demands, algorithms like pseudoknot prediction and RNA-RNA-interaction prediction are expected to profit even stronger than "standard" MFE folding. SparseMFEFold is free software, available at http://www.bioinf.uni-leipzig.de/~will/Software/SparseMFEFold.

KEYWORDS:

Pseudoknot-free RNA folding; RNA secondary structure prediction; Space efficient sparsification

Publication type

Publication type

12.
Phys Rev Lett. 2015 May 22;114(20):205302. Epub 2015 May 18.

Ultracold Dipolar Gas of Fermionic 23Na40 K Molecules in Their Absolute Ground State.

Author information

1
MIT-Harvard Center for Ultracold Atoms, Research Laboratory of Electronics, and Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA.

Abstract

We report on the creation of an ultracold dipolar gas of fermionic 23Na40 K molecules in their absolute rovibrational and hyperfine ground state. Starting from weakly bound Feshbach molecules, we demonstrate hyperfine resolved two-photon transfer into the singlet X 1Σ+|v=0,J=0⟩ ground state, coherently bridging a binding energy difference of 0.65 eV via stimulated rapid adiabatic passage. The spin-polarized, nearly quantum degenerate molecular gas displays a lifetime longer than 2.5 s, highlighting NaK's stability against two-body chemical reactions. A homogeneous electric field is applied to induce a dipole moment of up to 0.8 D. With these advances, the exploration of many-body physics with strongly dipolar Fermi gases of 23Na40K molecules is within experimental reach.

13.
Bioinformatics. 2015 Aug 1;31(15):2489-96. doi: 10.1093/bioinformatics/btv185. Epub 2015 Apr 2.

SPARSE: quadratic time simultaneous alignment and folding of RNAs without sequence-based heuristics.

Author information

1
Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany, Bioinformatics, Department of Computer Science, University of Leipzig, Leipzig, Germany.
2
Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany.
3
Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany, Centre for Biological Systems Analysis (ZBSA), University of Freiburg, Freiburg, Germany, Centre for Non-coding RNA in Technology and Health, University of Copenhagen, Copenhagen, Denmark and Centre for Biological Signalling Studies (BIOSS), University of Freiburg, Freiburg, Germany.

Abstract

MOTIVATION:

RNA-Seq experiments have revealed a multitude of novel ncRNAs. The gold standard for their analysis based on simultaneous alignment and folding suffers from extreme time complexity of [Formula: see text]. Subsequently, numerous faster 'Sankoff-style' approaches have been suggested. Commonly, the performance of such methods relies on sequence-based heuristics that restrict the search space to optimal or near-optimal sequence alignments; however, the accuracy of sequence-based methods breaks down for RNAs with sequence identities below 60%. Alignment approaches like LocARNA that do not require sequence-based heuristics, have been limited to high complexity ([Formula: see text] quartic time).

RESULTS:

Breaking this barrier, we introduce the novel Sankoff-style algorithm 'sparsified prediction and alignment of RNAs based on their structure ensembles (SPARSE)', which runs in quadratic time without sequence-based heuristics. To achieve this low complexity, on par with sequence alignment algorithms, SPARSE features strong sparsification based on structural properties of the RNA ensembles. Following PMcomp, SPARSE gains further speed-up from lightweight energy computation. Although all existing lightweight Sankoff-style methods restrict Sankoff's original model by disallowing loop deletions and insertions, SPARSE transfers the Sankoff algorithm to the lightweight energy model completely for the first time. Compared with LocARNA, SPARSE achieves similar alignment and better folding quality in significantly less time (speedup: 3.7). At similar run-time, it aligns low sequence identity instances substantially more accurate than RAF, which uses sequence-based heuristics.

PMID:
25838465
PMCID:
PMC4514930
DOI:
10.1093/bioinformatics/btv185
[Indexed for MEDLINE]
Free PMC Article
Icon for Silverchair Information Systems Icon for PubMed Central
14.
Nat Commun. 2015 Jan 27;6:6009. doi: 10.1038/ncomms7009.

Observation of coherent quench dynamics in a metallic many-body state of fermionic atoms.

Author information

1
1] Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA [2] Institut für Physik, Johannes Gutenberg-Universität, 55099 Mainz, Germany.
2
Department of Physics, The Pennsylvania State University, University Park, Pennsylvania 16802, USA.

Abstract

Quantum simulation with ultracold atoms has become a powerful technique to gain insight into interacting many-body systems. In particular, the possibility to study nonequilibrium dynamics offers a unique pathway to understand correlations and excitations in strongly interacting quantum matter. So far, coherent nonequilibrium dynamics has exclusively been observed in ultracold many-body systems of bosonic atoms. Here we report on the observation of coherent quench dynamics of fermionic atoms. A metallic state of ultracold spin-polarized fermions is prepared along with a Bose-Einstein condensate in a shallow three-dimensional optical lattice. After a quench that suppresses tunnelling between lattice sites for both the fermions and the bosons, we observe long-lived coherent oscillations in the fermionic momentum distribution, with a period that is determined solely by the Fermi-Bose interaction energy. Our results show that coherent quench dynamics can serve as a sensitive probe for correlations in delocalized fermionic quantum states and for quantum metrology.

15.
BMC Bioinformatics. 2014 Dec 31;15:404. doi: 10.1186/s12859-014-0404-0.

ExpaRNA-P: simultaneous exact pattern matching and folding of RNAs.

Author information

1
Bioinformatics, Institute of Computer Science, University of Freiburg, Freiburg, Germany. schmiedc@informatik.uni-freiburg.de.
2
Bioinformatics, Institute of Computer Science, University of Freiburg, Freiburg, Germany. mamo181@googlemail.com.
3
Max Planck Institute of Immunobiology and Epigenetics, Stuebeweg 51, Freiburg, 79108, Germany. heyne@informatik.uni-freiburg.de.
4
Department of Computer Science, University of Haifa, Mount Carmel, Haifa, Israel. mika.amit2@gmail.com.
5
Department of Computer Science, University of Haifa, Mount Carmel, Haifa, Israel. landau@univ.haifa.ac.il.
6
Department of Computer Science and Engineering, NYU-Poly, Brooklyn, NY, USA. landau@univ.haifa.ac.il.
7
Bioinformatics, Institute of Computer Science, University of Freiburg, Freiburg, Germany. backofen@informatik.uni-freiburg.de.
8
Center for Biological Signaling Studies (BIOSS), University of Freiburg, Freiburg, Germany. backofen@informatik.uni-freiburg.de.
9
Centre for Biological Systems Analysis (ZBSA), University of Freiburg, Freiburg, Germany. backofen@informatik.uni-freiburg.de.
10
Center for non-coding RNA in Technology and Health, University of Copenhagen, Grønnegårdsvej 3, Frederiksberg C, DK-1870, Denmark. backofen@informatik.uni-freiburg.de.
11
Bioinformatics, Institute of Computer Science, University of Freiburg, Freiburg, Germany. swill@csail.mit.edu.
12
Bioinformatics, Department of Computer Science, University of Leipzig, Leipzig, Germany. swill@csail.mit.edu.

Abstract

BACKGROUND:

Identifying sequence-structure motifs common to two RNAs can speed up the comparison of structural RNAs substantially. The core algorithm of the existent approach ExpaRNA solves this problem for a priori known input structures. However, such structures are rarely known; moreover, predicting them computationally is no rescue, since single sequence structure prediction is highly unreliable.

RESULTS:

The novel algorithm ExpaRNA-P computes exactly matching sequence-structure motifs in entire Boltzmann-distributed structure ensembles of two RNAs; thereby we match and fold RNAs simultaneously, analogous to the well-known "simultaneous alignment and folding" of RNAs. While this implies much higher flexibility compared to ExpaRNA, ExpaRNA-P has the same very low complexity (quadratic in time and space), which is enabled by its novel structure ensemble-based sparsification. Furthermore, we devise a generalized chaining algorithm to compute compatible subsets of ExpaRNA-P's sequence-structure motifs. Resulting in the very fast RNA alignment approach ExpLoc-P, we utilize the best chain as anchor constraints for the sequence-structure alignment tool LocARNA. ExpLoc-P is benchmarked in several variants and versus state-of-the-art approaches. In particular, we formally introduce and evaluate strict and relaxed variants of the problem; the latter makes the approach sensitive to compensatory mutations. Across a benchmark set of typical non-coding RNAs, ExpLoc-P has similar accuracy to LocARNA but is four times faster (in both variants), while it achieves a speed-up over 30-fold for the longest benchmark sequences (≈400nt). Finally, different ExpLoc-P variants enable tailoring of the method to specific application scenarios. ExpaRNA-P and ExpLoc-P are distributed as part of the LocARNA package. The source code is freely available at http://www.bioinf.uni-freiburg.de/Software/ExpaRNA-P .

CONCLUSIONS:

ExpaRNA-P's novel ensemble-based sparsification reduces its complexity to quadratic time and space. Thereby, ExpaRNA-P significantly speeds up sequence-structure alignment while maintaining the alignment quality. Different ExpaRNA-P variants support a wide range of applications.

PMID:
25551362
PMCID:
PMC4302096
DOI:
10.1186/s12859-014-0404-0
[Indexed for MEDLINE]
Free PMC Article
Icon for BioMed Central Icon for PubMed Central
16.
J Comput Biol. 2014 Jul;21(7):477-91. doi: 10.1089/cmb.2013.0163. Epub 2014 Apr 25.

Simultaneous alignment and folding of protein sequences.

Author information

1
1 School of Computer Science, McGill University , Montreal, Canada .

Abstract

Accurate comparative analysis tools for low-homology proteins remains a difficult challenge in computational biology, especially sequence alignment and consensus folding problems. We present partiFold-Align, the first algorithm for simultaneous alignment and consensus folding of unaligned protein sequences; the algorithm's complexity is polynomial in time and space. Algorithmically, partiFold-Align exploits sparsity in the set of super-secondary structure pairings and alignment candidates to achieve an effectively cubic running time for simultaneous pairwise alignment and folding. We demonstrate the efficacy of these techniques on transmembrane β-barrel proteins, an important yet difficult class of proteins with few known three-dimensional structures. Testing against structurally derived sequence alignments, partiFold-Align significantly outperforms state-of-the-art pairwise and multiple sequence alignment tools in the most difficult low-sequence homology case. It also improves secondary structure prediction where current approaches fail. Importantly, partiFold-Align requires no prior training. These general techniques are widely applicable to many more protein families (partiFold-Align is available at http://partifold.csail.mit.edu/ ).

PMID:
24766258
PMCID:
PMC4082353
DOI:
10.1089/cmb.2013.0163
[Indexed for MEDLINE]
Free PMC Article
Icon for PubMed Central
17.
IEEE/ACM Trans Comput Biol Bioinform. 2014 Jan-Feb;11(1):219-30. doi: 10.1109/TCBB.2013.2297113.

Local Exact Pattern Matching for Non-Fixed RNA Structures.

Abstract

Detecting local common sequence-structure regions of RNAs is a biologically important problem. Detecting such regions allows biologists to identify functionally relevant similarities between the inspected molecules. We developed dynamic programming algorithms for finding common structure-sequence patterns between two RNAs. The RNAs are given by their sequence and a set of potential base pairs with associated probabilities. In contrast to prior work on local pattern matching of RNAs, we support the breaking of arcs. This allows us to add flexibility over matching only fixed structures; potentially matching only a similar subset of specified base pairs. We present an O(n(3)) algorithm for local exact pattern matching between two nested RNAs, and an O(n(3) log n) algorithm for one nested RNA and one bounded-unlimited RNA. In addition, an algorithm for approximate pattern matching is introduced that for two given nested RNAs and a number k, finds the maximal local pattern matching score between the two RNAs with at most k mismatches in O(n(3)k(2)) time. Finally, we present an O(n(3)) algorithm for finding the most similar subforest between two nested RNAs.

PMID:
26355520
DOI:
10.1109/TCBB.2013.2297113
[Indexed for MEDLINE]
Icon for IEEE Engineering in Medicine and Biology Society
18.
Nucleic Acids Res. 2013 Sep;41(17):8034-44. doi: 10.1093/nar/gkt606. Epub 2013 Jul 17.

CRISPRmap: an automated classification of repeat conservation in prokaryotic adaptive immune systems.

Author information

1
Bioinformatics Group, Department of Computer Science, Albert-Ludwigs-University Freiburg, Georges-Köhler-Allee 106, 79110 Freiburg, Germany, ZBSA Centre for Biological Systems Analysis, Albert-Ludwigs-University Freiburg, Habsburgerstr. 49, 79104 Freiburg, Germany, BIOSS Centre for Biological Signalling Studies, Cluster of Excellence, Albert-Ludwigs-University Freiburg, Germany and Center for non-coding RNA in Technology and Health, University of Copenhagen, Gronnegardsvej 3, DK-1870 Frederiksberg C, Denmark.

Abstract

Central to Clustered Regularly Interspaced Short Palindromic Repeat (CRISPR)-Cas systems are repeated RNA sequences that serve as Cas-protein-binding templates. Classification is based on the architectural composition of associated Cas proteins, considering repeat evolution is essential to complete the picture. We compiled the largest data set of CRISPRs to date, performed comprehensive, independent clustering analyses and identified a novel set of 40 conserved sequence families and 33 potential structure motifs for Cas-endoribonucleases with some distinct conservation patterns. Evolutionary relationships are presented as a hierarchical map of sequence and structure similarities for both a quick and detailed insight into the diversity of CRISPR-Cas systems. In a comparison with Cas-subtypes, I-C, I-E, I-F and type II were strongly coupled and the remaining type I and type III subtypes were loosely coupled to repeat and Cas1 evolution, respectively. Subtypes with a strong link to CRISPR evolution were almost exclusive to bacteria; nevertheless, we identified rare examples of potential horizontal transfer of I-C and I-E systems into archaeal organisms. Our easy-to-use web server provides an automated assignment of newly sequenced CRISPRs to our classification system and enables more informed choices on future hypotheses in CRISPR-Cas research: http://rna.informatik.uni-freiburg.de/CRISPRmap.

PMID:
23863837
PMCID:
PMC3783184
DOI:
10.1093/nar/gkt606
[Indexed for MEDLINE]
Free PMC Article
Icon for Silverchair Information Systems Icon for PubMed Central
19.
Algorithms Mol Biol. 2013 Apr 20;8:14. doi: 10.1186/1748-7188-8-14. eCollection 2013.

LocARNAscan: Incorporating thermodynamic stability in sequence and structure-based RNA homology search.

Author information

1
Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, University of Leipzig, Härtelstraße 16 -18, Leipzig D-04107, Germany.
2
Bioinformatics Group, Department of Computer Science, Albert-Ludwigs-Universität Freiburg, Georges-Köhler-Allee 106, Freiburg D-79110, Germany.
3
Genetics Group, Max Planck Institute for Evolutionary Anthropology, Deutscher Platz 6, Leipzig D-04104, Germany.
4
RNomics Group, Fraunhofer Institute for Cell Therapy and Immunology, Perlickstraße 1, Leipzig D-04103, Germany.
5
Max Planck Institute for Mathematics in the Sciences, Inselstraße 22, Leipzig D-04103, Germany.
6
Center for non-coding RNA in Technology and Health, University of Copenhagen, Grønnegårdsvej 3, Frederiksberg C DK-1870, Denmark.
7
Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501, USA.
8
Young Investigators Group Bioinformatics and Transcriptomics, Department Proteomics Helmholtz Centre for Environmental Research - UFZ, Permoserstraße 15, Leipzig D-04318, Germany.
#
Contributed equally

Abstract

BACKGROUND:

The search for distant homologs has become an import issue in genome annotation. A particular difficulty is posed by divergent homologs that have lost recognizable sequence similarity. This same problem also arises in the recognition of novel members of large classes of RNAs such as snoRNAs or microRNAs that consist of families unrelated by common descent. Current homology search tools for structured RNAs are either based entirely on sequence similarity (such as blast or hmmer) or combine sequence and secondary structure. The most prominent example of the latter class of tools is Infernal. Alternatives are descriptor-based methods. In most practical applications published to-date, however, the information contained in covariance models or manually prescribed search patterns is dominated by sequence information. Here we ask two related questions: (1) Is secondary structure alone informative for homology search and the detection of novel members of RNA classes? (2) To what extent is the thermodynamic propensity of the target sequence to fold into the correct secondary structure helpful for this task?

RESULTS:

Sequence-structure alignment can be used as an alternative search strategy. In this scenario, the query consists of a base pairing probability matrix, which can be derived either from a single sequence or from a multiple alignment representing a set of known representatives. Sequence information can be optionally added to the query. The target sequence is pre-processed to obtain local base pairing probabilities. As a search engine we devised a semi-global scanning variant of LocARNA's algorithm for sequence-structure alignment. The LocARNAscan tool is optimized for speed and low memory consumption. In benchmarking experiments on artificial data we observe that the inclusion of thermodynamic stability is helpful, albeit only in a regime of extremely low sequence information in the query. We observe, furthermore, that the sensitivity is bounded in particular by the limited accuracy of the predicted local structures of the target sequence.

CONCLUSIONS:

Although we demonstrate that a purely structure-based homology search is feasible in principle, it is unlikely to outperform tools such as Infernal in most application scenarios, where a substantial amount of sequence information is typically available. The LocARNAscan approach will profit, however, from high throughput methods to determine RNA secondary structure. In transcriptome-wide applications, such methods will provide accurate structure annotations on the target side.

AVAILABILITY:

Source code of the free software LocARNAscan 1.0 and supplementary data are available at http://www.bioinf.uni-leipzig.de/Software/LocARNAscan.

20.
Genome Res. 2013 Jun;23(6):1018-27. doi: 10.1101/gr.137091.111. Epub 2013 Jan 7.

Structure-based whole-genome realignment reveals many novel noncoding RNAs.

Author information

1
Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA.

Abstract

Recent genome-wide computational screens that search for conservation of RNA secondary structure in whole-genome alignments (WGAs) have predicted thousands of structural noncoding RNAs (ncRNAs). The sensitivity of such approaches, however, is limited, due to their reliance on sequence-based whole-genome aligners, which regularly misalign structural ncRNAs. This suggests that many more structural ncRNAs may remain undetected. Structure-based alignment, which could increase the sensitivity, has been prohibitive for genome-wide screens due to its extreme computational costs. Breaking this barrier, we present the pipeline REAPR (RE-Alignment for Prediction of structural ncRNA), which efficiently realigns whole genomes based on RNA sequence and structure, thus allowing us to boost the performance of de novo ncRNA predictors, such as RNAz. Key to the pipeline's efficiency is the development of a novel banding technique for multiple RNA alignment. REAPR significantly outperforms the widely used predictors RNAz and EvoFold in genome-wide screens; in direct comparison to the most recent RNAz screen on D. melanogaster, REAPR predicts twice as many high-confidence ncRNA candidates. Moreover, modENCODE RNA-seq experiments confirm a substantial number of its predictions as transcripts. REAPR's advancement of de novo structural characterization of ncRNAs complements the identification of transcripts from rapidly accumulating RNA-seq data.

PMID:
23296921
PMCID:
PMC3668356
DOI:
10.1101/gr.137091.111
[Indexed for MEDLINE]
Free PMC Article
Icon for HighWire Icon for PubMed Central

Supplemental Content

Loading ...
Support Center