Skip to main content
SpringerLink
Log in

BDDBlast—A Memory Efficient Architecture for Pairwise Alignments

  • Conference paper
  • First Online:
Advances in Bioinformatics and Computational Biology (BSB 2022)

Part of the book series: Lecture Notes in Computer Science ((LNBI,volume 13523))

Included in the following conference series:

  • 229 Accesses

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 optimize 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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 44.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 59.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    Available at https://www.ncbi.nlm.nih.gov/protein/1004172080.

  2. 2.

    The value for parameters W, T and X are used to explain a simplified example, and were not used in any experiments. W and T have either default or typical values. Parameter X is mentioned for completeness, but not used in the example.

  3. 3.

    BDDs can have a worst case exponential memory complexity in cases where the dependencies between the variables is circular or very complex. These dependencies do not typically occur in BDDBlast.

References

  1. Altschul, S.F., et al.: Basic local alignment search tool. J. Mol. Biol. 215(3), 403–410 (1990)

    Article  CAS  Google Scholar 

  2. Altschul, S.F., et al.: Gapped blast and psi-blast: a new generation of protein database search programs. Nucleic Acids Res. 25(17), 3389 (1997)

    Article  CAS  Google Scholar 

  3. Clarke, E.M., Grumberg, O., Peled, D.: Model Checking. MIT Press, Cambridge (1999)

    Google Scholar 

  4. Kasap, S., Benkrid, K., Liu, Y.: Design and implementation of an FPGA-based core for gapped blast sequence alignment. Eng. Lett. 16 (2008)

    Google Scholar 

  5. Ye, W., et al.: H-blast: a fast protein sequence alignment toolkit on heterogeneous computers with GPUs. Bioinformatics 33(8), 1130–1138 (2017)

    CAS  Google Scholar 

  6. Nguyen, V., Lavenier, D.: PLAST: parallel local alignment search tool for database comparison. BMC Bioinform. 10(329), 1–13 (2009)

    Google Scholar 

  7. Fahim, S.: Comparative analysis of protein alignment algorithms in parallel environment using CUDA. Ph.D. dissertation, BRAC University (2016)

    Google Scholar 

  8. Boratyn, G.M., Schäffer, A.A., Agarwala, R., et al.: Domain enhanced lookup time accelerated blast. Biol. Direct 7(12), 1–14 (2012). https://doi.org/10.1186/1745-6150-7-12

    Article  CAS  Google Scholar 

  9. Buchfink, B., Xie, C., Huson, D.: Fast and sensitive protein alignment using diamond. Nat. Methods 12, 59–60 (2015)

    Article  CAS  Google Scholar 

  10. Eddy, S.R.: Where did the blosum62 alignment score matrix come from? Nat. Biotechnol. 22(8), 1035–1036 (2004)

    Article  CAS  Google Scholar 

  11. Hess, M., et al.: Addressing inaccuracies in BLOSUM computation improves homology search performance. BMC Bioinform. 17(1), 1–10 (2016). https://doi.org/10.1186/s12859-016-1060-3

    Article  CAS  Google Scholar 

  12. Lee, C.-Y.: Representation of switching circuits by binary-decision programs. Bell Labs Tech. J. 38(4), 985–999 (1959)

    Article  Google Scholar 

  13. Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. Comput. IEEE Trans. 100(8), 677–691 (1986)

    Article  Google Scholar 

  14. Brace, K.S., Rudell, R.L., Bryant, R.E.: Efficient implementation of a BDD package. In: 27th ACM/IEEE Design Automation conference, p. 40. ACM (1991)

    Google Scholar 

  15. Pruitt, K.D., Tatusova, T., Maglott, D.R.: NCBI reference sequences (RefSeq): a curated non-redundant sequence database of genomes, transcripts and proteins. Nucleic Acids Res. 35(suppl 1), D61–D65 (2006)

    Google Scholar 

  16. Gastauer, M., et al.: Ti - a metagenomic survey of soil microbial communities along a rehabilitation chronosequence after iron ore mining. Sci. Data 6, 1–10 (2019)

    Article  Google Scholar 

Download references

Acknowledgments

The authors would like to thanks Ronnie Alves and Kleber de Souza with assistance with the Corumba sequences. This research was supported by in part by CNPq, CAPES and FAPEMIG, Brazilian Funding Agencies.

Author information

Authors and Affiliations

  1. Computer Science Department, Universidade Federal de Minas Gerais, Belo Horizonte, MG, Brazil

    Demian Bueno de Oliveira, Alessandra Faria-Campos & Sérgio Campos

Authors
  1. Demian Bueno de Oliveira
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alessandra Faria-Campos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sérgio Campos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sérgio Campos .

Editor information

Editors and Affiliations

  1. Instituto Nacional de Câncer, Rio de Janeiro, Brazil

    Nicole M. Scherer

  2. Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

    Raquel C. de Melo-Minardi

Ethics declarations

Availability

BDDBlast and the sequences used in this paper can be found at: http://www.luar.dcc.ufmg.br/bddblast/.

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

de Oliveira, D.B., Faria-Campos, A., Campos, S. (2022). BDDBlast—A Memory Efficient Architecture for Pairwise Alignments. In: Scherer, N.M., de Melo-Minardi, R.C. (eds) Advances in Bioinformatics and Computational Biology. BSB 2022. Lecture Notes in Computer Science(), vol 13523. Springer, Cham. https://doi.org/10.1007/978-3-031-21175-1_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-21175-1_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-21174-4

  • Online ISBN: 978-3-031-21175-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation