Journal of Applied Research in Electrical Engineering

Current Issue

By Issue

By Author

By Subject

Author Index

Keyword Index

About Journal

Aims and Scope

Editorial Board

Publication Ethics

Indexing and Abstracting

Related Links

FAQ

Peer Review Process

News

Review Guide

Publons Membership Guide

A High-Performance MEMRISTOR-Based Smith-Waterman DNA Sequence Alignment Using FPNI Structure

Document Type : Research article

Authors

1 Department of Information and Communication Technology, Tallinn University of Technology, Tallinn 19086, Estonia

2 Reliable and Smart Systems Lab (RSS), Shahid Bahonar University of Kerman, Kerman 7616913439, Iran

Abstract

It is crucial to detect potential overlaps between any pair of the input reads and a reference genome in genome sequencing, but it takes an excessive amount of time, especially for ultra-long reads. Even though lots of acceleration designs are proposed for different sequencing methods, several crucial drawbacks impact these methods. One of these difficulties stems from the difference in read lengths that may take place as input data. In this work, we propose a new Race-logic implementation of the seed extension kernel of the BWA-MEM alignment algorithm. The first proposed method does not need reconfiguration to execute the seed extension kernel for different read lengths. We use MEMRISTORs instead of the conventional, complementary metal-oxide-semiconductor (CMOS), which leads to lower area overhead and power consumption. Also, we benefit from Field-Programmable Nanowire Interconnect Architecture as our matrix output resulting in a flexible output that bypasses the reconfiguration procedure of the system for reads with different lengths. Considering the power, area, and delay efficiency, we gain better results than other state-of-the-art implementations. Consequently, we gain up to 22x speedup compared to the state-of-the-art systolic arrays, 600x speed up considering different seed lengths of the previous state-of-the-art proposed methods, at least 10x improvements in area overhead, and 105x improvements in power.

Highlights

  • A new Race-logic implementation of the seed extension kernel of BWA-MEM alignment algorithm
  • A newly proposed method that does not need reconfiguration to execute the seed extension kernel for different read lengths as input
  • Lower area overhead and power consumption by using MEMRISTORs instead of the conventional, complementary metal-oxide-semiconductor (CMOS)
  • Using a Field-Programmable Nanowire Interconnect Architecture as the matrix output
  • The flexible output bypasses the reconfiguration procedure of the system for reads with different lengths

Keywords

Main Subjects

