The consensus string problem for a metric is NP-complete
type: Item
instance of: scholarly article
title: The consensus string problem for a metric is NP-complete
zbMATH Open document ID: 1118.68449
DOI: 10.1016/S1570-8667(03)00011-X
author: J. S. Sim
author: Kunsoo Park
published in: Journal of Discrete Algorithms
publication date: 2007-04-26T00:00:00Z
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5147084
zbMATH Keywords: consensus string
zbMATH Keywords: multiple sequence alignment
zbMATH Keywords: NP-complete
MaRDI profile type: Publication
cites work: Trees, Stars, and Multiple Biological Sequence Alignment
cites work: On covering problems of codes
cites work: Q4252402
cites work: Q2723944
cites work: Algorithms on Strings, Trees and Sequences
cites work: Efficient methods for multiple sequence alignment with guaranteed error bounds
cites work: Mapping the genome
cites work: Q4252342
cites work: Finding similar regions in many strings
cites work: The Complexity of Some Problems on Subsequences and Supersequences
cites work: More on the complexity of common superstring and supersequence problems
cites work: The shortest common supersequence problem over binary alphabet is NP- complete
cites work: Approximation algorithms for tree alignment with a given phylogeny
description: scientific article; zbMATH DE number 5147084