L'alineament de seqüències biològiques és un problema fonamental i una component essencial per al funcionament de múltiples eines bioinformàtiques. En el camp de la genòmica, és fonamental per al mapeig de seqüències d'ADN, la detecció de variants genòmiques, la reconstrucció «de-novo» de genomes i molts altres mètodes. En general, l'alineament de seqüències es sol resoldre utilitzant tècniques basades en programació dinàmica. Per això, les solucions actuals a aquest problema tenen complexitat quadràtica (en temps i memòria) en la longitud de la seqüència.
En el context del projecte DRAC, investigadors del BSC i la UAB han desenvolupat l'algorisme wavefront (WFA) per a l'alineament exacte de seqüències genòmiques. Aquest mètode explota les similituds entre les seqüències per a accelerar el procés d'alineament. Per a això, el WFA computa alineaments parcials amb cost incremental fins a aconseguir la solució òptima (Figura 1). El resultat és un algorisme amb una complexitat O(ns) proporcional a la longitud de les seqüències (n) i l'error entre les mateixes (s). D'aquesta forma, millora el temps d'execució de les millors solucions proposades fins avui usant menys memòria en el procés.
Donada la seva simplicitat, el WFA pot ser vectoritzat fàcilment usant instruccions SIMD; a diferència dels algorismes basats en programació dinàmica. A més, presenta un patró de còmput senzill que pot ser explotat fàcilment per qualsevol compilador modern amb la finalitat de autovectoritzar el codi per a qualsevol processador amb suport vectorial. A més, el WFA pot operar amb dades compactades reduint l'ús de memòria fins a x4. El resultat és que el WFA processa alineaments de seqüències curtes (Illumina) 20-300x més ràpid que altres mètodes i s'executa 10-100x més ràpid alineant seqüències llargues com les d'Oxford Nanopore.
Aquest treball ha estat finançat pel Fons de Desenvolupament Regional de la Unió Europea en el marc del Programa Operatiu FEDER de Catalunya 2014-2020, amb una subvenció del 50% del cost total elegible en el marc del projecte DRAC, amb número 001-P-001723.