The longest common subsequence problem for sequences with nested arc annotations.

DOI10.1016/S0022-0000(02)00004-1zbMath1059.68023OpenAlexW2067194564MaRDI QIDQ1872715

Jianjun Wen, Zhi-Zhong Chen, Tao Jiang, Guo-Hui Lin

Publication date: 14 May 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(02)00004-1

zbMATH Keywords

NP-hardnessApproximation algorithmLongest common subsequenceBook embeddingPolynomial-time approximation schemeSequence annotation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Protein sequences, DNA sequences (92D20) Approximation algorithms (68W25)

Related Items (10)

On the ordered list subgraph embedding problems ⋮ Computing the similarity of two sequences with nested arc annotations ⋮ A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs ⋮ The longest common subsequence problem for arc-annotated sequences ⋮ A metric for rooted trees with unlabeled vertices based on nested parentheses ⋮ A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes ⋮ Fast arc-annotated subsequence matching in linear space ⋮ Approximation of RNA multiple structural alignment ⋮ Algorithms for computing variants of the longest common subsequence problem ⋮ Parameterized Complexity of the Arc-Preserving Subsequence Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Embedding planar graphs in four pages
• Some simplified NP-complete graph problems
• On triangulating planar graphs under the four-connectivity constraint
• Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
• The Complexity of Coloring Circular Arcs and Chords
• Algorithms for the Longest Common Subsequence Problem
• Algorithms on Strings, Trees and Sequences
• Approximation algorithms for NP-complete problems on planar graphs
• Efficient Approximation Schemes for Maximization Problems onK3,3-free orK5-free Graphs
• The String-to-String Correction Problem
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Near optimal multiple alignment within a band in polynomial time

This page was built for publication: The longest common subsequence problem for sequences with nested arc annotations.