[inciampati]

The performance benefit of SIMD implementation of Smith-Waterman-Gotoh is moot relative to the gains provided by a total reformulation of the pairwise sequence alignment problem.

The Wavefront Algorithm (WFA) flips the problem on its head by progressively exploring the best scoring alignment until a global alignment is attained. Then no more work needs to be done to fill the matrix. The total work is actually quadratic in sequence divergence rather than length, a huge improvement over SWG for almost all applications.

In WFA the data dependencies are trivial and compilers easily auto-vectorize the inner loop of the algorithm. It's also possible to implement this in linear memory relative to sequence divergence with a bidirectional approach (biWFA).

All this is to say that vectorization and SIMD hardware is cool, but new theory and approach can completely overwhelm it's potential benefits.

[gww]

I agree with you about WFA. I was just very impressed when the striped SW first came out when I was still a fledgling PhD student.