@incollection{Will-LocARNA-2023,
author = {Will, Sebastian},
title = {{LocARNA 2.0: versatile simultaneous alignment and folding of RNAs}},
booktitle = {RNA Folding - Methods and Protocols},
series = {Methods in Molecular Biology},
publisher = {Humana New York, NY},
editor = {Ronny Lorenz},
note = {To appear},
year = {2023},
url = {https://hal.science/hal-03864352}
}
@incollection{Yao-Infrared-2023,
author = {Yao, Hua-Ting and Ponty, Yann and Will, Sebastian},
title = {{Developing complex RNA design applications in the Infrared framework}},
booktitle = {RNA Folding - Methods and Protocols},
series = {Methods in Molecular Biology},
publisher = {Humana New York, NY},
editor = {Ronny Lorenz},
note = {To appear},
year = {2023},
url = {https://hal.science/hal-03711828}
}
@inproceedings{Gray2023,
author = {Gray, Mateo and Jabbari, Hosna and Will, Sebastian},
title = {{SparseRNAFolD}: Sparse {RNA} pseudoknot-free Folding including Dangles},
booktitle = {Proceedings of WABI 2023},
year = {2023},
note = {To appear},
eprint = {2023.06.05.543808},
doi = {10.1101/2023.06.05.543808}
}
@incollection{Dinot-IJCAI2023,
title = {Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise},
author = {Matthieu Dinot and Benjamin Doerr and Ulysse Hennebelle and Sebastian Will},
booktitle = {Proceedings of the 32nd International Joint Conference on
Artificial Intelligence, {IJCAI'23}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
year = 2023,
note = {To appear},
abstract={In single-objective optimization, it is well known that evolutionary algorithms also without further adjustments can stand a certain amount of noise in the evaluation of the objective function. In contrast, this question is not at all understood for multi-objective optimization. In this work, we conduct the first mathematical runtime analysis of a simple multi-objective evolutionary algorithm (MOEA) on a classic benchmark in the presence of noise in the objective function. We prove that when bit-wise prior noise with rate p <= alpha/n, alpha a suitable constant, is present, the simple evolutionary multi-objective optimizer (SEMO) without any adjustments to cope with noise finds the Pareto front of the OneMinMax benchmark in time O(n^2 log n), just as in the case without noise. Given that the problem here is to arrive at a population consisting of n+1 individuals witnessing the Pareto front, this is a surprisingly strong robustness to noise (comparably simple evolutionary algorithms cannot optimize the single-objective OneMax problem in polynomial time when p = omega(log(n)/n)). Our proofs suggest that the strong robustness of the MOEA stems from its implicit diversity mechanism designed to enable it to compute a population covering the whole Pareto front. Interestingly this result only holds when the objective value of a solution is determined only once and the algorithm from that point on works with this, possibly noisy, objective value. We prove that when all solutions are reevaluated in each iteration, then any noise rate p = omega(log(n)/n^2) leads to a super-polynomial runtime. This is very different from single-objective optimization, where it is generally preferred to reevaluate solutions whenever their fitness is important and where examples are known such that not reevaluating solutions can lead to catastrophic performance losses.}
}
@article{Stadler2022,
author = {Stadler, Peter F. and Will, Sebastian},
title = {{Bi-alignments with affine gaps costs}},
journal = {Algorithms Mol. Biol.},
volume = {17},
number = {1},
pages = {1--13},
year = {2022},
month = {December},
issn = {1748-7188},
publisher = {BioMed Central},
doi = {10.1186/s13015-022-00219-7}
}
@InProceedings{Marchand-WABI2022,
author = {Marchand, Bertrand and Will, Sebastian and Berkemer, Sarah J. and Bulteau, Laurent and Ponty, Yann},
title = {{Automated Design of Dynamic Programming Schemes for RNA Folding with Pseudoknots}},
booktitle = {22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)},
pages = {7:1--7:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-243-3},
ISSN = {1868-8969},
year = {2022},
volume = {242},
editor = {Boucher, Christina and Rahmann, Sven},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17041},
URN = {urn:nbn:de:0030-drops-170414},
doi = {10.4230/LIPIcs.WABI.2022.7},
annote = {Keywords: RNA folding, treewidth, dynamic programming}
}
@article{Wang2021,
author = {Wang, Dehe and Jiang, Ao and Feng, Jiangpeng and Li, Guangnan and Guo, Dong and Sajid, Muhammad and Wu, Kai and Zhang, Qiuhan and Ponty, Yann and Will, Sebastian and Liu, Feiyan and Yu, Xinghai and Li, Shaopeng and Liu, Qianyun and Yang, Xing-Lou and Guo, Ming and Li, Xingqiao and Chen, Mingzhou and Shi, Zheng-Li and Lan, Ke and Chen, Yu and Zhou, Yu},
title = {{The SARS-CoV-2 subgenome landscape and its novel regulatory features}},
journal = {Mol. Cell},
volume = {81},
number = {10},
pages = {2135--2147.e5},
year = {2021},
month = {May},
issn = {1097-2765},
publisher = {Cell Press},
doi = {10.1016/j.molcel.2021.02.036}
}
@article{DeBisschop2021,
author = {De Bisschop, Gr{\'e}goire and Allouche, Delphine and Frezza, Elisa and Masquida, Beno{\^i}t and Ponty, Yann and Will, Sebastian and Sargueil, Bruno},
title = {{Progress toward SHAPE Constrained Computational Prediction of Tertiary Interactions in RNA Structure}},
journal = {Non-Coding RNA},
volume = {7},
number = {4},
pages = {71},
year = {2021},
month = {November},
issn = {2311-553X},
publisher = {Multidisciplinary Digital Publishing Institute},
doi = {10.3390/ncrna7040071}
}
@incollection{Ponty-RNARedPrint-Bookchapter-2021,
author = {Ponty, Yann and Hammer, Stefan and Yao, Hua-Ting and Will, Sebastian},
title = {{Advanced Design of Structural RNAs Using RNARedPrint}},
booktitle = {RNA Bioinformatics},
journal = {SpringerLink},
pages = {1--15},
year = {2021},
isbn = {978-1-0716-1307-8},
publisher = {Springer US},
doi = {10.1007/978-1-0716-1307-8_1},
abstract = {RNA design addresses the need to build novel RNAs, e.g., for biotechnological applications in synthetic biology, equipped with desired functional properties. This chapter describes how to use the software RNARedPrint for the de novo rational design of RNA sequences adopting one or several desired secondary structures. Depending on the application, these structures could represent alternate configurations or kinetic pathways. The software makes such design convenient and sufficiently fast for practical routine, where it even overcomes notorious problems in the application of RNA design, e.g., it maintains realistic GC content. Keywords: RNA design, Kinetic landscapes, Riboswitches}
}
@incollection{Waldl2020,
author = {Waldl, Maria and Will, Sebastian and Wolfinger, Michael T. and Hofacker, Ivo L. and Stadler, Peter F.},
title = {{Bi-alignments as Models of Incongruent Evolution of RNA Sequence and Secondary Structure}},
booktitle = {{Computational Intelligence Methods for Bioinformatics and Biostatistics}},
journal = {SpringerLink},
pages = {159--170},
year = {2020},
month = {December},
isbn = {978-3-030-63061-4},
publisher = {Springer},
address = {Cham, Switzerland},
doi = {10.1007/978-3-030-63061-4_15}
}
@inproceedings{Yao-RNAPOND-RECOMB2021,
author = {Yao, Hua-Ting and Waldisp{\"u}hl, J{\'e}r{\^o}me and Ponty, Yann and Will, Sebastian},
title = {{Taming Disruptive Base Pairs to Reconcile Positive and Negative Structural Design of RNA}},
booktitle = {Proc. of the 25th Annual International Conferences on Computational Molecular Biology (RECOMB'21)},
year = {2021},
url = {https://inria.hal.science/hal-02987566}
}
@Article{Muller_Miladi_Hutter-The_local_dilem-2020,
author = {Muller, Teresa and Miladi, Milad and Hutter, Frank and Hofacker, Ivo and Will, Sebastian and Backofen, Rolf},
title = {The locality dilemma of {Sankoff}-like {RNA} alignments},
journal = {Bioinformatics},
year = {2020},
volume = {36},
number = {Supplement 1},
pages = {i242-i250},
user = {will},
pmid = {32657398},
doi = {10.1093/bioinformatics/btaa431},
issn = {1367-4811},
abstract = {MOTIVATION: Elucidating the functions of non-coding RNAs by homology has been strongly limited due to fundamental computational and modeling issues. While existing simultaneous alignment and folding (SA&F) algorithms successfully align homologous RNAs with precisely known boundaries (global SA&F), the more pressing problem of identifying new classes of homologous RNAs in the genome (local SA&F) is intrinsically more difficult and much less understood. Typically, the length of local alignments is strongly overestimated and alignment boundaries are dramatically mispredicted. We hypothesize that local SA&F approaches are compromised this way due to a score bias, which is caused by the contribution of RNA structure similarity to their overall alignment score. RESULTS: In the light of this hypothesis, we study pairwise local SA&F for the first time systematically-based on a novel local RNA alignment benchmark set and quality measure. First, we vary the relative influence of structure similarity compared to sequence similarity. Putting more emphasis on the structure component leads to overestimating the length of local alignments. This clearly shows the bias of current scores and strongly hints at the structure component as its origin. Second, we study the interplay of several important scoring parameters by learning parameters for local and global SA&F. The divergence of these optimized parameter sets underlines the fundamental obstacles for local SA&F. Third, by introducing a position-wise correction term in local SA&F, we constructively solve its principal issues. AVAILABILITY AND IMPLEMENTATION: The benchmark data, detailed results and scripts are available at https://github.com/BackofenLab/local_alignment. The RNA alignment tool LocARNA, including the modifications proposed in this work, is available at https://github.com/s-will/LocARNA/releases/tag/v2.0.0RC6. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.}
}
@InProceedings{Miladi-Pankov-WABI2019,
author = {Milad Miladi and Martin Raden and Sebastian Will and Rolf Backofen},
title = {Fast and Accurate Structure Probability Estimation for Simultaneous Alignment and Folding of {RNA}s},
booktitle = {19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
pages = {14:1--14:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-123-8},
ISSN = {1868-8969},
year = {2019},
volume = {143},
editor = {Katharina T. Huber and Dan Gusfield},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
doi = {10.4230/LIPIcs.WABI.2019.14},
user = {mmann},
abstract = {Motivation: Simultaneous alignment and folding (SAF) of RNAs is the indispensable gold standard for inferring the structure of non-coding RNAs and their general analysis. The original algorithm, proposed by Sankoff, solves the theoretical problem exactly with a complexity of O(n6) in the full energy model. Over the last two decades, several variants and improvements of the Sankoff algorithm have been proposed to reduce its extreme complexity by proposing simplified energy models or imposing restrictions on the predicted alignments. Results: Here we introduce a novel variant of Sankoff's algorithm that reconciles the simplifications of PMcomp, namely moving from the full energy model to a simpler base pair-based model, with the accuracy of the loop-based full energy model. Instead of estimating pseudo-energies from unconditional base pair probabilities, our model calculates energies from conditional base pair probabilities that allow to accurately capture structure probabilities, which obey a conditional dependency. Supporting modifications with surgical precision, this model gives rise to the fast and highly accurate novel algorithm Pankov (Probabilistic Sankoff-like simultaneous alignment and folding of RNAs inspired by Markov chains). Pankov benefits from the speed-up of excluding unreliable base-pairing without compromising the loop-based free energy model of the Sankoff's algorithm. We show that Pankov outperforms its predecessors LocARNA and SPARSE in folding quality and is faster than LocARNA. Pankov is developed as a branch of the LocARNA package and available at https://github.com/mmiladi/Pankov.}
}
@InProceedings{Waldl-CIBB2019,
author = {Waldl, Maria and Will, Sebastian and Wolfinger, Michael T. and Hofacker, Ivo L. and Stadler, Peter F.},
title = {{Bi-Alignments as Models of Incongruent Evolution of RNA Sequence and Structure}},
booktitle = {Proceedings of CIBB 2019},
year = {2019},
publisher = {Cold Spring Harbor Laboratory},
doi = {10.1101/631606}
}
@InProceedings{Gelhausen-BIONFORMATICS2019,
author = {Rick Gelhausen and Sebastian Will and Ivo Hofacker and Rolf Backofen and Martin Raden},
title = {Constraint Maximal Inter-molecular Helix Lengths within RNA-RNA Interaction Prediction Improves Bacterial sRNA Target Prediction},
booktitle = {Proceedings of the 12th International Joint Conference on Biomedical Engineering Systems and Technologies - Volume 3: BIOINFORMATICS,},
year = {2019},
pages = {131-140},
publisher = {SciTePress},
organization = {INSTICC},
doi = {10.5220/0007689701310140},
isbn = {978-989-758-353-7}
}
@Article{Hammer-BMCBioinf2019,
author = {Hammer, Stefan and Wang, Wei and Will, Sebastian and Ponty, Yann},
title = {Fixed-parameter tractable sampling for {RNA} design with multiple target structures},
journal = {BMC Bioinformatics},
year = {2019},
volume = {20},
number = {1},
pages = {209},
user = {will},
pmid = {31023239},
doi = {10.1186/s12859-019-2784-7},
issn = {1471-2105},
abstract = {BACKGROUND: The design of multi-stable RNA molecules has important applications in biology, medicine, and biotechnology. Synthetic design approaches profit strongly from effective in-silico methods, which substantially reduce the need for costly wet-lab experiments. RESULTS: We devise a novel approach to a central ingredient of most in-silico design methods: the generation of sequences that fold well into multiple target structures. Based on constraint networks, our approach supports generic Boltzmann-weighted sampling, which enables the positive design of RNA sequences with specific free energies (for each of multiple, possibly pseudoknotted, target structures) and GC-content. Moreover, we study general properties of our approach empirically and generate biologically relevant multi-target Boltzmann-weighted designs for an established design benchmark. Our results demonstrate the efficacy and feasibility of the method in practice as well as the benefits of Boltzmann sampling over the previously best multi-target sampling strategy-even for the case of negative design of multi-stable RNAs. Besides empirically studies, we finally justify the algorithmic details due to a fundamental theoretic result about multi-stable RNA design, namely the #P-hardness of the counting of designs. CONCLUSION: introduces a novel, flexible, and effective approach to multi-target RNA design, which promises broad applicability and extensibility. Our free software is available at: https://github.com/yannponty/RNARedPrint Supplementary data are available online.}
}
@Article{Jabbari-BI2018,
author = {Jabbari, Hosna and Wark, Ian and Montemagno, Carlo and Will, Sebastian},
title = {Knotty: efficient and accurate prediction of complex {RNA} pseudoknot structures},
journal = {Bioinformatics},
year = {2018},
volume = {34},
number = {22},
pages = {3849-3856},
user = {will},
pmid = {29868872},
doi = {10.1093/bioinformatics/bty420},
issn = {1367-4811},
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 has O(n6) time and O(n4) space complexity. The algorithm CCJ 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 ( approximately 200 bases already require 256 GB 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 Theta(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 nt). 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 and implementation: Our software is available at https://github.com/HosnaJabbari/Knotty. Supplementary information: Supplementary data are available at Bioinformatics online.}
}
@InProceedings{Hammer-RECOMB18,
author = {Stefan Hammer and Yann Ponty and Wei Wang and Sebastian Will},
title = {Fixed-Parameter Tractable Sampling for RNA Design with Multiple Target Structures},
booktitle = {Proc. of the 22th Annual International Conferences on Computational Molecular Biology (RECOMB'18)},
pages = {256--257},
place = {Paris, France},
year = {2018},
editor = {Ben Raphael},
abstract = {The design of multi-stable RNA molecules has important applications in biology, medicine, and biotechnology. Synthetic design approaches largely benefit from effective in-silico methods, which can tremendously impact their cost and feasibility. Here, we revisit a central ingredient of most in-silico design methods: the sampling of sequences for multi-target design. We establish the \#P-hardness of uniform sampling, and introduce RNARedPrint, a tree decomposition-based algorithm for efficient, fixed parameter tractable sampling. By modeling the problem as a constraint network, RNARedPrint supports generic Boltzmann-weighted sampling for arbitrary additive RNA energy models; this enables generating designs meeting specific goals like expected free energies or GC-content. Finally, we empirically study general properties of the approach and generate biologically relevant multi-target Boltzmann-weighted designs for a common design benchmark. In particular, we show significant improvements over seed sequences generated by uniform sampling, the previously best available sampling strategy for multi-target design. Our software is freely available at: https://github.com/yannponty/RNARedPrint Keywords: Multi-target RNA Design, Counting Complexity, Boltzmann Sampling},
url = {https://hal.inria.fr/hal-01631277}
}
@Article{Gruning-NatMet2018,
author = {Gruning, Bjorn and Dale, Ryan and Sjodin, Andreas and Chapman, Brad A. and Rowe, Jillian and Tomkins-Tinch, Christopher H. and Valieris, Renan and Koster, Johannes},
title = {Bioconda: sustainable and comprehensive software distribution for the life sciences},
journal = {Nat Methods},
year = {2018},
volume = {15},
number = {7},
pages = {475-476},
user = {will},
pmid = {29967506},
doi = {10.1038/s41592-018-0046-7},
issn = {1548-7105}
}
@Article{Raden-NAR2018,
author = {Raden, Martin and Ali, Syed M. and Alkhnbashi, Omer S. and Busch, Anke and Costa, Fabrizio and Davis, Jason A. and Eggenhofer, Florian and Gelhausen, Rick and Georg, Jens and Heyne, Steffen and Hiller, Michael and Kundu, Kousik and Kleinkauf, Robert and Lott, Steffen C. and Mohamed, Mostafa M. and Mattheis, Alexander and Miladi, Milad and Richter, Andreas S. and Will, Sebastian and Wolff, Joachim and Wright, Patrick R. and Backofen, Rolf},
title = {Freiburg {RNA} tools: a central online resource for {RNA}-focused research and teaching},
journal = {Nucleic Acids Research},
year = {2018},
volume = {46},
number = {W1},
pages = {W25-W29},
user = {will},
pmid = {29788132},
doi = {10.1093/nar/gky329},
issn = {1362-4962},
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.}
}
@article{Kuehnl-BMCBI2017,
author = {Felix K{\"u}hnl and Peter F. Stadler and Sebastian Will},
title = {Tractable RNA--ligand interaction kinetics},
journal = {BMC Bioinformatics},
volume = {18},
number = {Suppl 12},
pages = {47},
year = {2017},
issn = {1471-2105},
doi = {10.1186/s12859-017-1823-5},
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. Availability. The method used in this study is available online: www.bioinf.uni-leipzig.de/~felix/software/RLIkin. Keywords: RNA secondary structure prediction, RNA interaction kinetics, RNA–ligand interaction, Riboswitches.}
}
@article{findeiss2017design,
title = {Design of Artificial Riboswitches as Biosensors},
author = {Findei{\ss}, Sven and Etzel, Maja and Will, Sebastian and M{\"o}rl, Mario and Stadler, Peter F},
journal = {Sensors},
volume = {17},
number = {9},
pages = {1990},
year = {2017},
publisher = {Multidisciplinary Digital Publishing Institute},
doi = {10.3390/s17091990},
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: aptamer; RNA structure; ligand binding; refolding; thermodynamics; rational design; folding kinetics}
}
@article{fallmann2017recent,
title = {Recent advances in RNA folding},
author = {Fallmann, J{\"o}rg and Will, Sebastian and Engelhardt, Jan and Gr{\"u}ning, Bj{\"o}rn and Backofen, Rolf and Stadler, Peter F},
journal = {Journal of Biotechnology},
year = {2017},
publisher = {Elsevier},
doi = {10.1016/j.jbiotec.2017.07.007},
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 secondary structure; RNA constraint folding; RNA interactions; RNA secondary structure comparison; RNA analysis}
}
@article{domin2017applicability,
title = {Applicability of a computational design approach for synthetic riboswitches},
author = {Domin, Gesine and Findei{\ss}, Sven and Wachsmuth, Manja and Will, Sebastian and Stadler, Peter F and M{\"o}rl, Mario},
journal = {Nucleic acids research},
volume = {45},
number = {7},
pages = {4108--4119},
year = {2017},
publisher = {Oxford University Press},
doi = {10.1093/nar/gkw1267},
abstract = {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. Topic: gene expression galactosidase ligands logic protein structure, secondary streptomycin thermodynamics tetracycline theophylline rna escherichia coli free energy binding (molecular function) molecule}
}
@article{gruning2017rna,
title = {The RNA workbench: best practices for RNA and high-throughput sequencing bioinformatics in Galaxy},
author = {Gr{\"u}ning, Bj{\"o}rn A and Fallmann, J{\"o}rg and Yusuf, Dilmurat and Will, Sebastian and Erxleben, Anika and Eggenhofer, Florian and Houwaart, Torsten and Batut, B{\'e}r{\'e}nice and Videm, Pavankumar and Bagnacani, Andrea and others},
journal = {Nucleic Acids Research},
year = {2017},
doi = {10.1093/nar/gkx409},
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.}
}
@InProceedings{Jabbari_et_al-LIPIcs2017,
author = {Hosna Jabbari and Ian Wark and Carlo Montemagno and Sebastian Will},
title = {Sparsification Enables Predicting Kissing Hairpin Pseudoknot Structures of Long {RNA}s in Practice},
booktitle = {17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
pages = {12:1--12:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-050-7},
ISSN = {1868-8969},
year = {2017},
volume = {88},
editor = {Russell Schwartz and Knut Reinert},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
doi = {10.4230/LIPIcs.WABI.2017.12},
abstract = {While computational RNA secondary structure prediction is an important tool in RNA research, it is still fundamentally limited to pseudoknot-free structures (or at best very simple pseudoknots) in practice. Here, we make the prediction of complex pseudoknots - including kissing hairpin structures - practically applicable by reducing the originally high space consumption. For this aim, we apply the technique of sparsification and other space-saving modifications to the recurrences of the pseudoknot prediction algorithm by Chen, Condon and Jabbari (CCJ algorithm). Thus, the theoretical space complexity of free energy minimization is reduced to $\Theta(n^3+Z)$, in the sequence length n and the number of non-optimally decomposable fragments ("candidates") Z. The sparsified CCJ algorithm, sparseCCJ, is presented in detail. Moreover, we provide and compare three generations of CCJ implementations, which continuously improve the space requirements: the original CCJ implementation, our first modified implementation, and our final sparsified implementation. The two latest implementations implement the established HotKnots DP09 energy model. In our experiments, using 244GB of RAM, the original CCJ implementation failed to handle sequences longer than 195 bases; sparseCCJ handles our pseudoknot data set (up to about length 400 bases) in this space limit. All three CCJ implementations are available at https://github.com/HosnaJabbari/CCJ. Keywords: RNA, secondary structure prediction, pseudoknots, space efficiency, sparsification}
}
@InProceedings{Kuehnl-tract_kinet_rna-ISBRA2016,
author = {Felix K{\"u}hnl and Peter F. Stadler and Sebastian Will},
title = {Tractable Kinetics of RNA--Ligand Interaction},
booktitle = {Bioinformatics Research and Applications (ISBRA 2016)},
year = {2016},
editor = {Anu Bourgeois and Pavel Skums and Xiang Wan and Alex Zelikovsky},
volume = {9683},
series = {LNBI},
pages = {2},
month = {June},
publisher = {Springer International Publishing},
doi = {10.1007/978-3-319-38782-6},
isbn = {978-3-319-38782-6},
abstract = {The interaction of RNAs and their ligands strongly depends on folding kinetics and thus requires explanations that go beyond thermodynamic effects. Whereas the computational prediction of minimum energy secondary structures, and even RNA--RNA and RNA--ligand interactions, are well established, the analysis of their kinetics is still in its infancy. Due to enormous conformation spaces, the exact analysis of the combined processes of ligand binding and structure formation requires either the explicit modeling of an intractably large conformation space or---often debatable---simplifications. Moreover, concentration effects play a crucial role. This increases the complexity of modeling the interaction kinetics fundamentally over single molecule kinetics.},
user = {will}
}
@article{Righetti_etal_PNAS2016,
author = {Righetti, Francesco and Nuss, Aaron M. and Twittenhoff, Christian and Beele, Sascha and Urban, Kristina and Will, Sebastian and Bernhart, Stephan H. and Stadler, Peter F. and Dersch, Petra and Narberhaus, Franz},
title = {Temperature-responsive in vitro RNA structurome of Yersinia pseudotuberculosis},
year = {2016},
volume = {113},
number = {26},
pages = {7237--7242},
pmid = {27298343},
doi = {10.1073/pnas.1523004113},
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 (37C), which induces a major metabolic transition. Our analysis profiles the structure of more than 1,750 RNAs at 25C, 37C, and 42C. 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.},
URL = {http://www.pnas.org/content/early/2016/06/10/1523004113.abstract},
eprint = {http://www.pnas.org/content/early/2016/06/10/1523004113.full.pdf},
journal = {Proceedings of the National Academy of Sciences}
}
@Article{Will_Jabbari-Spars_RNA_foldi-2016,
author = {Will, Sebastian and Jabbari, Hosna},
title = {Sparse {RNA} folding revisited: space-efficient minimum free energy structure prediction},
journal = {Algorithms Mol Biol},
year = {2016},
volume = {11},
number = {7},
pages = {13},
user = {will},
pmid = {27110275},
doi = {10.1186/s13015-016-0071-y},
issn = {1748-7188},
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 $n^2$, but are typically much smaller. The time complexity of RNA folding is reduced from $O(n^3)$ to $O(n^2 + nZ)$; the space complexity, from $O(n^2)$ to $O(n + T + Z)$. 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: space efficient sparsification; pseudoknot-free RNA folding; RNA secondary structure prediction}
}
@Article{Berkemer_etal-processed_small_rnas-GCB2015,
author = {Berkemer, Sarah Juliane and H{\"o}ner zu Siederdissen, Christian and Amman, Fabian and Wintsche, Axel and Sebastian Will and Hofacker, Ivo and Prohaska, Sonja and Stadler, Peter},
title = {Processed Small {RNAs} in Archaea and {BHB} Elements},
journal = {Genomics and Computational Biology},
volume = {1},
number = {1},
pages = {e18},
year = {2015},
doi = {10.18547/gcb.2015.vol1.iss1.e18},
abstract = {Bulge-helix-bulge (BHB) elements guide the enzymatic splicing machinery that in Archaea excises introns from tRNAs, rRNAs from their primary precursor, and accounts for the assembly of piece-wise encoded tRNAs. This processing pathway renders the intronic sequences as circularized RNA species. Although archaeal transcriptomes harbor a large number of circular small RNAs, it remains unknown whether most or all of them are produced through BHB-dependent splicing. We therefore conduct a genome-wide survey of BHB elements of a phylogenetically diverse set of archaeal species and complement this approach by searching for BHB-like structures in the vicinity of circularized transcripts. We find that besides tRNA introns, the majority of box C/D snoRNAs is associated with BHB elements. Not all circularized sRNAs, however, can be explained by BHB elements, suggesting that there is at least one other mechanism of RNA circularization at work in Archaea. Pattern search methods were unable, however, to identify common sequence and/or secondary structure features that could be characteristic for such a mechanism. Keywords: Circular RNA; Archaea; splicing; structure-based motif search}
}
@InProceedings{Will_Jabbari-Sparse_TB_RNA_MFE_Folding-WABI2015,
author = {Sebastian Will and Hosna Jabbari},
title = {Sparse RNA folding revisited: space-efficient minimum free energy prediction},
booktitle = {Proceedings of the 15th Workshop on Algorithms in Bioinformatics {(WABI 2015)}},
year = {2015},
series = {LNCS},
editor = {Mihai Pop and H{\'e}l{\`e}ne Touzet},
publisher = {Springer Berlin Heidelberg},
volume = {9289},
pages = {257--270},
isbn = {978-3-662-48220-9},
doi = {10.1007/978-3-662-48221-6_19},
abstract = {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, in particular for long RNAs and complex folding algorithms. So far, space-efficient sparsified RNA folding with fold reconstruction was solved only for simple pseudo-energy models. 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, which guarantees optimal structure prediction. In particular, this novel algorithm provides efficient fold reconstruction based on dynamically garbage collected trace arrows. We provide theoretical and empirical results on the efficiency of the method. SparseMFEFold is free software, available at http://www.bioinf.uni-leipzig.de/~will/Software/SparseMFEFold. Keywords: space efficient sparsification, pseudoknot-free RNA folding, RNA secondary structure prediction},
user = {will}
}
@article{Will_Otto_Miladi-SPARS_quadr_time-2015,
author = {Will, Sebastian and Otto, Christina and Miladi, Milad and Mohl, Mathias and Backofen, Rolf},
title = {{SPARSE}: quadratic time simultaneous alignment and folding of {RNAs} without sequence-based heuristics},
journal = {Bioinformatics},
year = {2015},
volume = {31},
number = {15},
pages = {2489--2496},
pmid = {25838465},
doi = {10.1093/bioinformatics/btv185},
issn = {1367-4803},
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. AVAILABILITY AND IMPLEMENTATION: SPARSE is freely available at http://www.bioinf.uni-freiburg.de/Software/SPARSE. CONTACT: backofen@informatik.uni-freiburg.de Supplementary information: Supplementary data are available at Bioinformatics online.}
}
@article{Otto_Mohl_Heyne-ExpaR_simul_exact-2014,
author = {Otto, Christina and M{\"o}hl, Mathias and Heyne, Steffen and Amit, Mika and Landau, Gad M. and Backofen, Rolf and Will, Sebastian},
title = {{ExpaRNA}-{P}: simultaneous exact pattern matching and folding of {RNAs}},
journal = {BMC Bioinformatics},
year = {2014},
volume = {15},
number = {1},
pages = {404},
user = {kousik},
pmid = {25551362},
doi = {10.1186/s12859-014-0404-0},
issn = {1471-2105},
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 inverted question marksimultaneous alignment and folding inverted question mark 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 inverted question marks 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 ( inverted question mark400nt). 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 inverted question marks 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.}
}
@article{amit14:_local_exact_patter_match_non_fixed_struc,
author = {Mika Amit and Rolf Backofen and Steffen Heyne and Gad M. Landau and Mathias M{\"o}hl and Christina Otto and Sebastian Will},
title = {Local Exact Pattern Matching for Non-Fixed {RNA} Structures},
journal = {IEEE/ACM Trans. Comput. Biology Bioinform.},
year = {2014},
volume = {11},
number = {1},
pages = {219--230},
doi = {10.1109/TCBB.2013.2297113},
issn = {1545-5963},
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^3k^2)$ time. Finally, we present an $O(n^3)$ algorithm for finding the most similar subforest between two nested RNAs.},
user = {backofen}
}
@InProceedings{Will_Stadler-Cyclic_MSA-WABI2014,
author = {Sebastian Will and Peter F. Stadler},
title = {A Common Framework for Linear and Cyclic Multiple Sequence Alignment Problems},
booktitle = {Proceedings of Algorithms in Bioinformatics (WABI'14)},
isbn = {978-3-662-44752-9},
editor = {Brown, Dan and Morgenstern, Burkhard},
year = {2014},
volume = {8701},
series = {LNCS},
pages = {135--147},
publisher = {Springer Berlin Heidelberg},
doi = {10.1007/978-3-662-44753-6_11},
user = {will},
abstract = {Circularized RNAs have received considerable attention is the last few years following the discovery that they are not only a rather common phenomenon in the transcriptomes of Eukarya and Archaea but also may have key regulatory functions. This calls for the adaptation of basic tools of sequence analysis to accommodate cyclic sequences. Here we discuss a common formal framework for linear and circular alignments as partitions that preserve (cyclic) order. We focus on the similarities and differences and describe a prototypical ILP formulation.},
keywords = {cyclic sequence alignment; multiple sequence alignment; cyclic orders; integer linear programming; circular RNAs}
}
@article{Waldispuhl_ODonnell_Will-Simul_Align_and-JCB2014,
author = {Waldispuhl, Jerome and O'Donnell, Charles W. and Will, Sebastian and Devadas, Srinivas and Backofen, Rolf and Berger, Bonnie},
title = {Simultaneous {Alignment} and {Folding} of {Protein} {Sequences}},
journal = {J Comput Biol},
year = {2014},
volume = {21},
number = {7},
pages = {477--491},
user = {backofen},
pmid = {24766258},
doi = {10.1089/cmb.2013.0163},
issn = {1557-8666},
abstract = {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 beta-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/ ).}
}
@InProceedings{Schneider_etal-ncRNAs-K-pastoris_2014,
title = {Genome-Wide Identification of Non-coding RNAs in Komagatella pastoris str. GS115},
author = {Schneider, Hugo and Bartschat, Sebastian and Doose, Gero and Maciel, Lucas and Pizani, Erick and Bassani, Marcelo and Torres, Fernando Araripe and Sebastian Will and Raiol, Tain{\'a} and Br{\'\i}gido, Marcelo and Walter, Maria Em{\'\i}lia and Stadler, Peter},
year = {2014},
isbn = {978-3-319-12417-9},
booktitle = {Advances in Bioinformatics and Computational Biology},
volume = {8826},
series = {Lecture Notes in Computer Science},
editor = {Campos, S{\'e}rgio},
doi = {10.1007/978-3-319-12418-6_15},
publisher = {Springer International Publishing},
keywords = {Non-coding RNA; Transcriptome; Komagatella pastoris; Pichia pastoris; snoRNA; long ncRNA},
pages = {115--122},
language = {English},
user = {will}
}
@article{Lange_Alkhnbashi_Rose-CRISP_autom_class-NAR2013,
author = {Lange, Sita J. and Alkhnbashi, Omer S. and Rose, Dominic and Will, Sebastian and Backofen, Rolf},
title = {{CRISPRmap}: an automated classification of repeat conservation in prokaryotic adaptive immune systems},
journal = {Nucleic Acids Res},
year = {2013},
volume = {41},
number = {17},
pages = {8034--44},
user = {sita},
pmid = {23863837},
doi = {10.1093/nar/gkt606},
note = {SJL, OSA and DR contributed equally to this work.},
issn = {1362-4962},
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.}
}
@article{Will_Yu_Berger-Struc_whole_reali-2013,
author = {Will, Sebastian and Yu, Michael and Berger, Bonnie},
title = {Structure-based whole-genome realignment reveals many novel noncoding {RNAs}},
journal = {Genome Res},
year = {2013},
volume = {23},
number = {6},
pages = {1018--1027},
user = {will},
pmid = {23296921},
doi = {10.1101/gr.137091.111},
issn = {1549-5469},
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.}
}
@inproceedings{Will_etal-SPARSE-RECOMB2013,
author = {Sebastian Will and Christina Schmiedl and Milad Miladi and Mathias M{\"o}hl and Rolf Backofen},
title = {{SPARSE}: Quadratic Time Simultaneous Alignment and Folding of {RNA}s Without Sequence-Based Heuristics},
booktitle = {Proceedings of the 17th International Conference on Research in Computational Molecular Biology (RECOMB 2013)},
year = {2013},
isbn = {978-3-642-37194-3},
volume = {7821},
series = {LNCS},
editor = {Deng, Minghua and Jiang, Rui and Sun, Fengzhu and Zhang, Xuegong},
doi = {10.1007/978-3-642-37195-0_28},
publisher = {Springer Berlin Heidelberg},
pages = {289--290},
user = {will},
abstract = {Motivation: There is increasing evidence of pervasive transcription, resulting in hundreds of thousands of ncRNAs of unknown function. Standard computational analysis tasks for inferring functional annotations like clustering require fast and accurate RNA comparisons based on sequence and structure similarity. The gold standard for the latter is Sankoff’s algorithm, which simultaneously aligns and folds RNAs. Because of its extreme time complexity of $O(n^6)$, numerous faster "Sankoff-style" approaches have been suggested. Several such approaches introduce heuristics based on sequence alignment, which compromises the alignment quality for RNAs with sequence identities below $60\%$. Avoiding such heuristics, as e.g. in LocARNA, has been assumed to prohibit time complexities better than $O(n^4)$, which strongly limits large-scale applications. Results: Breaking this barrier, we introduce SPARSE (Sparse Prediction and Alignment of RNAs using Structure Ensembles), a novel quadratic time Sankoff-style approach that does not rely on sequence-based heuristics but employs structural properties of RNA ensembles; its $O(n^2)$ complexity matches the one of sequence alignment. The approach is based on a novel lightweight Sankoff-style alignment model, for which we introduce the algorithm PARSE. For the first time it transfers the Sankoff-model completely to a lightweight energy model; thus, it is more expressive than all previous lightweight methods, which inherit the PMcomp model. In comparison to LocARNA and similar approaches, the novel model enables much stronger sparsification based on the RNA structure ensemble; consequently, SPARSE aligns and folds RNAs with similar alignment and better folding quality in significantly less time. Finally, SPARSE aligns ncRNAs from the challenging low sequence identity region more accurately than tools relying on sequence-based heuristics. Conclusion: Our results indicate that a complete lightweight Sankoff-style model with stronger sparsification can increase the performance and accuracy of RNA alignment, where the potential of the model points far beyond the studied prototype. Not falling back on sequence comparison, SPARSE suggests itself for large scale similarity assessment of RNAs with moderate to very low sequence identity.}
}
@incollection{Amman-Long_Range-BSB2013,
title = {The Trouble with Long-Range Base Pairs in RNA Folding},
author = {Fabian Amman and Stephan H. Bernhart and Gero Doose and Ivo L. Hofacker and Jing Qin and Peter F. Stadler and Sebastian Will},
year = {2013},
isbn = {978-3-319-02623-7},
booktitle = {Advances in Bioinformatics and Computational Biology},
volume = {8213},
series = {Lecture Notes in Computer Science},
editor = {Setubal, Jo{\~a}o C. and Almeida, Nalvo F.},
doi = {10.1007/978-3-319-02624-4_1},
publisher = {Springer International Publishing},
keywords = {RNA folding; long-range base pair; prediction accuracy; polymer zeta property},
pages = {1--11},
user = {will},
abstract = {RNA prediction has long been struggling with long-range base pairs since prediction accuracy decreases with base pair span. We analyze here the empirical distribution of base pair spans in large collection of experimentally known RNA structures. Surprisingly, we find that long-range base pairs are overrepresented in these data. In particular, there is no evidence that long-range base pairs are systematically overpredicted relative to short-range interactions in thermodynamic predictions. This casts doubt on a recent suggestion that kinetic effects are the cause of length-dependent decrease of predictability. Instead of a modification of the energy model we advocate a modification of the expected accuracy model for RNA secondary structures. We demonstrate that the inclusion of a span-dependent penalty leads to improved maximum expected accuracy structure predictions compared to both the standard MEA model and a modiS,ed folding algorithm with an energy penalty function. The prevalence of long-range base pairs provide further evidence that RNA structures in general do not have the so-called polymer zeta property. This has consequences for the asymptotic performance for a large class of sparsified RNA folding algorithms.}
}
@article{Will_Joshi_Hofacker-LocAR_Accur_bound-2012,
author = {Will, Sebastian and Joshi, Tejal and Hofacker, Ivo L. and Stadler, Peter F. and Backofen, Rolf},
title = {{LocARNA}-{P}: {Accurate} boundary prediction and improved detection of structural {RNAs}},
journal = {RNA},
year = {2012},
volume = {18},
number = {5},
pages = {900--14},
user = {will},
pmid = {22450757},
doi = {10.1261/rna.029041.111},
issn = {1355-8382},
abstract = {Current genomic screens for noncoding RNAs (ncRNAs) predict a large number of genomic regions containing potential structural ncRNAs. The analysis of these data requires highly accurate prediction of ncRNA boundaries and discrimination of promising candidate ncRNAs from weak predictions. Existing methods struggle with these goals because they rely on sequence-based multiple sequence alignments, which regularly misalign RNA structure and therefore do not support identification of structural similarities. To overcome this limitation, we compute columnwise and global reliabilities of alignments based on sequence and structure similarity; we refer to these structure-based alignment reliabilities as STARs. The columnwise STARs of alignments, or STAR profiles, provide a versatile tool for the manual and automatic analysis of ncRNAs. In particular, we improve the boundary prediction of the widely used ncRNA gene finder RNAz by a factor of 3 from a median deviation of 47 to 13 nt. Post-processing RNAz predictions, LocARNA-P's STAR score allows much stronger discrimination between true- and false-positive predictions than RNAz's own evaluation. The improved accuracy, in this scenario increased from AUC 0.71 to AUC 0.87, significantly reduces the cost of successive analysis steps. The ready-to-use software tool LocARNA-P produces structure-based multiple RNA alignments with associated columnwise STARs and predicts ncRNA boundaries. We provide additional results, a web server for LocARNA/LocARNA-P, and the software package, including documentation and a pipeline for refining screens for structural ncRNA, at http://www.bioinf.uni-freiburg.de/Supplements/LocARNA-P/.}
}
@article{Washietl_Will_Hendrix-Compu_analy_nonco-2012,
author = {Washietl, Stefan and Will, Sebastian and Hendrix, David A. and Goff, Loyal A. and Rinn, John L. and Berger, Bonnie and Kellis, Manolis},
title = {Computational analysis of noncoding {RNAs}},
journal = {Wiley Interdiscip Rev RNA},
year = {2012},
volume = {3},
number = {6},
pages = {759--78},
user = {will},
pmid = {22991327},
doi = {10.1002/wrna.1134},
issn = {1757-7012},
abstract = {Noncoding RNAs have emerged as important key players in the cell. Understanding their surprisingly diverse range of functions is challenging for experimental and computational biology. Here, we review computational methods to analyze noncoding RNAs. The topics covered include basic and advanced techniques to predict RNA structures, annotation of noncoding RNAs in genomic data, mining RNA-seq data for novel transcripts and prediction of transcript structures, computational aspects of microRNAs, and database resources. These authors contributed equally WIREs RNA 2012. doi: 10.1002/wrna.1134 For further resources related to this article, please visit the WIREs website.}
}
@article{Sorescu_Mohl_Mann-CARNA_RNA_struc-NAR2012,
author = {Dragos A. Sorescu and Mathias M{\"o}hl and Martin Mann and Rolf Backofen and Sebastian Will},
title = {{CARNA} - alignment of {RNA} structure ensembles},
journal = {Nucleic Acids Res},
year = {2012},
volume = {40},
number = {W1},
pages = {W49-W53},
note = {DAS, MM{\"o}, and MMa contributed equally to this work.},
user = {will},
pmid = {22689637},
doi = {10.1093/nar/gks491},
issn = {0305-1048},
abstract = {Due to recent algorithmic progress, tools for the gold standard of comparative RNA analysis, namely Sankoff-style simultaneous alignment and folding, are now readily applicable. Such approaches, however, compare RNAs with respect to a simultaneously predicted, single, nested consensus structure. To make multiple alignment of RNAs available in cases, where this limitation of the standard approach is critical, we introduce a web server that provides a complete and convenient interface to the RNA structure alignment tool 'CARNA'. This tool uniquely supports RNAs with multiple conserved structures per RNA and aligns pseudoknots intrinsically; these features are highly desirable for aligning riboswitches, RNAs with conserved folding pathways, or pseudoknots. We represent structural input and output information as base pair probability dot plots; this provides large flexibility in the input, ranging from fixed structures to structure ensembles, and enables immediate visual analysis of the results. In contrast to conventional Sankoff-style approaches, 'CARNA' optimizes all structural similarities in the input simultaneously, for example across an entire RNA structure ensemble. Even compared with already costly Sankoff-style alignment, 'CARNA' solves an intrinsically much harder problem by applying advanced, constraint-based, algorithmic techniques. Although 'CARNA' is specialized to the alignment of RNAs with several conserved structures, its performance on RNAs in general is on par with state-of-the-art general-purpose RNA alignment tools, as we show in a Bralibase 2.1 benchmark. The web server is freely available at http://rna.informatik.uni-freiburg.de/CARNA.}
}
@inproceedings{Schmiedl:etal:_exparnap:RECOMB2012,
author = {Christina Schmiedl and Mathias M{\"o}hl and Steffen Heyne and Mika Amit and Gad M. Landau and Sebastian Will and Rolf Backofen},
title = {Exact Pattern Matching for {RNA} Structure Ensembles},
booktitle = {Proceedings of the 16th International Conference on Research in Computational Molecular Biology (RECOMB 2012)},
pages = {245--260},
year = {2012},
series = {LNCS},
volume = {7262},
isbn = {978-3-642-29626-0},
editors = {Benny Chor},
publisher = {Springer-Verlag},
user = {will},
doi = {10.1007/978-3-642-29627-7_27},
abstract = {ExpaRNA's core algorithm computes, for two fixed RNA structures, a maximal non-overlapping set of maximal exact matchings. We introduce an algorithm ExpaRNA-P that solves the lifted problem of finding such sets of exact matchings in entire Boltzmann-distributed structure ensembles of two RNAs. Due to a novel kind of structural sparsification, the new algorithm maintains the time and space complexity of the algorithm for fixed input structures. Furthermore, we generalized the chaining algorithm of ExpaRNA in order to compute a compatible subset of ExpaRNA-P's exact matchings.We show that ExpaRNA-P outperforms ExpaRNA in BRAliBase 2.1 benchmarks, where we pass the chained exact matchings as anchor constraints to the RNA alignment tool LocARNA. Compared to LocARNA, this novel approach shows similar accuracy but is six times faster.}
}
@inproceedings{Amit-local_exact_pattern_matching-CPM2012,
author = {Mika Amit and Rolf Backofen and Steffen Heyne and Gad M. Landau and Mathias M{\"o}hl and Christina Schmiedl and Sebastian Will},
title = {Local Exact Pattern Matching for Non-fixed {RNA} Structures},
booktitle = {Proceedings of the 23th Annual Symposium on Combinatorial Pattern Matching (CPM 2012)},
year = {2012},
series = {LNCS},
volume = {7354},
publisher = {Springer-Verlag},
editors = {Juha K{\"a}rkk{\"a}inen and Jens Stoye},
isbn = {978-3-642-31264-9},
pages = {306--320},
doi = {10.1007/978-3-642-31265-6_25},
user = {will},
abstract = {Detecting local common sequence-structure regions of RNAs is a biologically meaningful problem. By detecting such regions, biologists are able to identify functional similarity 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 which matches fixed structures, we support the arc breaking edit operation; this allows to match only a subset of the given base pairs. We present an $O(n^3)$ algorithm for local exact pattern matching between two nested RNAs, and an $O(n^3 logn)$ algorithm for one nested RNA and one bounded-unlimited RNA.}
}
@inproceedings{Will:Yu:Berger:_structure_based:RECOMB2012,
author = {Sebastian Will and Michael Yu and Bonnie Berger},
title = {Structure-based Whole Genome Realignment Reveals Many Novel Non-coding {RNAs}},
booktitle = {Proceedings of the 16th International Conference on Research in Computational Molecular Biology (RECOMB 2012)},
pages = {341},
year = {2012},
series = {LNCS},
volume = {7262},
isbn = {978-3-642-29626-0},
editors = {Benny Chor},
publisher = {Springer-Verlag},
user = {will},
doi = {10.1007/978-3-642-29627-7_35},
abstract = {Recent genome-wide computational screens that search for conservation of RNA secondary structure in whole genome alignments (WGAs) have predicted thousands of structural non-coding 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 align- ment, 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 de novo Prediction of structural ncRNA) that realigns whole genomes based on RNA sequence and structure and then evaluates the realignments for potential structural ncRNAs with a ncRNA predictor such as RNAz 2.0. For efficiency of the pipeline, we develop a novel banding realignment algorithm for the RNA multiple alignment tool LocARNA. This allows us to perform very fast structure-based realignment within limited deviation of the original multiple alignment from the WGA. We apply REAPR to the complete twelve Drosophila WGAs to predict ncRNAs across all these Drosophila species. Compared to direct prediction from the original WGA at the same False Discovery Rate (FDR), we predict twice as many high-confidence ncRNA candidates in D.melanogaster while less than doubling the run-time. As a novelty in ncRNA prediction, we control the FDR, going beyond the usual a posteriori FDR estimation. Applying the sequence-based alignment tool Muscle for realignment, we demonstrate that structure-based methods are necessary for effective prediction of originally misaligned ncRNAs. Comparing to recent screens of Drosophila and ENCODE we show that REAPR outperforms the widely-used de novo predictors RNAz, EvoFold, and CMfinder. Finally, we reveal, with high confidence, a putative structural motif in the long ncRNA roX1 of D.melanogaster, known to regulate X chromosome dosage compensation in male ies. Interestingly, we recapitulate the Drosophila phylogeny, based on co-predicted ncRNAs across all genomes.}
}
@article{Meyer:Kurtz:Backofen:Struc_fast_index:2011,
author = {Fernando Meyer and Stefan Kurtz and Rolf Backofen and Sebastian Will and Michael Beckstette},
title = {Structator: fast index-based search for {RNA} sequence-structure patterns},
journal = {BMC Bioinformatics},
year = {2011},
volume = {12},
number = {1},
pages = {214},
user = {backofen},
pmid = {21619640},
doi = {10.1186/1471-2105-12-214},
issn = {1471-2105},
abstract = {ABSTRACT: BACKGROUND: The secondary structure of RNA molecules is intimately related to their function and often more conserved than the sequence. Hence, the important task of searching databases for RNAs requires to match sequence-structure patterns. Unfortunately, current tools for this task have, in the best case, a running time that is only linear in the size of sequence databases. Furthermore, established index data structures for fast sequence matching, like suffix trees or arrays, cannot benefit from the complementarity constraints introduced by the secondary structure of RNAs. RESULTS: We present a novel method and readily applicable software for time efficient matching of RNA sequence-structure patterns in sequence databases. Our approach is based on affix arrays, a recently introduced index data structure, preprocessed from the target database. Affix arrays support bidirectional pattern search, which is required for efficiently handling the structural constraints of the pattern. Structural patterns like stem-loops can be matched inside out, such that the loop region is matched first and then the pairing bases on the boundaries are matched consecutively. This allows to exploit base pairing information for search space reduction and leads to an expected running time that is sublinear in the size of the sequence database. The incorporation of a new chaining approach in the search of RNA sequence-structure patterns enables the description of molecules folding into complex secondary structures with multiple ordered patterns. The chaining approach removes spurious matches from the set of intermediate results, in particular of patterns with little specificity. In benchmark experiments on the Rfam database, our method runs up to two orders of magnitude faster than previous methods. CONCLUSIONS: The presented method's sublinear expected running time makes it well suited for RNA sequence-structure pattern matching in large sequence databases. RNA molecules containing several stem-loop substructures can be described by multiple sequence-structure patterns and their matches are efficiently handled by a novel chaining method. Beyond our algorithmic contributions, we provide with Structator a complete and robust open-source software solution for index-based search of RNA sequence-structure patterns. The Structator software is available at http://www.zbh.uni-hamburg.de/Structator.}
}
@article{Roy:Ernst:Kharchenko:Ident_funct_eleme:2010,
author = {Roy, Sushmita and Ernst, Jason and Kharchenko, Peter V. and Kheradpour, Pouya and Negre, Nicolas and Eaton, Matthew L. and Landolin, Jane M. and Bristow, Christopher A. and Ma, Lijia and Lin, Michael F. and Washietl, Stefan and Arshinoff, Bradley I. and Ay, Ferhat and Meyer, Patrick E. and Robine, Nicolas and Washington, Nicole L. and Di Stefano, Luisa and Berezikov, Eugene and Brown, Christopher D. and Candeias, Rogerio and Carlson, Joseph W. and Carr, Adrian and Jungreis, Irwin and Marbach, Daniel and Sealfon, Rachel and Tolstorukov, Michael Y. and Will, Sebastian and Alekseyenko, Artyom A. and Artieri, Carlo and Booth, Benjamin W. and Brooks, Angela N. and Dai, Qi and Davis, Carrie A. and Duff, Michael O. and Feng, Xin and Gorchakov, Andrey A. and Gu, Tingting and Henikoff, Jorja G. and Kapranov, Philipp and Li, Renhua and MacAlpine, Heather K. and Malone, John and Minoda, Aki and Nordman, Jared and Okamura, Katsutomo and Perry, Marc and Powell, Sara K. and Riddle, Nicole C. and Sakai, Akiko and Samsonova, Anastasia and Sandler, Jeremy E. and Schwartz, Yuri B. and Sher, Noa and Spokony, Rebecca and Sturgill, David and van Baren, Marijke and Wan, Kenneth H. and Yang, Li and Yu, Charles and Feingold, Elise and Good, Peter and Guyer, Mark and Lowdon, Rebecca and Ahmad, Kami and Andrews, Justen and Berger, Bonnie and Brenner, Steven E. and Brent, Michael R. and Cherbas, Lucy and Elgin, Sarah C. R. and Gingeras, Thomas R. and Grossman, Robert and Hoskins, Roger A. and Kaufman, Thomas C. and Kent, William and Kuroda, Mitzi I. and Orr-Weaver, Terry and Perrimon, Norbert and Pirrotta, Vincenzo and Posakony, James W. and Ren, Bing and Russell, Steven and Cherbas, Peter and Graveley, Brenton R. and Lewis, Suzanna and Micklem, Gos and Oliver, Brian and Park, Peter J. and Celniker, Susan E. and Henikoff, Steven and Karpen, Gary H. and Lai, Eric C. and MacAlpine, David M. and Stein, Lincoln D. and White, Kevin P. and Kellis, Manolis},
title = {Identification of functional elements and regulatory circuits by {Drosophila} {modENCODE}},
journal = {Science},
year = {2010},
volume = {330},
number = {6012},
pages = {1787--97},
user = {will},
pmid = {21177974},
doi = {10.1126/science.1198374},
issn = {0036-8075},
abstract = {To gain insight into how genomic information is translated into cellular and developmental programs, the Drosophila model organism Encyclopedia of DNA Elements (modENCODE) project is comprehensively mapping transcripts, histone modifications, chromosomal proteins, transcription factors, replication proteins and intermediates, and nucleosome properties across a developmental time course and in multiple cell lines. We have generated more than 700 data sets and discovered protein-coding, noncoding, RNA regulatory, replication, and chromatin elements, more than tripling the annotated portion of the Drosophila genome. Correlated activity patterns of these elements reveal a functional regulatory network, which predicts putative new functions for genes, reveals stage- and tissue-specific regulators, and enables gene-expression prediction. Our results provide a foundation for directed experimental and computational studies in Drosophila and related species and also a model for systematic data integration toward comprehensive genomic and functional annotation.}
}
@article{Moehl:Sparsification:AMB2011,
author = {Mathias M{\"o}hl and Raheleh Salari and Sebastian Will and Rolf Backofen and S. Cenk Sahinalp},
title = {Sparsification of {RNA} structure prediction including pseudoknots},
journal = {Algorithms Mol Biol},
year = {2010},
issn = {1748-7188},
volume = {5},
number = {1},
pages = {39},
user = {mmohl},
pmid = {21194463},
doi = {10.1186/1748-7188-5-39},
abstract = {ABSTRACT: BACKGROUND: Although many RNA molecules contain pseudoknots, computational prediction of pseudoknotted RNA structure is still in its infancy due to high running time and space consumption implied by the dynamic programming formulations of the problem. RESULTS: We introduce sparsification to significantly speedup the dynamic programming approaches for pseudoknotted RNA structure prediction, which also lower the space requirements. Although sparsification has been applied to a number of RNA-related structure prediction problems in the past few years, we provide the first application of sparsification to pseudoknotted RNA structure prediction specifically and to handling gapped fragments more generally - which has a much more complex recursive structure than other problems to which sparsification has been applied. We analyse how to sparsify four pseudoknot structure prediction algorithms, among those the most general method available (the Rivas-Eddy algorithm) and the fastest one (Reeder-Giegerich algorithm). In all algorithms the number of "candidate" substructures to be considered is reduced. CONCLUSION: Experimental results on the sparsified Reeder-Giegerich algorithm suggest a linear speedup over the unsparsified implementation.}
}
@inproceedings{moehl_wabi10:Sparsification,
author = {M{\"o}hl, Mathias and Salari, Raheleh and Will, Sebastian and Backofen, Rolf and Sahinalp, S. Cenk},
title = {Sparsification of {RNA} Structure Prediction Including Pseudoknots},
booktitle = {Proc. of the 10th Workshop on Algorithms in Bioinformatics {(WABI)}},
year = {2010},
series = {Lecture Notes in Computer Science},
editor = {Moulton, Vincent and Singh, Mona},
publisher = {Springer Berlin / Heidelberg},
pages = {40--51},
volume = {6293},
doi = {10.1007/978-3-642-15294-8_4},
abstract = {Although many RNA molecules contain pseudoknots, computational prediction of pseudoknotted RNA structure is still in its infancy due to high running time and space consumption implied by the dynamic programming formulations of the problem. In this paper, we introduce sparsification to significantly speedup the dynamic programming approaches for pseudoknotted RNA structure prediction, which also lower the space requirements. Although sparsification has been applied to a number of RNA-related structure prediction problems in the past few years, we provide the first application of sparsification to pseudoknotted RNA structure prediction specifically and to handling gapped fragments more generally - which has a much more complex recursive structure than other problems to which sparsification has been applied. We show that sparsification, when applied to the fastest, as well as the most general pseudoknotted structure prediction methods available, - respectively the Reeder-Giegerich algorithm and the Rivas-Eddy algorithm - reduces the number of candidate substructures to be considered significantly. In fact, experimental results on the sparsified Reeder-Giegerich algorithm suggest a linear speedup over the unsparsified implementation.},
user = {mmohl}
}
@inproceedings{palu_moehl_will_cp2010,
author = {Alessandro Dal Palu and Mathias M{\"o}hl and Sebastian Will},
title = {A Propagator for Maximum Weight String Alignment with Arbitrary Pairwise Dependencies},
booktitle = {Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming (CP-2010)},
year = {2010},
pages = {167--175},
location = {St Andrews, Scotland},
doi = {10.1007/978-3-642-15396-9_16},
abstract = {The optimization of weighted string alignments is a well studied problem recurring in a number of application domains and can be solved efficiently. The problem becomes MAX-SNP-hard as soon as arbitrary pairwise dependencies among the alignment edges are introduced. We present a global propagator for this problem which is based on efficiently solving a relaxation of it. In the context of bioinformatics, the problem is known as alignment of arc-annotated sequences, which is e.g. used for comparing RNA molecules. For a restricted version of this alignment problem, we show that a constraint program based on our propagator is on par with state of the art methods. For the general problem with unrestricted dependencies, our tool constitutes the first available method with promising applications in this field.},
user = {mmohl}
}
@article{Smith:Heyne:Richter:Freib_RNA_Tools:NAR2010,
author = {Smith, Cameron and Heyne, Steffen and Richter, Andreas S. and Will, Sebastian and Backofen, Rolf},
title = {Freiburg {RNA} {Tools}: a web server integrating {IntaRNA}, {ExpaRNA} and {LocARNA}},
journal = {Nucleic Acids Res},
year = {2010},
volume = {38 Suppl},
pages = {W373--7},
user = {arichter},
pmid = {20444875},
doi = {10.1093/nar/gkq316},
issn = {1362-4962},
abstract = {The Freiburg RNA tools web server integrates three tools for the advanced analysis of RNA in a common web-based user interface. The tools IntaRNA, ExpaRNA and LocARNA support the prediction of RNA-RNA interaction, exact RNA matching and alignment of RNA, respectively. The Freiburg RNA tools web server and the software packages of the stand-alone tools are freely accessible at http://rna.informatik.uni-freiburg.de.}
}
@inproceedings{Salari:etal:_time_and_space_effic_rna:RECOMB2010,
author = {Salari, Raheleh and M{\"o}hl, Mathias and Will, Sebastian and Sahinalp, S. Cenk and Backofen, Rolf},
title = {Time and Space Efficient {RNA}-{RNA} Interaction Prediction via Sparse Folding},
year = {2010},
booktitle = {Proc. of RECOMB 2010},
series = {Lecture Notes in Computer Science},
editor = {Berger, Bonnie},
publisher = {Springer-Verlag Berlin Heidelberg},
pages = {473--490},
volume = {6044},
doi = {10.1007/978-3-642-12683-3_31},
abstract = {In the past years, a large set of new regulatory ncRNAs have been identified, but the number of experimentally verified targets is considerably low. Thus, computational target prediction methods are on high demand. Whereas all previous approaches for predicting a general joint structure have a complexity of $O(n^6)$ running time and $O(n^4)$ space, a more time and space efficient interaction prediction that is able to handle complex joint structures is necessary for genome-wide target prediction problems. In this paper we show how to reduce both the time and space complexity of the RNA-RNA interaction prediction problem as described by Alkan et al. via dynamic programming sparsification - which allows to discard large portions of DP tables without loosing optimality. Applying sparsification techniques reduces the complexity of the original algorithm from $O(n^6)$ time and $O(n^4)$ space to $O(n^4 \psi(n))$ time and $O(n^2 \psi(n) + n^3)$ space for some function $\psi(n)$, which turns out to have small values for the range of $n$ that we encounter in practice. Under the assumption that the polymer-zeta property holds for RNA-structures, we demonstrate that $\psi(n)=O(n)$ on average, resulting in a linear time and space complexity improvement over the original algorithm. We evaluate our sparsified algorithm for RNA-RNA interaction prediction by total free energy minimization, based on the energy model of Chitsaz et al., on a set of known interactions. Our results confirm the significant reduction of time and space requirements in practice.},
user = {arichter}
}
@article{Moehl:Will:Backofen:PKalign:JCB2010,
author = {M{\"o}hl, Mathias and Will, Sebastian and Backofen, Rolf},
title = {Lifting prediction to alignment of {RNA} pseudoknots},
journal = {J Comput Biol},
issn = {1066-5277},
year = {2010},
volume = {17},
number = {3},
pages = {429--42},
user = {arichter},
pmid = {20377455},
doi = {10.1089/cmb.2009.0168},
abstract = {Prediction and alignment of RNA pseudoknot structures are NP-hard. Nevertheless, several efficient prediction algorithms by dynamic programming have been proposed for restricted classes of pseudoknots. We present a general scheme that yields an efficient alignment algorithm for arbitrary such classes. Moreover, we show that such an alignment algorithm benefits from the class restriction in the same way as the corresponding structure prediction algorithm does. We look at six of these classes in greater detail. The time and space complexity of the alignment algorithm is increased by only a linear factor over the respective prediction algorithm. For five of the classes, no efficient alignment algorithms were known. For the sixth, most general class, we improve the previously best complexity of O(n(5)m(5)) time to O(nm(6)), where n and m denote sequence lengths. Finally, we apply our fastest algorithm with O(nm(4)) time and O(nm(2)) space to comparative de-novo pseudoknot prediction.}
}
@article{Heyne:Will:Beckstette:Backofen:BI_ExpaRNA_2009,
author = {Steffen Heyne and Sebastian Will and Michael Beckstette and Rolf Backofen},
title = {Lightweight Comparison of {RNAs} Based on Exact Sequence-Structure Matches},
journal = {Bioinformatics},
year = {2009},
volume = {25},
number = {16},
pages = {2095--2102},
pmid = {19189979},
doi = {10.1093/bioinformatics/btp065},
issn = {1367-4803},
abstract = { MOTIVATION: Specific functions of ribonucleic acid (RNA) molecules are often associated with different motifs in the RNA structure. The key feature that forms such an RNA motif is the combination of sequence and structure properties. In this article, we introduce a new RNA sequence-structure comparison method which maintains exact matching substructures. Existing common substructures are treated as whole unit while variability is allowed between such structural motifs. Based on a fast detectable set of overlapping and crossing substructure matches for two nested RNA secondary structures, our method ExpaRNA (exact pattern of alignment of RNA) computes the longest collinear sequence of substructures common to two RNAs in O(H*nm) time and O(nm) space, where H << n.m for real RNA structures. Applied to different RNAs, our method correctly identifies sequence-structure similarities between two RNAs. RESULTS: We have compared ExpaRNA with two other alignment methods that work with given RNA structures, namely RNAforester and RNAalign. The results are in good agreement, but can be obtained in a fraction of running time, in particular for larger RNAs. We have also used ExpaRNA to speed up state-of-the-art Sankoff-style alignment tools like LocARNA, and observe a tradeoff between quality and speed. However, we get a speedup of 4.25 even in the highest quality setting, where the quality of the produced alignment is comparable to that of LocARNA alone. AVAILABILITY: The presented algorithm is implemented in the program ExpaRNA, which is available from our website (http://www.bioinf.uni-freiburg.de/Software).},
user = {heyne}
}
@article{Mann_CPSPweb_2009,
author = {Mann, Martin and Smith, Cameron and Rabbath, Mohamad and Edwards, Marlien and Will, Sebastian and Backofen, Rolf},
title = {{CPSP}-web-tools: a server for {3D} lattice protein studies},
journal = {Bioinformatics},
issn = {1367-4803},
year = {2009},
volume = {25},
number = {5},
pages = {676--7},
user = {arichter},
pmid = {19151096},
doi = {10.1093/bioinformatics/btp034},
abstract = {Studies on proteins are often restricted to highly simplified models to face the immense computational complexity of the associated problems. Constraint-based protein structure prediction (CPSP) tools is a package of very fast algorithms for ab initio optimal structure prediction and related problems in 3D HP-models [cubic and face centered cubic (FCC)]. Here, we present CPSP-web-tools, an interactive online interface of these programs for their immediate use. They include the first method for the direct prediction of optimal energies and structures in 3D HP side-chain models. This newest extension of the CPSP approach is described here for the first time. AVAILABILITY AND IMPLEMENTATION: Free access at http://cpsp.informatik.uni-freiburg.de}
}
@inproceedings{Waldispuehl:etal:TMBalign:RECOMB09,
author = {J{\'e}r{\^o}me Waldisp{\"u}hl and Charles W. O'Donnell and Sebastian Will and Srinivas Devadas and Rolf Backofen and Bonnie Berger},
title = {Simultaneous Alignment and Folding of Protein Sequences},
booktitle = {Proc.of the 13$^{th}$ Annual International Conferences on Computational Molecular Biology (RECOMB'09)},
user = {will},
editor = {Serafim Batzoglou},
publisher = {Springer},
location = {Heidelberg},
series = {LNBI},
volume = {5541},
year = {2009},
isbn = {978-3-642-02007-0},
pages = {339--355},
abstract = {One of the central challenges in computational biology is to develop accurate tools for protein structure analysis. Particularly difficult cases of this are sequence alignment and consensus folding of low-homology proteins. In this work, 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 additionally exploits sparsity in the set of likely super-secondary structure pairings and alignment candidates for each amino acid to achieve an effectively cubic running time for simultaneous pairwise alignment and folding. We demonstrate the efficacy of these techniques on transmembrane beta-barrel proteins, an important yet difficult class of proteins with very few available three-dimensional structures. In tests on sequence alignments derived from structure alignments, partiFold-Align is significantly more accurate than current best approaches for pairwise sequence alignment in the difficult case of low sequence homology and improves secondary structure prediction when current approaches fail. Importantly, partiFold-Align does not require training on transmembrane beta-barrel proteins. The generality of these techniques should allow them to be applied to a wide variety of protein structures.}
}
@inproceedings{Moehl:Will:Backofen:PKalign:RECOMB2009,
author = {Mathias M{\"o}hl and Sebastian Will and Rolf Backofen},
title = {Lifting Prediction to Alignment of {RNA} Pseudoknots},
user = {will},
booktitle = {Proc. of the 13th Annual International Conferences on Computational Molecular Biology (RECOMB'09)},
pages = {285--301},
editor = {Serafim Batzoglou},
publisher = {Springer},
location = {Heidelberg},
series = {LNBI},
volume = {5541},
year = {2009},
isbn = {978-3-642-02007-0},
abstract = {Many computational problems concerning RNA pseudoknot structures, most prominently their prediction and alignment, are NP-hard. For structure prediction, several algorithms have been proposed that are restricted to certain classes of pseudoknots in order to run efficiently. We present a general scheme that yields an efficient alignment algorithm for arbitrary classes of pseudoknots that can be predicted efficiently by dynamic programming. Moreover, we show that such an alignment algorithm benefits from restrictions to certain structure classes in the same way as structure prediction algorithms do. We look at five of these classes in greater detail. Compared to the respective structure prediction algorithm, the time and space complexity of the obtained alignment algorithm is increased by only a linear factor. For four of the classes, there do not exist alignment algorithms so far. For the fifth, most general class, our algorithm improves the time complexity compared to the best algorithm known so far, from $O(n^5m^5)$ time to $O(nm^6)$, where $n$ and $m$ are the length of the two aligned sequences. Finally, we apply the fastest of the generated algorithms with complexity $O(nm^4)$ time and $O(nm^2)$ space to comparative de-novo prediction of pseudoknots.}
}
@article{Bernhart:RNAalifold:BMC2008,
author = {Stephan H. Bernhart and Ivo L. Hofacker and Sebastian Will and Andreas R. Gruber and Peter F. Stadler},
title = {{RNAalifold}: improved consensus structure prediction for {RNA} alignments},
journal = {BMC Bioinformatics},
year = {2008},
volume = {9},
pages = {474},
user = {will},
doi = {10.1186/1471-2105-9-474},
pmid = {19014431},
abstract = {Background: The prediction of a consensus structure for a set of related RNAs is an important first step for subsequent analyses. RNAalifold, which computes the minimum energy structure that is simultaneously formed by a set of aligned sequences, is one of the oldest and most widely used tools for this task. In recent years, several alternative approaches have been advocated, pointing to several shortcomings of the original RNAalifold approach. Results: We show that the accuracy of RNAalifold predictions can be improved substantially by introducing a different, more rational handling of alignment gaps, and by replacing the rather simplistic model of covariance scoring with more sophisticated RIBOSUM-like scoring matrices. These improvements are achieved without compromising the computational efficiency of the algorithm. We show here that the new version of RNAalifold not only outperforms the old one, but also several other tools recently developed, on different datasets. Conclusions: The new version of RNAalifold not only can replace the old one for almost any application but it is also competitive with other approaches including those based on SCFGs, maximum expected accuracy, or hierarchical nearest neighbor classifiers.}
}
@inproceedings{Moehl:Will:Backofen:CPM2008,
author = {Mathias M{\"o}hl and Sebastian Will and Rolf Backofen},
title = {Fixed Parameter Tractable Alignment of {RNA} Structures Including Arbitrary Pseudoknots},
booktitle = {Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching (CPM 2008)},
year = {2008},
pages = {69--81},
series = {LNCS},
vol = {5029},
publisher = {Springer-Verlag},
abstract = {We present an algorithm that computes the edit distance of two RNA structures with arbitrary kinds of pseudoknots. A main benefit of the algorithm is that, despite the problem is NP-hard, the algorithmic complexity adapts to the complexity of the RNA structures. Due to fixed parameter tractability, we can guarantee polynomial run-time for a parameter which is small in practice. Our algorithm can be considered as a generalization of the algorithm of Jiang et al.~(Jiang, 2002) to arbitrary pseudoknots. In their absence, it gracefully degrades to the same polynomial algorithm. A prototypical implementation demonstrates the applicability of the method.},
user = {will}
}
@article{Will:Busch:Backofen:_effic_sequen_align_side_const:Constraints2008,
author = {Sebastian Will and Anke Busch and Rolf Backofen},
title = {Efficient Sequence Alignment with Side-Constraints by Cluster Tree Elimination},
journal = {Constraints Journal},
issn = {1383-7133},
volume = {13},
number = {1},
pages = {110--129},
year = {2008},
user = {will},
url = {http://ai.uwaterloo.ca/~vanbeek/Constraints/vol13.html},
abstract = {Aligning DNA and protein sequences is a core technique in molecular biology. Often, it is desirable to include partial prior knowledge and conditions in an alignment. Going beyond prior work, we aim at the integration of such side constraints in free combination into alignment algorithms. The most common and successful technique for efficient alignment algorithms is dynamic programming (DP). However, a weakness of DP is that one cannot include additional constraints without specifically tailoring a new DP algorithm. Here, we discuss a declarative approach that is based on constraint techniques and show how it can be extended by formulating additional knowledge as constraints. We take special care to obtain the efficiency of DP for sequence alignment. This is achieved by careful modeling and applying proper solving strategies. Finally, we apply our method to the scanning for RNA motifs in large sequences. This case study demonstrates how the new approach can be used in real biological problems. A prototypic implementation of the method is available at http://www.bioinf.uni-freiburg.de/Software/CTE-Alignment.},
doi = {10.1007/s10601-007-9032-x}
}
@inproceedings{Otto:Will:Backofen:_struc_local_multip_align_of_rna:CGB08,
author = {Wolfgang Otto and Sebastian Will and Rolf Backofen},
title = {Structure Local Multiple Alignment of {RNA}},
booktitle = {Proceedings of German Conference on Bioinformatics (GCB'2008)},
publisher = {Gesellschaft f{\"u}r Informatik (GI)},
series = {Lecture Notes in Informatics (LNI)},
volume = {P-136},
year = {2008},
pages = {178--188},
isbn = {987-3-88579-230-7},
issn = {1617-5468},
abstract = {Today, RNA is well known to perform important regulatory and catalytical function due to its distinguished structure. Consequentially, structure is conserved in evolution and state-of-the art RNA multiple alignment algorithms consider structure as well as sequence information. However, existing tools neglect the important aspect of locality. Notably, locality in RNA occurs as similarity of subsequences as well as similarity of only substructures. We present a novel approach for multiple alignment of RNAs that deals with both kinds of locality. The approach extends LocARNA by structural locality and delegates the construction of multiple alignments to T-Coffee.
The paper systematically investigates structural locality in known RNA families. Benchmarking multiple alignment tools on structurally local families shows the need for algorithmic support of this locality. The improvement in accuracy in special cases is achieved while staying competitive with state-of-the-art alignment tools across the whole Bralibase.
LocARNA and its T-Coffee extended variant LocARNATE are freely available at http://www.bioinf.uni-freiburg.de/Software/LocARNA/.},
user = {will}
}
@inproceedings{Heyne:Will:Beckstette:Backofen:GCB08,
author = {Heyne, Steffen and Will, Sebastian and Beckstette, Michael and Backofen, Rolf},
title = {Lightweight comparison of {RNAs} based on exact sequence-structure matches},
booktitle = {Proceedings of the German Conference on Bioinformatics (GCB'2008)},
publisher = {Gesellschaft f{\"u}r Informatik (GI)},
series = {Lecture Notes in Informatics (LNI)},
volume = {P-136},
year = {2008},
pages = {189--198},
isbn = {987-3-88579-230-7},
issn = {1617-5468},
abstract = {Specific functions of RNA molecules are often associated to different motifs in the RNA structure. The key feature is that the combination of sequence and structure properties form such an RNA motif. In this paper we introduce a new RNA sequence-structure comparison method which maintains exact matching substructures. Existing common substructures are treated as whole unit while variability is allowed between such structural motifs. Based on a fast detectable set of overlapping and crossing substructure matches for two nested RNA secondary structures, our method computes the longest colinear sequence of substructures common to two RNAs in $O(n^2m^2)$ time and $O(nm)$ space. Applied to different RNAs, our method correctly identifies sequence-structure similarities between two RNAs. The results of our experiments are in good agreement with existing alignment-based methods, but can be obtained in a fraction of running time, in particular for larger RNAs. The proposed algorithm is implemented in the program expaRNA, which is available from our website (www.bioinf.uni-freiburg.de/Software).},
user = {heyne}
}
@article{Mann:Will:Backofen:CPSP-tools:BMCB:2008,
author = {Martin Mann and Sebastian Will and Rolf Backofen},
title = {{CPSP}-tools - Exact and Complete Algorithms for High-throughput {3D} Lattice Protein Studies},
journal = {BMC Bioinformatics},
issn = {1471-2105},
year = {2008},
volume = {9},
pages = {230},
doi = {10.1186/1471-2105-9-230},
user = {mmann},
abstract = {Background: The principles of protein folding and evolution pose problems of very high inherent complexity. Often these problems are tackled using simplified protein models, e.g. lattice proteins. The CPSP-tools package provides programs to solve exactly and completely the problems typical of studies using 3D lattice protein models. Among the tasks addressed are the prediction of (all) globally optimal and/or suboptimal structures as well as sequence design and neutral network exploration. Results: In contrast to stochastic approaches, which are not capable of answering many fundamental questions, our methods are based on fast, non-heuristic techniques. The resulting tools are designed for high-throughput studies of 3D-lattice proteins utilizing the Hydrophobic-Polar (HP) model. The source bundle is freely available at http://www.bioinf.uni-freiburg.de/sw/cpsp/ Conclusions: The CPSP-tools package is the first set of exact and complete methods for extensive, high-throughput studies of non-restricted 3D-lattice protein models. In particular, our package deals with cubic and face centered cubic (FCC) lattices.}
}
@article{Will:etal:_infer_non_codin_rna_famil:PLOS2007,
author = {Sebastian Will and Kristin Reiche and Ivo L. Hofacker and Peter F. Stadler and Rolf Backofen},
title = {Inferring Non-Coding {RNA} Families and Classes by Means of Genome-Scale Structure-Based Clustering},
journal = {PLoS Comput Biol},
year = {2007},
volume = {3},
number = {4},
pages = {e65},
issn = {1553-734X},
pmid = {17432929},
doi = {10.1371/journal.pcbi.0030065},
user = {will},
abstract = {The RFAM database defines families of ncRNAs by means of sequence similarities that are sufficientto establish homology. In some cases, such as microRNAs, box H/ACA snoRNAs, functional commonalities define classes of RNAs that are characterized by structural similarities, and typically consist ofmultiple RNA families. Recent advances in high-throughput transcriptomics and comparative genomics have produced very large sets of putative non-coding RNAs and regulatory RNA signals. For many ofthem, evidence for stabilizing selection acting on their secondary structures has been derived, and at least approximate models of their structures have been computed. The overwhelming majority of these hypo-thetical RNAs cannot be assigned to established families or classes. We present here a structure-based clustering approach that is capable of extracting putative RNA classesfrom genome-wide surveys for structured RNAs. The LocARNA tool implements a novel variant of theSankoff algorithm that is sufficiently fast to deal with several thousand candidate sequences. The method is also robust against false positive predictions, i.e., a contamination of the input data with unstructured ornon-conserved sequences. We have successfully tested the LocARNA-based clustering approach on the sequences of the RFAM-seedalignments. Furthermore, we have applied it to a previously published set of 3332 predicted structured elements in the Ciona intestinalis genomes (Missal et al., Bioinformatics 21(S2), i77-i78). In addition torecovering e.g. tRNAs as a structure-based class, the method identifies several RNA families, including microRNA and snoRNA candidates, and suggests several novel classes of ncRNAs for which to-date norepresentative has been experimentally characterized.}
}
@article{Bompfuenewerer:_variat_rna_foldin_align:JMathB07,
author = {Athanasius F. Bompf{\"u}newerer and Rolf Backofen and Stephan H. Bernhart and Jana Hertel and Ivo L. Hofacker and Peter F. Stadler and Sebastian Will},
title = {Variations on {RNA} folding and alignment: lessons from {Benasque}},
journal = {Journal of Mathematical Biology},
issn = {0303-6812},
year = {2008},
volume = {56},
number = {1-2},
pages = {129--144},
user = {backofen},
pmid = {17611759},
doi = {10.1007/s00285-007-0107-5},
abstract = {Dynamic programming algorithms solve many standard problems of RNA bioinformatics in polynomial time. In this contribution we discuss a series of variations on these standard methods that implement refined biophysical models, such as a restriction of RNA folding to canonical structures, and an extension of structural alignments to an explicit scoring of stacking propensities. Furthermore, we demonstrate that a local structural alignment can be employed for ncRNA gene finding. In this context we discuss scanning variants for folding and alignment algorithms.}
}
@article{BompfuenewererConsortium:RNAs_every_genom:2007,
author = {Athanasius F. Bompf{\"u}newerer Consortium and Backofen, Rolf and Bernhart, Stephan H. and Flamm, Christoph and Fried, Claudia and Fritzsch, Guido and Hackerm{\"u}ller, J{\"o}rg and Hertel, Jana and Hofacker, Ivo L. and Missal, Kristin and Mosig, Axel and Prohaska, Sonja J. and Rose, Dominic and Stadler, Peter F. and Tanzer, Andrea and Washietl, Stefan and Will, Sebastian},
title = {{RNAs} everywhere: genome-wide annotation of structured {RNAs}},
journal = {J Exp Zoolog B Mol Dev Evol},
year = {2007},
volume = {308B},
number = {1},
pages = {1--25},
user = {will},
pmid = {17171697},
doi = {10.1002/jez.b.21130},
issn = {1552-5007},
abstract = {Starting with the discovery of microRNAs and the advent of genome-wide transcriptomics, non-protein-coding transcripts have moved from a fringe topic to a central field research in molecular biology. In this contribution we review the state of the art of "computational RNomics", i.e., the bioinformatics approaches to genome-wide RNA annotation. Instead of rehashing results from recently published surveys in detail, we focus here on the open problem in the field, namely (functional) annotation of the plethora of putative RNAs. A series of exploratory studies are used to provide non-trivial examples for the discussion of some of the difficulties.}
}
@incollection{wscp:chap6:bioinfo,
author = {Alessandro {Dal Pal{\`u}} and Agostino Dovier and Fran{\c{c}}ois Fages and Sebastian Will},
title = {Constraint-based Methods for Bioinformatics},
chapter = {6},
pages = {129--150},
editor = {Fr{\'e}d{\'e}ric Benhamou and Narendra Jussien and Barry O'Sullivan},
booktitle = {Trends in Constraint Programming},
publisher = {ISTE},
year = {2007},
month = {May},
isbn = {9781905209972},
address = {London, UK},
user = {will}
}
@inproceedings{Mann_ELL_BIRD07,
author = {Martin Mann and Sebastian Will and Rolf Backofen},
title = {The Energy Landscape Library - A Platform for Generic Algorithms},
booktitle = {BIRD'07 - 1st international Conference on Bioinformatics Research and Development},
year = {2007},
location = {Berlin, Germany},
volume = {217},
publisher = {Oesterreichische Computer Gesellschaft},
isbn = {978-3-85403-217-5},
pages = {83--86},
abstract = {The study of energy landscapes of biopolymers and their models is an important field in bioinformatics. For instance the investigation of kinetics or folding simulations are done using methods that are based on sampling or exhaustive enumeration. Most of such algorithms are independent of the underlying landscape model. Therefore frameworks for generic algorithms to investigate the landscape properties is needed. Here, we present the Energy Landscape Library (ELL) that allows such a model-independent formulation of generic algorithms dealing with discrete states. The ELL is a completely object-oriented C++ library that is highly modular, easy to extend, and freely available online. It can be used for a fast and easy implementation of new generic algorithms (possibly based on the provided basic method pool) or as a framework to test their properties for different landscape models, which can be formulated straightforward.},
user = {mmann}
}
@article{Backofen:Will:Constraints2006,
author = {Rolf Backofen and Sebastian Will},
title = {A Constraint-Based Approach to Fast and Exact Structure Prediction in Three-Dimensional Protein Models},
journal = {Journal of Constraints},
year = {2006},
url = {http://ai.uwaterloo.ca/~vanbeek/Constraints/constraints.html#volume11},
volume = {11},
number = {1},
pages = {5--30},
publisher = {Springer Netherlands},
issn = {1383-7133 (Paper) 1572-9354 (Online)},
doi = {10.1007/s10601-006-6848-8},
month = {January},
abstract = {Simplified protein models are used for investigating general properties of proteins and principles of protein folding. Furthermore, they are suited for hierarchical approaches to protein structure prediction. A well known protein model is the HPmodel of Lau and Dill [33], which models the important aspect of hydrophobicity. One can define the HP-model for various lattices, among them two-dimensional and three-dimensional ones. Here, we investigate the three-dimensional case. The main motivation for studying simplified protein models is to be able to predict model structures much more quickly and more accurately than is possible for real proteins. However, up to now there was a dilemma: the algorithmically tractable, simple protein models can not model real protein structures with good quality and introduce strong artifacts.
We present a constraint-based method that largely improves this situation. It outperforms all existing approaches for lattice protein folding in HP-models. This approach is the first one that can be applied to two three-dimensional lattices, namely the cubic lattice and the face-centered-cubic (FCC ) lattice. Moreover, it is the only exact method for the FCC lattice. The ability to use the FCC lattice is a significant improvement over the cubic lattice. The key to our approach is the ability to compute maximally compact sets of points (used as hydrophobic cores), which we accomplish for the first time for the FCC lattice.
Keywords: protein structure prediction, HP-model, face-centered cubic lattice, constraint programming},
user = {will}
}
@article{Wolfinger:etal:_explor:EPL2006,
author = {Michael T. Wolfinger and Sebastian Will and Ivo L. Hofacker and Rolf Backofen and Peter F. Stadler},
title = {Exploring the lower part of discrete polymer model energy landscapes},
journal = {Europhysics Letters},
year = {2006},
pages = {725--732},
volume = {74},
number = {4},
doi = {10.1209/epl/i2005-10577-0},
publists = {All},
user = {will},
abstract = {We present a generic, problem independent algorithm for exploration of the lowenergy portion of the energy landscape of discrete systems and apply it to the energy landscape of lattice proteins. Starting from a set of optimal and near-optimal conformations derived from a constraint-based search technique, we are able to selectively investigate the lower part of lattice protein energy landscapes in two and three dimensions. This novel approach allows, in contrast to exhaustive enumeration, for an eOEcient calculation of optimal and near-optimal structures below a given energy threshold and is only limited by the available amount of memory. A straightforward application of the algorithm is calculation of barrier trees (representing the energy landscape), which then allows dynamics studies based on landscape theory.}
}
@article{Busch:Will:Backofen:Bioinformatics2005,
author = {Anke Busch and Sebastian Will and Rolf Backofen},
title = {{SECISDesign}: a server to design {SECIS}-elements within the coding sequence},
journal = {Bioinformatics},
issn = {1460-2059},
year = {2005},
volume = {21},
number = {15},
pages = {3312--3},
publists = {All and Anke Busch and Sebastian Will and Rolf Backofen},
user = {backofen},
pmid = {15919727},
abstract = {SUMMARY: SECISDesign is a server for the design of SECIS-elements and arbitrary RNA-elements within the coding sequence of an mRNA. The element has to satisfy both structure and sequence constraints. At the same time, a certain amino acid similarity to the original protein has to be kept. The designed sequence can be used for recombinant expression of selenoproteins in Escherichia coli. AVAILABILITY: The server is available at http://www.bio.inf.uni-jena.de/Software/SECISDesign/index.html.}
}
@article{Backofen:Will:_local_sequence_structure:JBCB2004,
author = {Rolf Backofen and Sebastian Will},
title = {Local Sequence-Structure Motifs in {RNA}},
journal = {Journal of Bioinformatics and Computational Biology (JBCB)},
year = {2004},
pages = {681--698},
volume = {2},
number = {4},
publisher = {Imperial College Press},
abstract = {Ribonuclic acid (RNA) enjoys increasing interest in molecular biology; despite this interest fundamental algorithms are lacking, e.g. for identifying local motifs. As proteins, RNA molecules have a distinctive structure. Therefore, in addition to sequence information, structure plays an important part in assessing the similarity of RNAs. Furthermore, common sequence-structure features in two or several RNA molecules are often only spatially local, where possibly large parts of the molecules are dissimilar. Consequently, we address the problem of comparing RNA molecules by computing an optimal local alignment with respect to sequence and structure information. While local alignment is superior to global alignment for identifying local similarities, no general local sequence-structure alignment algorithms are currently known. We suggest a new general definition of locality for sequence-structure alignments that is biologically motivated and efficiently tractable. To show the former, we discuss locality of RNA and prove that the defined locality means connectivity by atomic and non-atomic bonds. To show the latter, we present an efficient algorithm for the newly defined pairwise local sequence-structure alignment (lssa) problem for RNA. For molecules of lengthes n and m, the algorithm has worst-case time complexity of $O(n^2m^2max(n,m))$ and a space complexity of only $O(nm)$. An implementation of our algorithm is available at http://www.bio.inf.uni-jena.de. Its runtime is competitive with global sequence-structure alignment.
Keywords: RNA; local alignment; local sequence-structure alignment; lssa},
user = {will},
pmid = {15617161},
url = {http://www.worldscinet.com/jbcb/02/0204/S0219720004000818.html}
}
@inproceedings{Will:Backofen:SymCon2003,
author = {Sebastian Will and Rolf Backofen},
title = {Breaking of Partial Symmetries in the Photo and Alignment Problem},
booktitle = {Proceedings of the Third International Workshop on Symmetry in Constraint Satisfaction Problems (SymCon 2003)},
pages = {187--194},
year = {2003},
editor = {Barbara Smith and Ian Gent and Warwick Harvey},
user = {will},
abstract = {Symmetry breaking by adding symmetric constraints during search usually assumes that symmetric constraints are simple. We identify symmetries with complex symmetric constraints, where the symmetries nevertheless can be handled by a similar method. For this aim, we introduce partial symmetries. We identify those symmetries in two problems. The photo problem is a well known example problem, while the alignment problem is a real world problem from bioinformatics.}
}
@inproceedings{Backofen:Will:_const_based_approac_struc_predic:ICLP2003,
author = {Rolf Backofen and Sebastian Will},
title = {A Constraint-Based Approach to Structure Prediction for Simplified Protein Models that Outperforms Other Existing Methods},
booktitle = {Proceedings of the 19th International Conference on Logic Programming (ICLP 2003)},
year = {2003},
series = {Lecture Notes in Computer Science},
volume = {2916},
publisher = {Springer},
pages = {49--71},
user = {will},
abstract = {Lattice protein models are used for hierarchical approaches to protein structure prediction, as well as for investigating general principles of protein folding. So far, one has the problem that either the lattice does not model real protein conformations with good quality, or there is no efficient method known for finding native conformations. We present a constraint-based method that largely improves this situ- ation. It outperforms all existing approaches in lattice protein folding on the type of model we have chosen (namely the HP-model by Lau and Dill[34], which models the important aspect of hydrophobicity). It is the only exact method that has been applied to two different lattices. Furthermore, it is the only exact method for the face-centered cubic lattice. This lattice is important since it has been shown [38] that the FCC lattice can model real protein conformations with coordinate root mean square deviation below 2 Angstrom. Our method uses a constraint-based approach. It works by first calculating maximally compact sets of points (hydrophobic cores), and then threading the given HP-sequence to the hydrophobic cores such that the core is occupied by H-monomers.}
}
@article{Bac:Wil:Constraints2002,
author = {Rolf Backofen and Sebastian Will},
title = {Excluding symmetries in constraint-based search},
year = {2002},
journal = {Constraints},
volume = {7},
number = {3},
pages = {333--349},
publisher = {Kluwer Academic Publishers},
abstract = {We introduce a new method for excluding symmetries in constraint based search. To our knowledge, it is the first declarative method that can be applied to {\em arbitrary} symmetries. Our method is based on the notion of symmetric constraints, which are used in our modification of a general constraint based search algorithm. The method does not influence the search strategy. Furthermore, it can be used with either the full set of symmetries, or with an subset of all symmetries. We proof correctness, completeness and symmetry exclusion properties of our method. Then, we show how to apply the method in the special case of geometric symmetries (rotations and reflections) and permutation symmetries. Furthermore, we give results from practical applications.},
user = {will}
}
@inproceedings{Will:PSB2002,
author = {Sebastian Will},
title = {Constraint-based Hydrophobic Core Construction for Protein Structure Prediction in the Face-Centered-Cubic Lattice},
booktitle = {Proceedings of the Pacific Symposium on Biocomputing 2002 (PSB 2002)},
editor = {Russ B. Altman and A. Keith Dunker and Lawrence Hunter and Teri E. Klein},
publisher = {World Scientific Publishing Co. Pte. Ltd.},
address = {Singapore},
year = {2002},
pages = {661--672},
pmid = {11928518},
abstract = {We present an algorithm for exact protein structure prediction in the FCC-HP-model. This model is a lattice protein model on the face-centered-cubic lattice that models the main force of protein folding, namely the hydrophobic force. The structure prediction for this model can be based on the construction of hydrophobic cores. The main focus of the paper is on an algorithm for constructing maximally and submaximally compact hydrophobic cores of a given size. This algorithm treats core construction as a constraint satisfaction problem (CSP), and the paper describes its constraint model. The algorithm employs symmetry excluding constraint-based search [Backofen, Will: CP99] and relies heavily on good upper bounds on the number of contacts. Here, we use and strengthen upper bounds presented earlier. [Backofen, Will: CPM2001] The resulting structure prediction algorithm (including previous work [Backofen, Will: CPM2001, Backofen, Will: CP2001]) handles sequences of sizes in the range of real proteins fast, i.e. we predict a first structure often within a few minutes. The algorithm is the first exact one for the FCC, besides full enumeration which is impracticable for chain lengths greater than about 15. We tested the algorithm succesfully up to sequence length of 160, which is far beyond the capabilities even of previous heuristic approaches.},
user = {will}
}
@inproceedings{Bac:Wil:CPM2001,
author = {Rolf Backofen and Sebastian Will},
title = {Optimally Compact Finite Sphere Packings --- Hydrophobic Cores in the {FCC}},
booktitle = {Proc. of the 12th Annual Symposium on Combinatorial Pattern Matching ({CPM2001})},
year = {2001},
series = {Lecture Notes in Computer Science},
volume = {2089},
address = {Berlin},
publisher = {Springer-Verlag},
pages = {257--272},
isbn = {3-540-42271-4},
abstract = {Lattice protein models are used for hierarchical approaches to protein structure prediction, as well as for investigating principles of protein folding. The problem is that there is so far no known lattice that can model real protein conformations with good quality, \emph{and} for which there is an efficient method to prove whether a conformation found by some heuristic algorithm is optimal. We present such a method for the FCC-HP-Model [Agarwala et al., JCB 97]. For the FCC-HP-Model, we need to find conformations with a maximally compact hydrophobic core. Our method allows us to enumerate maximally compact hydrophobic cores for sufficiently great number of hydrophobic amino-acids. We have used our method to prove the optimality of heuristically predicted structures for HP-sequences in the FCC-HP-model.},
user = {will}
}
@inproceedings{Bac:Wil:CP2001,
author = {Rolf Backofen and Sebastian Will},
title = {Fast, Constraint-based Threading of {HP}-Sequences to Hydrophobic Cores},
booktitle = {Proc. of the 7th International Conference on Principle and Practice of Constraint Programming (CP'2001)},
series = {Lecture Notes in Computer Science},
volume = {2239},
address = {Berlin},
publisher = {Springer-Verlag},
year = {2001},
pages = {494--508},
isbn = {3-540-42863-1},
abstract = {Lattice protein models are used for hierarchical approaches to protein structure prediction, as well as for investigating principles of protein folding. So far, one has the problem that there exists no lattice that can model real protein conformations with good quality \emph{and} for which an efficient method to find native conformations is known. We present the first method for the FCC-HP-Model [Agarwala et al., JCB 97] that is capable of finding native conformations for real-sized HP-sequences. It has been shown [Park and Levitt, JMB 95] that the FCC lattice can model real protein conformations with coordinate root mean square deviation below 2 \AA. Our method uses a constraint-based approach. It works by first calculating maximally compact sets of points (hydrophobic cores), and then threading the given HP-sequence to the hydrophobic cores such that the core is occupied by H-monomers. },
user = {will}
}
@inproceedings{Bac:Wil:Clo:PSB2000,
author = {Rolf Backofen and Sebastian Will and Peter Clote},
title = {Algorithmic approach to quantifying the hydrophobic force contribution in protein folding},
booktitle = {Proceedings of the Pacific Symposium on Biocomputing (PSB 2000)},
editor = {Russ B. Altman and A. Keith Dunker and Lawrence Hunter and Teri E. Klein},
pages = {92--103},
year = {2000},
volume = {5},
abstract = {Though the electrostatic, ionic, van der Waals, Lennard-Jones, hydrogen bonding, and other forces play an important role in the energy function minimized at a protein's native state, it is widely believed that the {\em hydrophobic force} is the dominant term in protein folding. In this paper, we attempt to quantify the extent to which the hydrophobic force determines the positions of the backbone $\alpha$-carbon atoms in PDB data, by applying Monte-Carlo and genetic algorithms to determine the predicted conformation with minimum energy, where only the hydrophobic force is considered (i.e. Dill's HP-model, and refinements using Woese's polar requirement). This is done by computing the root mean square deviation between the normalized distance matrix $D = (d_{i,j})$ ($d_{i,j}$ is normalized Euclidean distance between residues $r_i$ and $r_j$) for PDB data with that obtained from the output of our algorithms. Our program was run on the database of ancient conserved regions drawn from GenBank 101 generously supplied by W. Gilbert's lab, as well as medium-sized proteins (E. Coli RecA, 2reb, Erythrocruorin, 1eca, and Actinidin 2act). The root mean square deviation (RMSD) between distance matrices derived from the PDB data and from our program output is quite small, and by comparison with RMSD between PDB data and random coils, allows a quantification of the hydrophobic force contribution Keywords: lattice, face-centered-cubic, hydrophobic force, automorphism },
user = {will}
}
@inproceedings{Abdennadher:Saft:Will:PACLP00,
author = {Slim Abdennadher and Matthias Saft and Sebastian Will},
title = {Classroom Assignment using Constraint Logic Programming},
booktitle = {Proceedings of the Second International Conference and Exhibition on The Practical Application of Constraint Technologies and Logic Programming (PACLP 2000)},
year = {2000},
abstract = {The Classroom Assignment problem consists of scheduling a set of courses into a fixed number of rooms, given a fixed timetable. At the University of Munich, a classroom plan has to be created each semester after collecting timetables of all departments and wishes of teachers. This planning is very complex since a lot of constraints have to be met, e.g. room size and equipment. Using constraint-based programming, we developed a prototype, called RoomPlan, that supports automatic creation of classroom plans. With RoomPlan a schedule can be created interactively within some minutes instead of some days. RoomPlan was presented at the Systems'99 Computer exhibition in Munich.},
user = {will}
}
@article{Bac:Wil:Bor:BioInfo99,
author = {Rolf Backofen and Sebastian Will and Erich Bornberg-Bauer},
title = {Application of Constraint Programming Techniques for Structure Prediction of Lattice Proteins with Extended Alphabets},
journal = {Bioinformatics},
year = {1999},
volume = {15},
number = {3},
pages = {234--242},
abstract = {Predicting the ground state of biopolymers is a notoriously hard problem in biocomputing. Model systems, such as lattice proteins are simple tools and valuable to test and improve new methods. Best known are HP-type models with sequences composed from a binary (hydrophobic and polar) alphabet. Major drawback is the degeneracy, i.e. the number of different ground state conformations. Here we show how recently developed constraint programming techniques can be used to solve the structure prediction problem efficiently for a higher order alphabet. To our knowledge it is the first report of an exact and computationally feasible solution to model proteins of length up to 36 and without resorting to maximally compact states. We further show that degeneracy is reduced by more than one order of magnitude and that ground state conformations are not necessarily compact. Therefore, more realistic protein simulations become feasible with our model.},
user = {will}
}
@inproceedings{Bac:Wil:CP99,
author = {Rolf Backofen and Sebastian Will},
title = {Excluding Symmetries in Constraint-Based Search},
booktitle = {Proceedings of the 5th International Conference on Principle and Practice of Constraint Programming (CP'99)},
pages = {73--87},
editor = {Joxan Jaffar},
volume = {1713},
series = {Lecture Notes in Computer Science},
address = {Berlin},
publisher = {Springer-Verlag},
year = {1999},
abstract = { We introduce a new method for excluding symmetries in constraint based search. To our knowledge, it is the first declarative method that can be applied to {\em arbitrary} symmetries. Our method is based on the notion of symmetric constraints, which are used in our modification of a general constraint based search algorithm. The method does not influence the search strategy. Furthermore, it can be used with either the full set of symmetries, or with an subset of all symmetries. We proof correctness, completeness and symmetry exclusion properties of our method. We then show how to apply the method in the special case of geometric symmetries (rotations and reflections) and permutation symmetries. Furthermore, we give results from practical applications. },
user = {will}
}
@inproceedings{Bac:Wil:Clo:GCB99,
author = {Rolf Backofen and Sebastian Will and Peter Clote},
title = {Algorithmic approach to quantifying the hydrophobic force contribution in protein folding},
booktitle = {Proceedings of the German Conference on Bioinformatics (GCB'99)},
pages = {93--106},
year = {1999},
note = {http://www.bioinfo.de/isb/gcb99},
abstract = { Though the electrostatic, ionic, van der Waals, Lennard-Jones, hydrogen bonding, and other forces play an important role in the energy function minimized at a protein's native state, it is widely believed that the {\em hydrophobic force} is the dominant term in protein folding. In this paper, we attempt to quantify the extent to which the hydrophobic force determines the positions of the backbone $\alpha$-carbon atoms in PDB data, by applying Monte-Carlo and genetic algorithms to determine the predicted conformation with minimum energy, where only the hydrophobic force is considered (i.e. Dill's HP-model, and refinements using Woese's polar requirement). This is done by computing the root mean square deviation between the normalized distance matrix $D = (d_{i,j})$ ($d_{i,j}$ is normalized Euclidean distance between residues $r_i$ and $r_j$) for PDB data with that obtained from the output of our algorithms. Our program was run on the database of ancient conserved regions drawn from GenBank 101 generously supplied by W. Gilbert's lab, as well as medium-sized proteins (E. Coli RecA, 2reb, Erythrocruorin, 1eca, and Actinidin 2act). The root mean square deviation (RMSD) between distance matrices derived from the PDB data and from our program output is quite small, and by comparison with RMSD between PDB data and random coils, allows a quantification of the hydrophobic force contribution The final version of this paper will appear in the proceedings of PSB'2000. Keywords: lattice, face-centered-cubic, hydrophobic force, automorphism},
user = {will}
}
@inproceedings{Bac:Wil:GCB98,
author = {Rolf Backofen and Sebastian Will},
title = {Structure Prediction in an {HP}-type Lattice with an Extended Alphabet},
booktitle = {Proc of German Conference on Bioinformatics (GCB'98)},
year = {1998},
abstract = { The protein structure prediction problem is one of the most important problems in computational biology. This problem consists of finding the conformation of a protein (given by a sequence of amino-acids) with minimal energy. Because of the complexity of this problem, simplified models like Dill's HP-lattice model have become a major tool for investigating general properties of protein folding. Even for this simplified model, the structure prediction problem has been proven to be NP-complete. A disadvantage of the HP-problem is its high degeneracy. I.e., for every sequence there are a lot of conformations having the minimal energy. For this reason, extended alphabets have been used in the literature. One of these alphabets is the HPNX-alphabet, which considers hydrophobic amino acids as well as positive and negative charged ones. In this paper, we describe an exact algorithm for solving the structure prediction problem for the HPNX-alphabet. To our knowledge, our algorithm is the first exact one for finding the minimal conformation of an lattice protein in a lattice model with an alphabet more complex than HP. We also compare our results with results as given for the HP-model. },
user = {will}
}