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

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)

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

• scientific article; zbMATH DE number 2185647 (Why is no real title available?)
• scientific article; zbMATH DE number 2185648 (Why is no real title available?)
• A special case for subset interconnection designs
• Algorithms for the Longest Common Subsequence Problem
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• 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 String-to-String Correction Problem
• The longest common subsequence problem for sequences with nested arc annotations.

Cited in

(17)

• Tight conditional lower bounds for longest common increasing subsequence
• Tight conditional lower bounds for longest common increasing subsequence
• scientific article; zbMATH DE number 1615278 (Why is no real title available?)
• scientific article; zbMATH DE number 1754611 (Why is no real title available?)
• scientific article; zbMATH DE number 2087047 (Why is no real title available?)
• A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs
• The longest common subsequence problem for arc-annotated sequences
• scientific article; zbMATH DE number 7561345 (Why is no real title available?)
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• Improved algorithms for largest cardinality 2-interval pattern problem
• Parameterized complexity of the arc-preserving subsequence problem
• Arc-preserving subsequences of arc-annotated sequences
• 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
• A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes
• Anytime algorithms for the longest common palindromic 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)