Table of Contents Pairwise alignment in subquadratic time Random model AlgorithmSeed heuristic Match pruning AnalysisExpanded statesExcess errors Algorithmic complexity This post is a proof sketch to show that A* with the seed heuristic (Groot Koerkamp and Ivanov 2024) does exact pairwise alignment of random strings with random mutations in near linear time. Pairwise alignment in subquadratic time Link to heading Backurs and Indyk (2018) show that computing edit distance can not be done in st...
