The consensus string problem for a metric is NP-complete

DOI10.1016/S1570-8667(03)00011-XzbMath1118.68449MaRDI QIDQ876700

Jeong Seop Sim, Kun Soo Park

Publication date: 26 April 2007

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

zbMATH Keywords

multiple sequence alignment; NP-complete; consensus string

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Consensus String Problem for Multiple Regular Languages, 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, Efficient approaches for the flooding problem on graphs, Tractability and hardness of flood-filling games on trees, Hardness results for the center and median string problems under the weighted and unweighted edit distances, Hybridizations of Metaheuristics With Branch & Bound Derivates, The Contig Assembly Problem and Its Algorithmic Solutions

Cites Work

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