Sparse RNA folding: time and space efficient algorithms

DOI10.1016/J.JDA.2010.09.001zbMATH Open1216.92033OpenAlexW2064714768MaRDI QIDQ533404FDOQ533404

Authors: Rolf Backofen, Dekel Tsur, Shay Zakov, Michal Ziv-Ukelson 

Publication date: 3 May 2011

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2010.09.001

Recommendations

• Sparse RNA Folding: Time and Space Efficient Algorithms
• Sparse RNA folding revisited: space-efficient minimum free energy prediction
• A sparsified Four-Russian algorithm for RNA folding
• Efficient computation of RNA folding dynamics
• Speeding up the dynamic algorithm for planar RNA folding

zbMATH Keywords

dynamic programmingsparsificationspace complexitytime complexityRNA folding

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Biochemistry, molecular biology (92C40) Analysis of algorithms (68W40)

Cites Work

• Biological Sequence Analysis
• A linear space algorithm for computing maximal common subsequences
• Recognition and parsing of context-free languages in time n3
• Research in Computational Molecular Biology
• Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
• An Improved Context-Free Recognizer
• RNA secondary structure: a complete mathematical analysis
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• Algorithms for the Longest Common Subsequence Problem
• Algorithms in bioinformatics. 10th international workshop, WABI 2010, Liverpool, UK, September 6--8, 2010. Proceedings
• New clique and independent set algorithms for circle graphs
• Approximation and exact algorithms for RNA secondary structure prediction and recognition of stochastic context-free languages
• A Study of Accessible Motifs and RNA Folding Complexity
• Sparse RNA Folding: Time and Space Efficient Algorithms
• Title not available (Why is that?)
• A faster and more space-efficient algorithm for inferring arc-annotations of RNA sequences through alignment

Cited In (12)

• Title not available (Why is that?)
• If the current clique algorithms are optimal, so is Valiant's parser
• RNA secondary structures in a polymer-zeta model how foldings should be shaped for sparsification to establish a linear speedup
• Sparse RNA folding revisited: space-efficient minimum free energy prediction
• A sparsified Four-Russian algorithm for RNA folding
• Towards hardness of approximation for polynomial time problems
• The rainbow spectrum of RNA secondary structures
• SparseRNAFoID: sparse RNA pseudoknot-free folding including dangles
• Sparse RNA Folding: Time and Space Efficient Algorithms
• Hardness of RNA folding problem with four symbols
• Hardness of RNA folding problem with four symbols
• The block spectrum of RNA pseudoknot structures

Uses Software

• Mfold
• CONTRAfold

This page was built for publication: Sparse RNA folding: time and space efficient algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q533404)