On the longest common rigid subsequence problem

DOI10.1007/S00453-008-9175-1MaRDI QIDQ848965zbMATH OpenOpenAlexFDO

Authors N. Bansal, Moshe Lewenstein, Bin Ma, Kaizhong Zhang

Publication date 23 February 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-008-9175-1

zbMATH Keywords

approximation algorithmslongest common subsequencemotif findinglongest common rigid subsequencepattern matching and computational biology

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Searching and sorting (68P10)

Recommendations

• Combinatorial Pattern Matching
• Constrained LCS: Hardness and Approximation
• Hardness of longest common subsequence for sequences with bounded run-lengths
• Maximal common subsequences and minimal common supersequences
• On the longest common parameterized subsequence

Cites work

• scientific article; zbMATH DE number 1615273 (Why is no real title available?)
• scientific article; zbMATH DE number 1945160 (Why is no real title available?)
• Combinatorial Pattern Matching
• Derandomized graph products
• Distinguishing string selection problems.
• Finding similar regions in many sequences
• Finding similar regions in many strings
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• On the closest string and substring problems
• Optimization, approximation, and complexity classes
• Pattern recognition in several sequences: Consensus and alignment
• Some APX-completeness results for cubic graphs
• The Complexity of Some Problems on Subsequences and Supersequences

Cited in

(7)

• Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs
• scientific article; zbMATH DE number 5873671 (Why is no real title available?)
• Hardness of longest common subsequence for sequences with bounded run-lengths
• Quick greedy computation for minimum common string partition
• The longest filled common subsequence problem
• On the Longest Common Parameterized Subsequence
• Combinatorial Pattern Matching

Describes a project that uses

Uses Software

• TEIRESIAS

This page was built for publication: On the longest common rigid subsequence problem

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