Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots

DOI10.1016/S0166-218X(00)00186-4zbMath0956.92019MaRDI QIDQ1585319

Tatsuya Akutsu

Publication date: 17 March 2001

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

zbMATH Keywords

approximation algorithmRNA secondary structurepseudoknot

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Dynamic programming (90C39) Biochemistry, molecular biology (92C40) Complexity and performance of numerical algorithms (65Y20) Computational methods for problems pertaining to biology (92-08)

Related Items (22)

Algebraic dynamic programming for multiple context-free grammars ⋮ Local connectivity of neutral networks ⋮ Polynomial algorithms for protein similarity search for restricted mRNA structures ⋮ Classifying RNA pseudoknotted structures ⋮ Pseudoknot-generating operation ⋮ Posets and Spaces of $k$-Noncrossing RNA Structures ⋮ Combinatorics of RNA structures with pseudoknots ⋮ New approximation algorithms for RNA secondary structures prediction problems by local search ⋮ Approximating the 2-interval pattern problem ⋮ Rapid ab initio prediction of RNA pseudoknots via graph tree decomposition ⋮ Predicting RNA secondary structures with pseudoknots by MCMC sampling ⋮ Asymptotic enumeration of RNA structures with pseudoknots ⋮ Fatgraph models of RNA structure ⋮ Unnamed Item ⋮ Moduli spaces and macromolecules ⋮ Fixed-parameter algorithms for protein similarity search under mRNA structure constraints ⋮ Computational prediction of nucleic acid secondary structure: Methods, applications, and challenges ⋮ Combinatorial design of pseudoknot RNA ⋮ Unnamed Item ⋮ Stacks in canonical RNA pseudoknot structures ⋮ Tree adjoining grammars for RNA structure prediction ⋮ A new method for prediction of RNA secondary structure with pseudoknots, based on helix removal and refinement

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• RNA secondary structures and their prediction
• Dynamic programming with convexity, concavity and sparsity
• Planar graphs: Theory and algorithms
• RNA secondary structure: a complete mathematical analysis
• TAL recognition in \(O(M(n^2))\) time
• Approximation and exact algorithms for RNA secondary structure prediction and recognition of stochastic context-free languages
• The Complexity of Some Problems on Subsequences and Supersequences

This page was built for publication: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots