BDDBlast - A Memory Efficient Architecture for Pairwise Alignments

• Demian Bueno de Oliveira Federal University of Minas Gerais (UFMG)
• Alessandra Faria-Campos Federal University of Minas Gerais (UFMG)
• Sérgio Campos Federal University of Minas Gerais (UFMG)

Abstract

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.