The consensus string problem for a metric is NP-complete

DOI10.1016/S1570-8667(03)00011-XMaRDI QIDQ876700zbMATH OpenFDO

Authors J. S. Sim, Kunsoo Park

Publication date 26 April 2007

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

zbMATH Keywords

NP-completeconsensus stringmultiple sequence alignment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the hardness of the consensus string problem
• Topology of strings: median string is NP-complete
• Consensus string problem for multiple regular languages
• Distinguishing string selection problems.
• On the Efficiency of the Hamming C-Centerstring Problems

Cites work

• scientific article; zbMATH DE number 1615274 (Why is no real title available?)
• scientific article; zbMATH DE number 1305456 (Why is no real title available?)
• scientific article; zbMATH DE number 1305511 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• Approximation algorithms for tree alignment with a given phylogeny
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Finding similar regions in many strings
• Mapping the genome
• More on the complexity of common superstring and supersequence problems
• On covering problems of codes
• The Complexity of Some Problems on Subsequences and Supersequences
• The shortest common supersequence problem over binary alphabet is NP- complete
• Trees, Stars, and Multiple Biological Sequence Alignment

Cited in

(16)

• Hybridizations of metaheuristics with branch \& bound derivates
• Consensus string problem for multiple regular languages
• Closest substring problems for regular languages
• Efficient approaches for the flooding problem on graphs
• Consensus string problem for multiple regular languages
• On the hardness of the consensus string problem
• Ensemble clustering by means of clustering embedding in vector spaces
• Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• Tight hardness results for consensus problems on circular strings and time series
• Hardness results for the center and median string problems under the weighted and unweighted edit distances
• Topology of strings: median string is NP-complete
• The contig assembly problem and its algorithmic solutions
• On the string consensus problem and the Manhattan sequence consensus problem
• A Survey on the Complexity of Flood-Filling Games
• Tractability and hardness of flood-filling games on trees

This page was built for publication: The consensus string problem for a metric is NP-complete

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