Implementazione di un algoritmo di allineamento di sequenze genomiche su FPGA

Marco Domenico Santambrogio (mail)

Architetture dei sistemi di elaborazione

FPGA, Computazione ad alte prestazioni, Genomica

C/C++, FPGA

L’allineamento di sequenze è una procedura centrale nella bioinformatica che trova moltissime applicazioni nel campo della genomica e, più in generale, nella biologia molecolare. Le evoluzioni tecnologiche richiedono algoritmi che siano sempre più veloci ed efficienti per portare a termine tali procedure. Purtroppo, gli algoritmi ad oggi sviluppati per l’allineamento di sequenze hanno complessità temporale e spaziale, nel migliore dei casi, quadratica. Per questo scopo, noi proponiamo un’implementazione basata su FPGA del “Wavefront Alignment Algorithm” (WFA). Questo algoritmo è usato per l’allineamento gap-affine globale che sfrutta regioni omologhe tra le due sequenze ed è stato ideato per velocizzare gli algoritmi proposti precedentemente di complessità ancora maggiore (algoritmo di Needleman-Wunsch). L’implementazione su FPGA ha lo scopo di accelerare tale algoritmo per renderlo più veloce, flessibile e meno dispendioso di energia nell’esecuzione.