Paper Info
Title
Using Binary Decision Diagrams (BDDs) for Memory Optimization in Basic Local Alignment Search Tool (BLAST).
Abstract
Sequence alignment is the procedure of comparing two or more DNA or protein sequences in order to find similarities between them. One of the tools used for this purpose is the Basic Local Alignment Search Tool (BLAST). BLAST however, presents limits on the size of sequences that can be analyzed requiring the use of a lot of memory and time for long sequences. Therefore, improvements can be made to overcome these limitations. In this work we propose the use of the data structure Binary Decision Diagram (BDD) to represent alignments obtained through BLAST, which offers a compressed and efficient representation of the aligned sequences. We have developed a BDD-based version of BLAST, which omits any redundant information shared by the aligned sequences. We have observed a considerable improvement on memory usage, saving up to 63,95% memory, with a negligible performance degradation of only 3,10%. This approach could improve alignment methods, obtaining compact and efficient representations, which could allow the alignment of longer sequences, such as genome-wide human sequences, to be used in population and migration studies.
Year
DOI
Venue
2014
10.1007/978-3-319-12418-6_9
ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2014
Keywords
Field
DocType
Binary Decision Diagrams (BDD),Basic Local Alignment Search Tool (BLAST),Multiple Sequence Alignment
Sequence alignment,Population,Data structure,Computer science,Algorithm,Binary decision diagram,Artificial intelligence,Multiple sequence alignment,Basic Local Alignment Search Tool,Machine learning
Conference
Volume
ISSN
Citations 
8826
0302-9743
0
PageRank 
References 
Authors
0.34
5
5
Name
Order
Citations
PageRank
Demian Oliveira100.34
Fernando A. F. Braz242.83
Bruno Ferreira391.97
Alessandra C. Faria-Campos443.17
Sérgio V. A. Campos542.15