"[...] the naive O(n^2) strategy for scoring all alignments is unacceptable. Instead, we use the fact that "scoring all alignments" is a convolution operation and can be implemented with the Fast Fourier Transform (FFT), bringing the complexity down to O(n log n)."
I absolutely love it when something that, at very first glance, has no business in being solved in the frequency domain, gets solved in the frequency domain.
"[...] the naive O(n^2) strategy for scoring all alignments is unacceptable. Instead, we use the fact that "scoring all alignments" is a convolution operation and can be implemented with the Fast Fourier Transform (FFT), bringing the complexity down to O(n log n)."
I absolutely love it when something that, at very first glance, has no business in being solved in the frequency domain, gets solved in the frequency domain.