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. One random string, of which the other is a random mutation via some model. We will make the strongest possible assumption on the randomness of the input: that \(A\) is random, and that \(B\) is a random mutation of \(A\) with a limited/bounded error rate \(e \leq f(n)\).