Topology of strings: median string is NP-complete
type: Item
instance of: scholarly article
title: Topology of strings: median string is NP-complete
zbMATH Open document ID: 0940.68116
DOI: 10.1016/S0304-3975(97)00240-5
published in: Theoretical Computer Science
publication date: 2000-06-04T00:00:00Z
review text: Given a set of strings, the problem of finding a string that minimises its distance to the set is directly related with problems frequently encountered in areas involving pattern recognition or computational biology. Based on the Levenshtein (or edit) distance, different definitions of distances between a string and a set of strings can be adopted. In particular, if this definition is the sum of the distances to each string of the set, the string that minimises this distance is the (generalised) median string. Finding this string corresponds in speech recognition to giving a model for a set of acoustic sequences, and in computational biology to constructing an optimal evolutionary tree when the given phylogeny is a star. Only efficient algorithms are known for finding approximate solutions. The results in this paper are combinatorial and negative. We prove that computing the median string corresponds to a NP-complete decision problems, thus proving that this problem is NP-hard.
Mathematics Subject Classification ID: 68T10
zbMATH DE Number: 1454280
zbMATH Keywords: NP-complete problems
zbMATH Keywords: string-to-string correction
zbMATH Keywords: Levenshtein distance
zbMATH Keywords: generalised median
zbMATH Keywords: multiple sequence alignment
author: Colin de la Higuera
author: Francisco Casacuberta
MaRDI profile type: Publication
cites work: A survey of multiple sequence comparison methods
cites work: Q3670607
cites work: Q4198056
cites work: From the median to the generalized center
cites work: Multiple sequence comparison -- a peptide matching approach
cites work: Q4859180
cites work: Finding approximate patterns in strings
cites work: The String-to-String Correction Problem
cites work: Approximation algorithms for tree alignment with a given phylogeny
Recommended article: Complexities of the Centre and Median String Problems
Recommended article: The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
Recommended article: Recognizing string graphs in NP
Recommended article: The consensus string problem for a metric is NP-complete
Recommended article: Some computations in string topology
Recommended article: Q4258669
Recommended article: String graphs. II: Recognizing string graphs is NP-hard
Recommended article: The transposition median problem is NP-complete
description: scientific article; zbMATH DE number 1454280