A sparsified Four-Russian algorithm for RNA folding

DOI10.1007/978-3-662-48221-6_20MaRDI QIDQ5283833zbMATHOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(7)

• Sparse RNA Folding: Time and Space Efficient Algorithms
• Speedup of RNA pseudoknotted secondary structure recurrence computation with the four-Russians method
• SparseRNAFoID: sparse RNA pseudoknot-free folding including dangles
• scientific article; zbMATH DE number 6411942 (Why is no real title available?)
• 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
• Sparse RNA folding: time and space efficient algorithms

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)