Rapid dynamic programming algorithms for RNA secondary structure

DOI10.1016/0196-8858(86)90025-4zbMath0607.92012OpenAlexW2143766500MaRDI QIDQ1086193

Temple F. Smith, Michael S. Waterman

Publication date: 1986

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-8858(86)90025-4

zbMATH Keywords

polynomial time algorithmbiochemistrylinear RNA sequencenew dynamic programming algorithmsPrediction of RNA secondary structure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Physiological, cellular and medical topics (92Cxx)

Related Items

Linear trees and RNA secondary structure, Sequence comparison with concave weighting functions, Topological language for RNA, The rainbow spectrum of RNA secondary structures, Perspectives of Monge properties in optimization, Combinatorics of RNA structures with pseudoknots, Monge properties of sequence alignment, Speeding up the dynamic algorithm for planar RNA folding, An optimal algorithm with unknown time complexity for convex matrix searching, Asymptotic enumeration of RNA structures with pseudoknots, A phase transition for the minimum free energy of secondary structures of a random RNA, Dynamic programming with convexity, concavity and sparsity, RNA pseudoknot structures with arc-length \(\geq 3\) and stack-length \(\geq \sigma \), Loop homology of bi-secondary structures, RNA folding and large \(N\) matrix theory, Central and local limit theorems for RNA structures, Loop homology of bi-secondary structures. II, General combinatorics of RNA secondary structure

Cites Work

• Unnamed Item
• RNA secondary structures and their prediction
• A distance geometry program for determining the structures of small proteins and other macromolecules from nuclear magnetic resonance measurements of intramolecular \({}^ 1H-^ 1H\) proximities in solution
• RNA secondary structure: a complete mathematical analysis
• On some new sequences generalizing the Catalan and Motzkin numbers
• Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
• Algorithms for Loop Matchings