Theoretical Analysis of Edit Distance Algorithms

Edit distance--a classical problem in computer science--has received ongoing attention from both practitioners and theoreticians. Given two strings A and B, the edit distance is the minimum number of substitutions, insertions, and deletions needed to transform A into B. For example, the edit distance between apf leee and rapleet is 3: . The edit distance problem is widely known, as it is often taught as part of the undergraduate curriculum to illustrate two-dimensional dynamic programming. Theoreticians have studied the problem starting from as early as 196624 and 1974,43 but it very much remains an active topic of research today (for example, Boroujeni et al.8). Simultaneously, bioinformatics practitioners continue to actively develop14,15,40 and apply9,28,38,39,42,45 fast edit distance solvers ubiquitously. Given its status as a classic problem and its importance to both theoreticians and practitioners, edit distance provides a unique opportunity to study the interaction between theory and practice. Theoreticians develop abstract algorithms that have superior theoretical performance; practitioners develop implemented algorithms that have superior empirical performance. In an ideal world, practitioners would implement and analyze the empirical performance of the abstract algorithms developed by theoreticians, while theoreticians would analyze the theoretical performance of the implemented algorithms developed by practitioners. In the real world, there is often a wide gap between the practical and theoretical communities; understanding how to close this gap is critical to making theoretical computer science more relevant to applications. The edit distance problem is then an excellent lens through which to understand how the theoretical analysis of algorithms impacts practical implementations. There are many ways to approach the practice/theory gap in a problem like edit distance.