Computing the similarity of two sequences with nested arc annotations

DOI10.1016/j.tcs.2003.10.026zbMath1087.68040OpenAlexW2136740638MaRDI QIDQ1884953

Jiong Guo, Jens Gramm, Rolf Niedermeier, Jochen Alber

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.10.026

zbMATH Keywords

NP-completenessRNA secondary structureFixed-parameter tractabilityLongest common subsequenceArc-annotated sequencesSearch tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Protein sequences, DNA sequences (92D20)

Related Items (5)

On the ordered list subgraph embedding problems ⋮ A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs ⋮ Fast arc-annotated subsequence matching in linear space ⋮ Parameterized Complexity of the Arc-Preserving Subsequence Problem ⋮ Improved algorithms for largest cardinality 2-interval pattern problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The parameterized complexity of sequence alignment and consensus
• Computing similarity between RNA structures
• Parameterized complexity of finding subgraphs with hereditary properties.
• The longest common subsequence problem for sequences with nested arc annotations.
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• New methods for 3-SAT decision and worst-case analysis
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• Algorithms on Strings, Trees and Sequences
• Longest common subsequences
• Near optimal multiple alignment within a band in polynomial time
• Faster exact algorithms for hard problems: A parameterized point of view

This page was built for publication: Computing the similarity of two sequences with nested arc annotations