TY - GEN
T1 - Unary Words Have the Smallest Levenshtein k-Neighbourhoods
AU - Charalampopoulos, Panagiotis
AU - Pissis, Solon P.
AU - Radoszewski, Jakub
AU - Walen, Tomasz
AU - Zuba, Wiktor
PY - 2020/6/9
Y1 - 2020/6/9
N2 - The edit distance (a.k.a. the Levenshtein distance) between two words is defined as the minimum number of insertions, deletions or substitutions of letters needed to transform one word into another. The Levenshtein k-neighbourhood of a word w is the set of words that are at edit distance at most k from w. This is perhaps the most important concept underlying BLAST, a widely-used tool for comparing biological sequences. A natural combinatorial question is to ask for upper and lower bounds on the size of this set. The answer to this question has important algorithmic implications as well. Myers notes that "such bounds would give a tighter characterisation of the running time of the algorithm" behind BLAST. We show that the size of the Levenshtein k-neighbourhood of any word of length n over an arbitrary alphabet is not smaller than the size of the Levenshtein k-neighbourhood of a unary word of length n, thus providing a tight lower bound on the size of the Levenshtein k-neighbourhood. We remark that this result was posed as a conjecture by Dufresne at WCTA 2019. 2012 ACM Subject Classification Theory of computation ! Pattern matching.
AB - The edit distance (a.k.a. the Levenshtein distance) between two words is defined as the minimum number of insertions, deletions or substitutions of letters needed to transform one word into another. The Levenshtein k-neighbourhood of a word w is the set of words that are at edit distance at most k from w. This is perhaps the most important concept underlying BLAST, a widely-used tool for comparing biological sequences. A natural combinatorial question is to ask for upper and lower bounds on the size of this set. The answer to this question has important algorithmic implications as well. Myers notes that "such bounds would give a tighter characterisation of the running time of the algorithm" behind BLAST. We show that the size of the Levenshtein k-neighbourhood of any word of length n over an arbitrary alphabet is not smaller than the size of the Levenshtein k-neighbourhood of a unary word of length n, thus providing a tight lower bound on the size of the Levenshtein k-neighbourhood. We remark that this result was posed as a conjecture by Dufresne at WCTA 2019. 2012 ACM Subject Classification Theory of computation ! Pattern matching.
KW - Combinatorics on words
KW - Edit distance
KW - Levenshtein distance
UR - http://www.scopus.com/inward/record.url?scp=85088374754&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85088374754&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CPM.2020.10
DO - 10.4230/LIPIcs.CPM.2020.10
M3 - Conference contribution
AN - SCOPUS:85088374754
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 12
BT - 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
A2 - Gortz, Inge Li
A2 - Weimann, Oren
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020
Y2 - 17 June 2020 through 19 June 2020
ER -