El alineamiento de secuencias biológicas es un problema fundamental y una componente esencial para el funcionamiento de múltiples herramientas bioinformáticas. En el campo de la genómica, es fundamental para el mapeo de secuencias de ADN, la detección de variantes genómicas, la reconstrucción «de-novo» de genomas y otros muchos métodos. En general, el alineamiento de secuencias se suele resolver utilizando técnicas basadas en programación dinámica. Por ello, las soluciones actuales a este problema tienen complejidad cuadrática (en tiempo y memoria) en la longitud de la secuencia.
En el contexto del proyecto DRAC, investigadores del BSC y la UAB han desarrollado el algoritmo wavefront (WFA) para el alineamiento exacto de secuencias genómicas. Este método explota las similaridades entre las secuencias para acelerar el proceso de alineamiento. Para ello, el WFA computa alineamientos parciales con coste incremental hasta alcanzar la solución óptima (Figura 1). El resultado es un algoritmo con una complejidad O(ns) proporcional a la longitud de las secuencias (n) y el error entre las mismas (s). De esta forma, mejora el tiempo de ejecución de las mejores soluciones propuestas hasta la fecha usando menos memoria en el proceso.
Dada su simplicidad, el WFA puede ser vectorizado fácilmente usando instrucciones SIMD; a diferencia de los algoritmos basados en programación dinámica. Además, presenta un patrón de cómputo sencillo que puede ser explotado fácilmente por cualquier compilador moderno con el fin de autovectorizar el código para cualquier hardware con soporte vectorial. Además, el WFA puede operar con datos compactados reduciendo el uso de memoria hasta x4. El resultado es que el WFA procesa alineamientos de secuencias cortas (Illumina) 20-300x más rápido que otros métodos y se ejecuta 10-100x más rápido alineando secuencias largas como las de Oxford Nanopore.
El proyecto DRAC con número de expediente 001-P-001723 ha sido cofinanciado en un 50% con 2.000.000,00€ por el Fondo Europeo de Desarrollo Regional de la Unión Europea en el marco del Programa Operativo FEDER de Cataluña 2014-2020, con el soporte de la Generalitat de Cataluña.