### Aaron Sy and Arun Ganesh

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2019-60

May 17, 2019

### http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-60.pdf

We show that the edit distance between pairs of strings generated by a standard model called the indel channel can be computed in O(n log n) time with high probability. The algorithm is simple and only uses the textbook dynamic programming algorithm as a primitive, first computing an approximate alignment between the two strings, and then running the dynamic programming algorithm restricted to entries close to the approximate alignment. The analysis of our algorithm provides theoretical justification for alignment heuristics used in practice such as BLAST, FASTA, and MAFFT, which also start by computing approximate alignments quickly and then find the best alignment near the approximate alignment. Our main technical contribution is a partitioning of alignments such that the number of the subsets in the partition is not too large and every alignment in one subset is worse than an alignment considered by our algorithm with high probability. We hope similar techniques might be useful in the average-case analysis of other programs commonly solved via dynamic programming.

**Advisor:** Satish Rao

BibTeX citation:

@mastersthesis{Sy:EECS-2019-60, Author = {Sy, Aaron and Ganesh, Arun}, Title = {Near-Linear Time Edit Distance for Indel Channels}, School = {EECS Department, University of California, Berkeley}, Year = {2019}, Month = {May}, URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-60.html}, Number = {UCB/EECS-2019-60}, Abstract = {We show that the edit distance between pairs of strings generated by a standard model called the indel channel can be computed in O(n log n) time with high probability. The algorithm is simple and only uses the textbook dynamic programming algorithm as a primitive, first computing an approximate alignment between the two strings, and then running the dynamic programming algorithm restricted to entries close to the approximate alignment. The analysis of our algorithm provides theoretical justification for alignment heuristics used in practice such as BLAST, FASTA, and MAFFT, which also start by computing approximate alignments quickly and then find the best alignment near the approximate alignment. Our main technical contribution is a partitioning of alignments such that the number of the subsets in the partition is not too large and every alignment in one subset is worse than an alignment considered by our algorithm with high probability. We hope similar techniques might be useful in the average-case analysis of other programs commonly solved via dynamic programming.} }

EndNote citation:

%0 Thesis %A Sy, Aaron %A Ganesh, Arun %T Near-Linear Time Edit Distance for Indel Channels %I EECS Department, University of California, Berkeley %D 2019 %8 May 17 %@ UCB/EECS-2019-60 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-60.html %F Sy:EECS-2019-60