The longest common subsequence problem for arc-annotated sequences

DOI10.1016/S1570-8667(03)00080-7zbMATH Open1118.68756MaRDI QIDQ876717FDOQ876717

Bin Ma, Kaizhong Zhang, Guohui Lin, Tao Jiang

Publication date: 26 April 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

zbMATH Keywords

dynamic programmingapproximation algorithmlongest common subsequencemaximum independent setMax SNP-hardRNA structural similarity comparisonsequence annotation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimization, approximation, and complexity classes
• The longest common subsequence problem for sequences with nested arc annotations.
• The String-to-String Correction Problem
• Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
• On approximation properties of the Independent set problem for degree 3 graphs
• Algorithms for the Longest Common Subsequence Problem
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• A special case for subset interconnection designs

Cited In (14)

• Tight conditional lower bounds for longest common increasing subsequence
• Title not available (Why is that?)
• On the ordered list subgraph embedding problems
• A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs
• Title not available (Why is that?)
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• Improved algorithms for largest cardinality 2-interval pattern problem
• The longest common subsequence problem for sequences with nested arc annotations.
• An algebraic view of the relation between largest common subtrees and smallest common supertrees
• Title not available (Why is that?)
• Anytime algorithms for the longest common palindromic subsequence problem
• A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes
• Parameterized Complexity of the Arc-Preserving Subsequence Problem
• Efficient pattern matching for RNA secondary structures

This page was built for publication: The longest common subsequence problem for arc-annotated sequences

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