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.

Advisors: 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