BDDBlast - A Memory Efficient Architecture for Pairwise Alignments

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

Resumo

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.

Palavras-chave: BLAST, Basic Local Alignment Sequencing Tool, BDD, Binary Decision Diagrams