The longest common subsequence problem for arc-annotated sequences

DOI10.1016/S1570-8667(03)00080-7zbMath1118.68756MaRDI QIDQ876717

Bin Ma, Tao Jiang, Zhang, Kaizhong, Guo-Hui Lin

Publication date: 26 April 2007

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

zbMATH Keywords

dynamic programmingapproximation algorithmmaximum independent setlongest common subsequenceMax SNP-hardRNA structural similarity comparisonsequence annotation

Mathematics Subject Classification ID

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

Related Items (11)

On the ordered list subgraph embedding problems ⋮ Solving longest common subsequence problems via a transformation to the maximum clique problem ⋮ A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes ⋮ Efficient pattern matching for RNA secondary structures ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Unnamed Item ⋮ Parameterized Complexity of the Arc-Preserving Subsequence Problem ⋮ An algebraic view of the relation between largest common subtrees and smallest common supertrees ⋮ Improved algorithms for largest cardinality 2-interval pattern problem ⋮ Unnamed Item ⋮ Anytime algorithms for the longest common palindromic subsequence problem

Cites Work

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

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