Open Access iconOpen Access



BitmapAligner: Bit-Parallelism String Matching with MapReduce and Hadoop

Mary Aksa1, Junaid Rashid2,*, Muhammad Wasif Nisar1, Toqeer Mahmood3, Hyuk-Yoon Kwon4, Amir Hussain5

1 Department of Computer Science, COMSATS University Islamabad, Wah, 47040, Pakistan
2 Department of Computer Science, AIR University Islamabad, Aerospace and Aviation Campus Kamra, 43570, Pakistan
3 Department of Computer Science, National Textile University, Faisalabad, 37610, Pakistan
4 Department of Industrial Engineering and Research Center for Electrical and Information Technology, Seoul National University of Science and Technology, Nowon-Gu, Seoul, 01811, Korea
5 Data Science and Cyber Analytics Research Group, Edinburgh Napier University, Edinburgh, EH11 4DY, UK

* Corresponding Author: Junaid Rashid. Email: email

Computers, Materials & Continua 2021, 68(3), 3931-3946.


Advancements in next-generation sequencer (NGS) platforms have improved NGS sequence data production and reduced the cost involved, which has resulted in the production of a large amount of genome data. The downstream analysis of multiple associated sequences has become a bottleneck for the growing genomic data due to storage and space utilization issues in the domain of bioinformatics. The traditional string-matching algorithms are efficient for small sized data sequences and cannot process large amounts of data for downstream analysis. This study proposes a novel bit-parallelism algorithm called BitmapAligner to overcome the issues faced due to a large number of sequences and to improve the speed and quality of multiple sequence alignment (MSA). The input files (sequences) tested over BitmapAligner can be easily managed and organized using the Hadoop distributed file system. The proposed aligner converts the test file (the whole genome sequence) into binaries of an equal length of the sequence, line by line, before the sequence alignment processing. The Hadoop distributed file system splits the larger files into blocks, based on a defined block size, which is 128 MB by default. BitmapAligner can accurately process the sequence alignment using the bitmask approach on large-scale sequences after sorting the data. The experimental results indicate that BitmapAligner operates in real time, with a large number of sequences. Moreover, BitmapAligner achieves the exact start and end positions of the pattern sequence to test the MSA application in the whole genome query sequence. The MSA’s accuracy is verified by the bitmask indexing property of the bit-parallelism extended shifts (BXS) algorithm. The dynamic and exact approach of the BXS algorithm is implemented through the MapReduce function of Apache Hadoop. Conversely, the traditional seeds-and-extend approach faces the risk of errors while identifying the pattern sequences’ positions. Moreover, the proposed model resolves the large-scale data challenges that are covered through MapReduce in the Hadoop framework. Hive, Yarn, HBase, Cassandra, and many other pertinent flavors are to be used in the future for data structuring and annotations on the top layer of Hadoop since Hadoop is primarily used for data organization and handles text documents.


Cite This Article

APA Style
Aksa, M., Rashid, J., Nisar, M.W., Mahmood, T., Kwon, H. et al. (2021). Bitmapaligner: bit-parallelism string matching with mapreduce and hadoop. Computers, Materials & Continua, 68(3), 3931-3946.
Vancouver Style
Aksa M, Rashid J, Nisar MW, Mahmood T, Kwon H, Hussain A. Bitmapaligner: bit-parallelism string matching with mapreduce and hadoop. Comput Mater Contin. 2021;68(3):3931-3946
IEEE Style
M. Aksa, J. Rashid, M.W. Nisar, T. Mahmood, H. Kwon, and A. Hussain "BitmapAligner: Bit-Parallelism String Matching with MapReduce and Hadoop," Comput. Mater. Contin., vol. 68, no. 3, pp. 3931-3946. 2021.


cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 2451


  • 1400


  • 0


Share Link