History of the wave-front algorithm ...

[thegenemyers]

Hi Heng, Richard Durbin pointed me at your history and I thought I would offer a few corrections/additions.

Esko and I developed the idea independently. I came up with it in 1984 and published in 1986 and did not know about his 1985 paper. Your history makes it sound like my paper referenced his, it did not, the Landau Vishkin paper is the one that cited his 1985 paper.

My 1986 paper also showed that the algorithm was O(n+k^2) in expectation. I also showed how to deliver an alignment in linear space with a forward and reverse wave. And using a suffix tree and O(1) lca finding that the algorithm could be made (impractically) to run in O(nlogn+k^2) worst-case time. So it went well beyond Esko's paper and fully superceded the work of Landau and Vishkin and others in that group. My paper also gave a much cleaner exposition I think than Esko's (look at the two papers) and introduced the term "wave".

But the story doesn't end there. In the mid-2000's I realized the wave could be extended heuristically in a way that accelerated
with increasing stringency of match. This finally found its way into a paper in my 2014 WABI paper `Efficient Alignment Discovery amongst Noisy Long Reads,''. This paper doesn't give my final word on the wavefront heurisitc which remains unpublished but does I think give interesting ideas for how to terminate a wave extension as well as several ideas for trimming the wave front. I gave many talks about this work from 2013 on in the context of long read sequencing and assembly. I met Santiago when he was a Ph.D. in Roderic Guigo's labe and in fact was on his thesis committee. I like him very much and I think he liked my work including the non-affine wave-front which lead him to develop WFA.

That ends my description of the history from my perspective. Please incorporate as you see fit. I've been a long time fan of
your work and hope that perhaps one day we will actually meet before I get too old :-) I still interact with Richard a lot so perhaps
in that context.

Kind regards, Gene Myers

[lh3]

By "the two authors" in the original text, I meant Landau and Vishkin, but I agree it could also be interpreted as yours and their paper. I now mention Landau & Vishkin in a separate paragraph to avoid this confusion. I also added a few notes based on your explanation. Thanks! Copying @richarddurbin

I have followed and learned from your work for over two decades. I really hope we can meet in person some day.