@article{ higuera_topology_2000,
  title = {Topology of strings: {Median} string is {NP}-complete},
  volume = {230},
  issn = {0304-3975},
  shorttitle = {Topology of strings},
  url = {http://www.sciencedirect.com/science/article/pii/S0304397597002405},
  doi = {10.1016/S0304-3975(97)00240-5},
  abstract = {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.},
  number = {1–2},
  urldate = {2015-04-21TZ},
  journal = {Theoretical Computer Science},
  author = {Higuera, Colin de la and Casacuberta, F.},
  month = {January},
  year = {2000},
  note = {00093},
  keywords = {Levenshtein distance, Multiple sequence alignment, NP-complete problems, String-to-string correction, generalised Median},
  pages = {39--48}
}

{"_id":"kcqJ9xNXskwFc8soG","authorIDs":[],"author_short":["Higuera","de<nbsp>la, C.","Casacuberta, F."],"bibbaseid":"higuera-denbspla-casacuberta-topologyofstringsmedianstringisnpcomplete-2000","bibdata":{"abstract":"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.","author":["Higuera","de la, Colin","Casacuberta, F."],"author_short":["Higuera","de<nbsp>la, C.","Casacuberta, F."],"bibtex":"@article{ higuera_topology_2000,\n title = {Topology of strings: {Median} string is {NP}-complete},\n volume = {230},\n issn = {0304-3975},\n shorttitle = {Topology of strings},\n url = {http://www.sciencedirect.com/science/article/pii/S0304397597002405},\n doi = {10.1016/S0304-3975(97)00240-5},\n abstract = {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.},\n number = {1–2},\n urldate = {2015-04-21TZ},\n journal = {Theoretical Computer Science},\n author = {Higuera, Colin de la and Casacuberta, F.},\n month = {January},\n year = {2000},\n note = {00093},\n keywords = {Levenshtein distance, Multiple sequence alignment, NP-complete problems, String-to-string correction, generalised Median},\n pages = {39--48}\n}","bibtype":"article","doi":"10.1016/S0304-3975(97)00240-5","id":"higuera_topology_2000","issn":"0304-3975","journal":"Theoretical Computer Science","key":"higuera_topology_2000","keywords":"Levenshtein distance, Multiple sequence alignment, NP-complete problems, String-to-string correction, generalised Median","month":"January","note":"00093","number":"1–2","pages":"39--48","shorttitle":"Topology of strings","title":"Topology of strings: Median string is NP-complete","type":"article","url":"http://www.sciencedirect.com/science/article/pii/S0304397597002405","urldate":"2015-04-21TZ","volume":"230","year":"2000","bibbaseid":"higuera-denbspla-casacuberta-topologyofstringsmedianstringisnpcomplete-2000","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/S0304397597002405"},"keyword":["Levenshtein distance","Multiple sequence alignment","NP-complete problems","String-to-string correction","generalised Median"],"downloads":0},"bibtype":"article","biburl":"http://bibbase.org/zotero/ealprr","creationDate":"2015-04-22T00:12:57.275Z","downloads":0,"keywords":["levenshtein distance","multiple sequence alignment","np-complete problems","string-to-string correction","generalised median"],"search_terms":["topology","strings","median","string","complete","higuera","de<nbsp>la","casacuberta"],"title":"Topology of strings: Median string is NP-complete","year":2000,"dataSources":["fcy64Zdm28gydMmuE"]}