A sparsified Four-Russian algorithm for RNA folding

DOI10.1007/978-3-662-48221-6_20zbMATH Open1367.92088OpenAlexW2238936896MaRDI QIDQ5283833FDOQ5283833

Authors: Yelena Frid, Dan Gusfield 

Publication date: 25 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48221-6_20

Recommendations

• Sparse RNA folding: time and space efficient algorithms
• Sparse RNA Folding: Time and Space Efficient Algorithms
• Sparse RNA folding revisited: space-efficient minimum free energy prediction
• RNA secondary structures in a polymer-zeta model how foldings should be shaped for sparsification to establish a linear speedup
• Speedup of RNA pseudoknotted secondary structure recurrence computation with the four-Russians method

zbMATH Keywords

Four-Russian algorithmsecondary structure prediction problem

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Computational methods for problems pertaining to biology (92-08)

Cites Work

• Biological Sequence Analysis
• Faster all-pairs shortest paths via circuit complexity
• RNA secondary structure: a complete mathematical analysis
• Algorithms for Loop Matchings
• Speeding up the four Russians algorithm by about one more logarithmic factor
• Matrix-vector multiplication in sub-quadratic time (some preprocessing required)
• Approximation and exact algorithms for RNA secondary structure prediction and recognition of stochastic context-free languages
• Sparse RNA Folding: Time and Space Efficient Algorithms
• Sparse RNA folding: time and space efficient algorithms
• Title not available (Why is that?)
• RNA secondary structures and their prediction
• Speedup of RNA pseudoknotted secondary structure recurrence computation with the four-Russians method

Cited In (7)

• Sparse RNA folding: time and space efficient algorithms
• 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
• Title not available (Why is that?)
• SparseRNAFoID: sparse RNA pseudoknot-free folding including dangles
• Sparse RNA Folding: Time and Space Efficient Algorithms
• Speedup of RNA pseudoknotted secondary structure recurrence computation with the four-Russians method

This page was built for publication: A sparsified Four-Russian algorithm for RNA folding

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