References
[1]  M. Taheri, and A. Mahani, "Development and hardware acceleration of a novel 2-D BWA-MEM DNA sequencing alignment algorithm", in The First Conference on Applied Research in Electrical Engineering, Iran, 2021.
[2]  J. Giles, "Computational social science: Making the links", Nature, vol. 488, no. 7412, pp. 448-450, 2012.
[3]  Z. D. Stephens, S. Y. Lee, F. Faghri, R. H. Campbell, C. Zhai, M. J Efron, R. Iyer, M. C. Schatz, S. Sinha, and G. E. Robinson, "Big data: astronomical or genomical?", PLoS Biology, vol. 13, no. 7, 2015.
[4]  B. Langmead, C. Trapnell, M. Pop, and S. L. Salzberg. "Ultrafast and memory-efficient alignment of short dna sequences to the human genome", Genome Biology, vol. 10, no. 3, pp. 1-10, 2009.
[5]  H. Li, and R. Durbin, "Fast and accurate short read alignment with burrows– wheeler transform",  Bioinformatics, vol. 25, no. 14, pp. 1754–1760, 2009.
[6]  H. Li, J. Ruan, and R. Durbin, "Mapping short dna sequencing reads and calling variants using mapping quality scores", Genome Research, vol. 18, no. 11, pp. 1851– 1858, 2008.
[7]  R. Li, C. Yu, Y. Li, T. Lam, S. Yiu, K. Kristiansen, and J. Wang. "Soap2: an improved ultrafast tool for short read alignment", Bioinformatics, vol. 25, no. 15, pp. 1966–1967, 2009.
[8]  H. Li, "Aligning sequence reads, clone sequences and assembly contigs with bwa-mem", arXiv preprint arXiv:1303.3997, 2013.
[9]  T. .F Smith, M. S. Waterman, "Identification of common molecular subsequences", Journal of Molecular Biology, vol. 147, no. 1, pp. 195–197, 1981.
[10]  T. W Lam, W. Sung, S. Tam, C. Wong, and S. Yiu, "Compressed indexing and local alignment of dna", Bioinformatics, vol. 24, no. 6, pp. 791– 797, 2008.
[11]  W. J. Kent, "Blat—the blast-like alignment tool", Genome Research, vol. 12, no. 4, pp. 656– 664, 2002.
[12]  V. Marx, "Biology: The big challenges of big data", vol. 498, no. 7453, pp. 255-260, 2013.
[13]  S. F. Altschul, T. L. Madden, A. A. Schäffer, J. Zhang, Z. Zhang, W. Miller, and D. J. Lipman, "Gapped blast and psi-blast: a new generation of protein database search programs", Nucleic Acids research, vol. 25, no. 17, pp. 3389–3402, 1997.
[14]  W. R. Pearson, and D. J. Lipman, "Improved tools for biological sequence comparison", Proceedings of the National Academy of Sciences, vol. 85, no. 8, pp. 2444–2448, 1988.
[15]  W. Wilbur, and D. J. Lipman, "The context dependent comparison of biological sequences", SIAM Journal on Applied Mathematics, vol. 44, no. 3, pp. 557–567, 1984.
[16]  R. K. Singh, DL Hoffman, S. G. Tell, and C. Thomas White, "Bioscan: a network sharable computational resource for searching biosequence databases", Bioinformatics, vol. 12, no. 3, pp.191–196, 1996.
[17]  A. Madhavan, T. Sherwood, and D. Strukov, "Race logic: A hardware acceleration for dynamic programming algorithms", in 2014 ACM/IEEE 41st International Symposium on Computer Architecture, 2014, pp. 517–528.
[18]  E. Rucci, C. Garcia, G. Botella, A. De Giusti, M. Naiouf, and M. Prieto-Matias, "Swifold: Smith-waterman implementation on fpga with opencl for long dna sequences", BMC systems biology, vol. 12, no. 5, pp. 96, 2018.
[19]  F. Zokaee, H. R Zarandi, and L. Jiang, "Aligner: A process-in-memory architecture for short read alignment in rerams," IEEE Computer Architecture Letters, vol. 17, no. 2, pp. 237–240, 2018.
[20]  M. Taheri, M. S. Ansari, S. Magierowski, and A. Mahani, "Hardware acceleration of the novel two dimensional burrows-wheeler aligner algorithm with maximal exact matches seed extension kernel”, IET Circuits, Devices and Systems, vol. 15, no. 2, pp. 94-103, 2021.
[21]  M. Alser, H. Hassan, H. Xin, O. Ergin, O. Mutlu, and C. Alkan, “Gatekeeper: a new hardware architecture for accelerating pre-alignment in dna short read mapping”, Bioinformatics, vol. 33, no. 21, pp. 3355–3363, 2017.
[22]  M. Farrar, “Striped smith–waterman speeds database searches six times over other simd implementations,” Bioinformatics, vol. 23, no. 2, pp. 156–161, 2006.
[23]  S. S. Banerjee, M. El-Hadedy, J. Bin Lim, Z. T. Kalbarczyk, D. Chen, S. S Lumetta, and R K Iyer, “Asap: accelerated short-read alignment on programmable hardware”, IEEE Transactions on Computers, vol. 68, no. 3, pp. 331–346, 2018.
[24]  E. J. Houtgast, V. Sima, K. Bertels, and Z. Al-Ars, “An fpga-based systolic array to accelerate the bwa-mem genomic mapping algorithm”, in 2015 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS), 2015, pp. 221–227.
[25]  E. J. Houtgast, V. Sima, K. Bertels, and Z. Al-Ars, “Hardware acceleration of bwa-mem genomic short read mapping for longer read lengths”, Computational biology and chemistry, vol. 75, pp. 54–64, 2018.
[26]  E. J. Houtgast, V. Sima, K. Bertels, and Z. Al-Ars, “Gpu accelerated bwa-mem genomic mapping algorithm using adaptive load balancing”, in International Conference on Architecture of Computing Systems, 2016, pp. 130– 142.
[27]  E. J. Houtgast, V. Sima, G. Marchiori, K. Bertels, and Z. Al-Ars, “Power-efficiency analysis of accelerated bwa-mem implementations on heterogeneous computing platforms”, in 2016 International Conference on ReConFigurable Computing and FPGAs (ReConFig), 2016, pp. 1–8.
[28]  C. Pham-Quoc, B. Kieu-Do, and T. Ngoc Thinh, “A high-performance fpga-based bwa-mem dna sequence alignment”, Concurrency and Computation: Practice and Experience, vol. 33, no. 2, e5328.
[29]  A. Bayat, B. Gaëta, A. Ignjatovic, and S. Parameswaran, “Pairwise alignment of nucleotide sequences using maximal exact matches”, BMC bioinformatics, vol. 20, no. 1, pp. 1-15, 2019.
[30]  H. Zandevakili and A. Mahani, “A new asic structure with self-repair capability using field-programmable nanowire interconnect architecture”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 26, no. 11, pp. 2268–2278, 2018.
[31]  C. Wang, R. Yan, Xi. Wang, Jing-Na Si, and Ziding Zhang, “Comparison of linear gap penalties and profile-based variable gap penalties in profile–profile alignments”, Computational biology and chemistry, vol. 35, no. 5, pp. 308–318, 2011.
[32]  S. Henikoff and J. G Henikoff, “Amino acid substitution matrices from protein blocks”, Proceedings of the National Academy of Sciences, vol. 89, no. 22, pp. 10915– 10919, 1992.
[33]  W. Sung, “Algorithms in bioinformatics: A practical introduction,” CRC Press, 2009.
[34]  G. Navarro, “A guided tour to approximate string matching”, ACM computing surveys (CSUR), vol. 33, no. 1, pp. 31–88, 2001.
[35]  V. I Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals”, in Soviet physics doklady, vol. 10, no.8, pp. 707–710, 1966.
[36]  L. Chua, “Memristor-the missing circuit element”, IEEE Transactions on circuit theory, vol. 18, no. 5, pp. 507–519, 1971.
[37]  L. O. Chua, and S. Mo Kang, “Memristive devices and systems”, Proceedings of the IEEE, vol. 64, no. 2, pp. 209–223, 1976.
[38]  A. C Torrezan, J. Paul Strachan, G. Medeiros-Ribeiro, and R S. Williams, “Sub-nanosecond switching of a tantalum oxide memristor”, Nanotechnology, vol. 22, no. 48, pp. 1-7, 2011.
[39]  J. Borghetti, Z. Li, J. Straznicky, X. Li, D. AA Ohlberg, W. Wu, D. R. Stewart, and R. S. Williams, “A hybrid nanomemristor/transistor logic circuit capable of self-programming”, Proceedings of the National Academy of Sciences, vol. 106, no. 6, pp. 1699–1703, 2009.
[40]  G. S. Snider, and R. S. Williams, “Nano/cmos architectures using a fieldprogrammable nanowire interconnect”, Nanotechnology, vol. 18, no. 3, 035204, 2007.
Journal of Applied Research in Electrical Engineering
Volume 1, Issue 1
Winter and Spring 2022
January 2022
Pages 59-68
Files
History
  • Receive Date: 31 December 2020
  • Revise Date: 27 April 2021
  • Accept Date: 27 May 2021
Share
How to cite
Statistics