On the hardness of the consensus string problem

DOI10.1016/J.IPL.2013.02.016MaRDI QIDQ396596zbMATH OpenOpenAlexFDO

Authors Amihood Amir, Haim Paryenty, Liam Roditty

Publication date 13 August 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2013.02.016

zbMATH Keywords

computational complexityHamming distanceconsensuscombinatorial problemsswapreversal

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Recommendations

• The consensus string problem for a metric is NP-complete
• On the Efficiency of the Hamming C-Centerstring Problems
• Tight hardness results for consensus problems on circular strings and time series
• Efficient algorithms for consensus string problems minimizing both distance sum and radius
• Finding similar regions in many strings

Cites work

• scientific article; zbMATH DE number 2081011 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• A three-string approach to the closest string problem
• An Extension of the String-to-String Correction Problem
• Configurations and minority in the string consensus problem
• Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• More efficient algorithms for closest string and substring problems
• On covering problems of codes
• On the spherical surface of smallest radius enclosing a bounded subset of 𝑛-dimensional euclidean space
• Optimal solutions for the closest-string problem via integer programming
• Pattern Matching with Swaps
• Pattern matching with address errors: rearrangement distances
• String rearrangement metrics: a survey
• Two Algorithms for the Minimum Enclosing Ball Problem

Cited in

(8)

• Consensus string problem for multiple regular languages
• Closest substring problems for regular languages
• Consensus string problem for multiple regular languages
• The consensus string problem for a metric is NP-complete
• Two-string consensus problem under non-overlapping inversion and transposition distance
• Tight hardness results for consensus problems on circular strings and time series
• On the string consensus problem and the Manhattan sequence consensus problem
• An efficient algorithm to detect common ancestor genes for non-overlapping inversion and applications

This page was built for publication: On the hardness of the consensus string problem

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