Extending the Hardness of RNA Secondary Structure Comparison

DOI10.1007/978-3-540-74450-4_13MaRDI QIDQ3611904zbMATH OpenOpenAlexWikidataFDO

Authors Guillaume Blin, Guillaume Fertin, Irena Rusu, Christine Sinoquet

Publication date 3 March 2009

Published in Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74450-4_13

zbMATH Keywords

arc-annotated sequencescomputational biologyedit distanceNP-hardnessRNA structures

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Biochemistry, molecular biology (92C40) Systems biology, networks (92C42)

Recommendations

• Comparing RNA structures with biologically relevant operations cannot be done without strong combinatorial restrictions
• What Makes the Arc-Preserving Subsequence Problem Hard?
• The longest common subsequence problem for sequences with nested arc annotations.
• A new algorithm for computing similarity between RNA structures
• Fixed Parameter Tractable Alignment of RNA Structures Including Arbitrary Pseudoknots

Cited in

(7)

• RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm.
• Hardness of RNA folding problem with four symbols
• Comparing RNA structures with biologically relevant operations cannot be done without strong combinatorial restrictions
• Hardness of RNA folding problem with four symbols
• A new algorithm for computing similarity between RNA structures
• A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes
• Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm

This page was built for publication: Extending the Hardness of RNA Secondary Structure Comparison

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