What Makes the Arc-Preserving Subsequence Problem Hard?

DOI10.1007/11567752_1MaRDI QIDQ5449952zbMATH OpenOpenAlexFDO

Authors Guillaume Blin, Guillaume Fertin, Romeo Rizzi, Stéphane Vialette

Publication date 19 March 2008

Published in Transactions on Computational Systems Biology II (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.74.634

zbMATH Keywords

Arc-Preserving Subsequence problemComputational complexityRNA structures

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Biochemistry, molecular biology (92C40)

Recommendations

• Computational Science – ICCS 2005
• A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs
• Arc-preserving subsequences of arc-annotated sequences
• scientific article; zbMATH DE number 1754611
• The longest common subsequence problem for sequences with nested arc annotations.

Cited in

(5)

• Fast arc-annotated subsequence matching in linear space
• Parameterized complexity of the arc-preserving subsequence problem
• Extending the Hardness of RNA Secondary Structure Comparison
• Computational Science – ICCS 2005
• Finding common structured patterns in linear graphs

This page was built for publication: What Makes the Arc-Preserving Subsequence Problem Hard?

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