Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems

DOI10.1137/0145048zbMath0581.92012OpenAlexW2095145214WikidataQ115188651 ScholiaQ115188651MaRDI QIDQ3705254

David Sankoff

Publication date: 1985

Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0145048

zbMATH Keywords

biological sequencesphylogenetic treeRNA foldingnew algorithmalignment of finite sequencesancestral sequencesinference of RNA secondary structureprotosequence problems

Mathematics Subject Classification ID

Dynamic programming (90C39) Genetics and epigenetics (92D10) Computational methods for problems pertaining to biology (92-08) Physiological, cellular and medical topics (92Cxx)

Related Items (28)

The longest common subsequence problem for sequences with nested arc annotations. ⋮ A genetic algorithm on multiple sequences alignment problems in biology ⋮ Rapid dynamic programming algorithms for RNA secondary structure ⋮ Algebraic dynamic programming for multiple context-free grammars ⋮ The parameterized complexity of sequence alignment and consensus ⋮ The longest common subsequence problem for arc-annotated sequences ⋮ Forest alignment with affine gaps and anchors, applied in RNA structure comparison ⋮ Approximation algorithms for multiple sequence alignment ⋮ Fixed Parameter Tractable Alignment of RNA Structures Including Arbitrary Pseudoknots ⋮ New approximation algorithms for RNA secondary structures prediction problems by local search ⋮ Speeding up the dynamic algorithm for planar RNA folding ⋮ Lock-free parallel dynamic programming ⋮ Computational methods in noncoding RNA research ⋮ Variations on RNA folding and alignment: Lessons from Benasque ⋮ PSSMTS: Position specific scoring matrices on tree structures ⋮ Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems ⋮ Efficient sequence alignment with side-constraints by cluster tree elimination ⋮ A phase transition for the minimum free energy of secondary structures of a random RNA ⋮ Partially local multi-way alignments ⋮ Fast RNA structure alignment for crossing input structures ⋮ Sparse RNA folding: time and space efficient algorithms ⋮ Evolutionary rate variation and RNA secondary structure prediction ⋮ Cofolga: a genetic algorithm for finding the common folding of two RNAs ⋮ Modeling and predicting all-\(\alpha\) transmembrane proteins including helix-helix pairing ⋮ Unnamed Item ⋮ Fast RNA Structure Alignment for Crossing Input Structures ⋮ Sparse RNA Folding: Time and Space Efficient Algorithms ⋮ A polyhedral approach to sequence alignment problems

This page was built for publication: Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems