The longest common subsequence problem for arc-annotated sequences

DOI10.1016/S1570-8667(03)00080-7MaRDI QIDQ876717zbMATH OpenFDO

Authors Tao Jiang, Bin Ma, Guohui Lin, Kaizhong Zhang

Publication date 26 April 2007

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

Full work available at URL https://doi.org/10.1016/S1570-8667(03)00080-7

zbMATH Keywords

approximation algorithmdynamic programminglongest common subsequenceMax SNP-hardmaximum independent setRNA structural similarity comparisonsequence annotation

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1615278
• The longest common subsequence problem for arc-annotated sequences
• Arc-preserving subsequences of arc-annotated sequences
• scientific article; zbMATH DE number 1754611
• The longest common subsequence problem for sequences with nested arc annotations.

Cites work

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

Cited in

(18)

• The longest common subsequence problem for sequences with nested arc annotations.
• Tight conditional lower bounds for longest common increasing subsequence
• Anytime algorithms for the longest common palindromic subsequence problem
• An algebraic view of the relation between largest common subtrees and smallest common supertrees
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• scientific article; zbMATH DE number 1615278 (Why is no real title available?)
• The longest common subsequence problem for arc-annotated sequences
• Pattern matching for arc-annotated sequences
• Parameterized complexity of the arc-preserving subsequence problem
• Arc-preserving subsequences of arc-annotated sequences
• scientific article; zbMATH DE number 1754611 (Why is no real title available?)
• scientific article; zbMATH DE number 2087047 (Why is no real title available?)
• Efficient pattern matching for RNA secondary structures
• Sketching, streaming, and fine-grained complexity of (weighted) LCS
• Tight conditional lower bounds for longest common increasing subsequence
• A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes
• A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs
• Improved algorithms for largest cardinality 2-interval pattern problem

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)