Vectorization of global alignment - single query vs single target

[torognes]

SIMD-vectorization of global alignment of one query vs one target sequence. Should use the striped approach of Farrar (2007) or the vertical vector approach of Rognes (2000).

[torognes]

Particularly important for clustering.

[frederic-mahe]

Not sure if it relevant or not: https://github.com/CMU-SAFARI/Shouji#key-mechanism presents a pre-filtering technique to reduce the number of sequence pairwise-comparisons.

The same team published a new algorithm implemented in C, available under the name SneakySnake.

SneakySnake significantly improves the accuracy of pre-alignment filtering by up to four orders of magnitude compared to the state-of-the-art pre-alignment filters, Shouji, GateKeeper, and SHD. SneakySnake accelerates Edlib (state-of-the-art implementation of Myers’s bit-vector algorithm) and Parasail (sequence aligner with configurable scoring function), by up to 37.6× and 43.9× (>12× on average), respectively, without requiring hardware acceleration

[frederic-mahe]

Closing for now. We can always revisit in the future (use the tag PotentialFuture to select these items)