BDDBlast - A Memory Efficient Architecture for Pairwise Alignments - de Oliveira, Demian Bueno; Faria-Campos, Alessandra; Campos, Sérgio (Anais do Simpósio Brasileiro de Bioinformática (BSB); 2022: Anais do XV Simpósio Brasileiro de Bioinformática, 2022)
BLAST, or Basic Local Alignment Search Tool, is one of the most widely used bioinformatics tools today. However, as biological data accumulates, its use can become a bottleneck limiting biological analyses both in time and memory usage. In this work we propose the use of a new data structure to re-implement BLAST. We use Binary Decision Diagrams (BDDs) to store the biological sequences and opti- mize resources, reducing memory requirements. This new approach has allowed us to construct the alignment of biological sequences with gains of up to 65.7% in memory usage for the allocation of the BLAST data structures and up to 16.3% faster search results, without altering the BLAST algorithm or its results.