The consensus string problem for a metric is NP-complete

DOI10.1016/S1570-8667(03)00011-XzbMATH Open1118.68449MaRDI QIDQ876700FDOQ876700

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)

Cites Work

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

Cited In (14)

• A Survey on the Complexity of Flood-Filling Games
• Hardness results for the center and median string problems under the weighted and unweighted edit distances
• The Contig Assembly Problem and Its Algorithmic Solutions
• Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
• Closest substring problems for regular languages
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• On the string consensus problem and the Manhattan sequence consensus problem
• Consensus string problem for multiple regular languages
• Ensemble clustering by means of clustering embedding in vector spaces
• Consensus String Problem for Multiple Regular Languages
• Efficient approaches for the flooding problem on graphs
• Hybridizations of Metaheuristics With Branch & Bound Derivates
• Topology of strings: median string is NP-complete
• Tractability and hardness of flood-filling games on trees

   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 👍 👎

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)