Topology of strings: Median string is NP-complete
| Autor: | C. de la Higuera, Francisco Casacuberta |
|---|---|
| Rok vydání: | 2000 |
| Předmět: |
TheoryofComputation_MISCELLANEOUS
Empty string String-to-string correction problem General Computer Science Levenshtein distance String (computer science) String searching algorithm Approximate string matching Theoretical Computer Science Combinatorics High Energy Physics::Theory generalised Median String-to-string correction Edit distance Multiple sequence alignment String metric NP-complete problems Computer Science(all) Mathematics |
| Zdroj: | Theoretical Computer Science. 230:39-48 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/s0304-3975(97)00240-5 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect