Sparse RNA folding: time and space efficient algorithms

DOI10.1016/j.jda.2010.09.001zbMath1216.92033OpenAlexW2064714768MaRDI QIDQ533404

Dekel Tsur, Rolf Backofen, 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

zbMATH Keywords

dynamic programmingtime complexitysparsificationspace complexityRNA folding

Mathematics Subject Classification ID

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

Related Items (7)

A Sparsified Four-Russian Algorithm for RNA Folding ⋮ RNA secondary structures in a polymer-zeta model how foldings should be shaped for sparsification to establish a linear speedup ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ The rainbow spectrum of RNA secondary structures ⋮ Unnamed Item ⋮ The block spectrum of RNA pseudoknot structures ⋮ Unnamed Item

Uses Software

• Mfold
• CONTRAfold

Cites Work

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

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