License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2020.17
URN: urn:nbn:de:0030-drops-128061
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12806/
Ganesh, Arun ;
Sy, Aaron
Near-Linear Time Edit Distance for Indel Channels
Abstract
We consider the following model for sampling pairs of strings: s₁ is a uniformly random bitstring of length n, and s₂ is the bitstring arrived at by applying substitutions, insertions, and deletions to each bit of s₁ with some probability. We show that the edit distance between s₁ and s₂ can be computed in O(n ln n) time with high probability, as long as each bit of s₁ has a mutation applied to it with probability at most a small constant. 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. Similar techniques may be of interest in the average-case analysis of other problems commonly solved via dynamic programming.
BibTeX - Entry
@InProceedings{ganesh_et_al:LIPIcs:2020:12806,
author = {Arun Ganesh and Aaron Sy},
title = {{Near-Linear Time Edit Distance for Indel Channels}},
booktitle = {20th International Workshop on Algorithms in Bioinformatics (WABI 2020)},
pages = {17:1--17:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-161-0},
ISSN = {1868-8969},
year = {2020},
volume = {172},
editor = {Carl Kingsford and Nadia Pisanti},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12806},
URN = {urn:nbn:de:0030-drops-128061},
doi = {10.4230/LIPIcs.WABI.2020.17},
annote = {Keywords: edit distance, average-case analysis, dynamic programming, sequence alignment}
}
|
Keywords: |
|
edit distance, average-case analysis, dynamic programming, sequence alignment |
|
Collection: |
|
20th International Workshop on Algorithms in Bioinformatics (WABI 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
25.08.2020 |
