Three referees support accept, one indicates reject (with weak self-assigned confidence tough). In my opinion, the rebuttal nicely addressed all points of criticism raised, so I also recommend acceptance. However, please include the additional experiments from the rebuttal in your revised paper.

Pairwise alignment of DNA sequencing data is a ubiquitous task in bioinformatics and typically represents a heavy computational burden. State-of-the-art approaches to speed up this task use hashing to identify short segments (k-mers) that are shared by pairs of reads, which can then be used to estimate alignment scores. However, when the number of reads is large, accurately estimating alignment scores for all pairs is still very costly. Moreover, in practice, one is only interested in identifying pairs of reads with large alignment scores. In this work, we propose a new approach to pairwise alignment estimation based on two key new ingredients.