Sequence Alignment and Mapping Algorithms used in Big Data Bioinformatics


95 / 138

Authors

  • Prakash Kumar ICAR-Indian Agricultural Statistics Research Institute, New Delhi
  • Raju Kumar ICAR-Indian Agricultural Statistics Research Institute, New Delhi
  • Deepak Singh ICAR-Indian Agricultural Statistics Research Institute, New Delhi
  • Himadri Shekhar Roy ICAR-Indian Agricultural Statistics Research Institute, New Delhi
  • Md. Yeasin ICAR-Indian Agricultural Statistics Research Institute, New Delhi

https://doi.org/10.56093/JISAS.V79I3.8

Keywords:

BWT; FM-Index; HyperLogLog; MinHash and LSH

Abstract

The rapid evolution of next-generation sequencing (NGS) technologies has transformed genomics into a data-intensive science, generating 
unprecedented volumes of sequencing data and creating major computational challenges for efficient read mapping and alignment. This review 
focuses on recent advances in mapping and alignment algorithmic strategies that have emerged in response to increasing sequencing throughput, 
longer read lengths, and the growing demand for rapid and accurate genomic analyses. Special emphasis is placed on lightweight and sketch-based 
approaches, including MinHash and HyperLogLog, which enable efficient similarity estimation and large-scale dataset comparison, particularly in 
metagenomic applications. Key indexing and compression techniques such as the Burrows–Wheeler Transform (BWT), FM-Index, and Locality
Sensitive Hashing (LSH) are critically discussed for their roles in reducing memory requirements and accelerating alignment while maintaining 
high sensitivity and tolerance to mismatches. Alignment tools are compared based on essential performance metrics, including mapping sensitivity, 
proportion of appropriately paired reads, computational time, memory usage, and robustness in handling tandem repeat-rich reads. This review 
synthesizes recent methodological innovations aimed at addressing big-data challenges in bioinformatics and provides insights to support the 
development of next-generation hybrid aligners that integrate emerging sketching and indexing paradigms for scalable and accurate genomic analysis.

Downloads

Download data is not yet available.

References

1. Ait Lahcen, L., Yamak, Z., and Morgenstern, B. (2013). DIALIGN at

2. GOBICS Multiple sequence alignment using various sources of

3. external information. Nucleic Acids Research, 41(W1), W3–W7.

4. Altschul, S.F., Gish, W., Miller, W., Myers, E.W., and Lipman, D.J.

5. (1990). Basic local alignment search tool. Journal of Molecular

6. Biology, 215(3), 403-410.

7. Baker, D.N., and Langmead, B. (2019). Dashing: Fast and accurate

8. genomic distances with HyperLogLog. Genome Biology, 20, 265.

9. Brinda, K. (2016). Novel computational techniques for mapping

10. and classifying next-generation sequencing data. (Doctoral

11. dissertation). University Paris-Est.

12. Broder, A.Z. (1997). On the resemblance and containment of documents.

13. In Proceedings. Compression and Complexity of SEQUENCES

14. 1997 (Cat. No. 97TB100171) (pp. 21-29). IEEE.

15. Burrows, M., and Wheeler, D.J. (1994). A block-sorting lossless data

16. compression algorithm (SRC Research Report No. 124). Palo

17. Alto, CA.

18. Canzar, S., and Salzberg, S.L. (2017). Short read mapping: An

19. algorithmic tour. Proceedings of the IEEE, 105(3), 436-458.

20. Cazenave, T. (2007). Overestimation for multiple sequence alignment.

21. In Proceedings of the IEEE Symposium on Computational

22. Intelligence in Bioinformatics and Computational Biology (pp.

23. 159-164).

24. Durbin, R., Eddy, S.R., Krogh, A., and Mitchison, G. (1998). Biological

25. sequence analysis: Probabilistic models of proteins and nucleic

26. acids. Cambridge University Press.

27. Ferragina, P., and Manzini, G. (2000). Opportunistic data structures

28. with applications. In Proceedings of the 41st IEEE Symposium on

29. Foundations of Computer Science (pp. 390-398). IEEE Computer

30. Society.

31. Feng, D.F., and Doolittle, R.F. (1987). Progressive sequence alignment

32. as a prerequisite to correct phylogenetic trees. Journal of

33. Molecular Evolution, 25, 351-360.

34. Flajolet, P., Fusy, E., Gandouet, O., and Meunier, F. (2007).

35. HyperLogLog: The analysis of a near-optimal cardinality

36. estimation algorithm. In Analysis of Algorithms (pp. 127-146).

37. Gibbs, A. J., and McIntyre, G.A. (1970). The diagram, a method for

38. comparing sequences. European Journal of Biochemistry, 16,

39. 1-11.

40. Gotoh, O. (1982). An improved algorithm for matching biological

41. sequences. Journal of Molecular Biology, 162, 705-708.

42. Indyk, P., and Motwani, R. (1998). Approximate nearest neighbors:

43. Towards removing the curse of dimensionality. In Proceedings of

44. the Thirtieth Annual ACM Symposium on Theory of Computing

45. (pp. 604-613). ACM.

46. Ioffe, M.V., Nishnianidze, D.N., and Valinevich, P.A. (2010). A new

47. exactly solvable two-dimensional quantum model not amenable to

48. separation of variables. Journal of Physics A: Mathematical and

49. Theoretical, 43, 485303.

50. Kucherov, G. (2019). Evolution of biosequence search algorithms: A

51. brief survey. Bioinformatics, 35(19), 3547-3552.

52. Kucherov, G., Salikhov, K., and Tsur, D. (2016). Approximate string

53. matching using a bidirectional index. Theoretical Computer

54. Science, 638, 145-158.

55. Lam, T. W., Li, R., Tam, A., Wong, S., Wu, E., and Yiu, S.M. (2009).

56. High throughput short read alignment via bi-directional BWT.

57. In Proceedings of the IEEE International Conference on

58. Bioinformatics and Biomedical Engineering (pp. 31-36).

59. Langmead, B., and Nellore, A. (2018). Cloud computing for genomic

60. data analysis and collaboration. Nature Reviews Genetics, 19(4),

61. 208-219.

62. Langmead, B., and Salzberg, S.L. (2012). Fast gapped-read alignment

63. with Bowtie 2. Nature Methods, 9(4), 357-359.

64. Lee, C.Y., Chiu, Y.C., Wang, L.B., Kuo, Y.L., Chuang, E.Y., Lai, L.C.,

65. and Tsai, M.H. (2013). Common applications of next-generation

66. sequencing technologies in genomic research. Translational

67. Cancer Research, 2(1), 33-45.

68. Li, H. (2013). Aligning sequence reads, clone sequences and assembly

69. contigs with BWA-MEM. arXiv, 1303.3997.

70. Li, H., and Durbin, R. (2009). Fast and accurate short read alignment

71. with Burrows–Wheeler transform. Bioinformatics, 25(14),

72. 1754-1760.

73. Lindner, R., and Friedel, C. C. (2012). A comprehensive evaluation

74. of alignment algorithms in the context of RNA-seq. PLoS ONE,

75. 7(12), e52403.

76. Magi, A., Benelli, M., Gozzini, A., Girolami, F., Torricelli, F.,

77. and Brandi, M.L. (2010). Bioinformatics for next generation

78. sequencing data. Genes, 1(2), 294-307.

79. 294

80. Prakash Kumar et al. / Journal of the Indian Society of Agricultural Statistics

81. Makinen, V., Belazzougui, D., Cunial, F., and Tomescu, A.I. (2015).

82. Genome-scale algorithm design. Cambridge University Press.

83. Marco-Sola, S., Sammeth, M., Guigo, R., and Ribeca, P. (2012). The

84. GEM mapper: Fast, accurate and versatile alignment by filtration.

85. Nature Methods, 9, 1185-1188.

86. Morris, R. (1978). Counting large numbers of events in small registers.

87. Communications of the ACM, 21(10), 840-842.

88. Morgenstern, B., Zhu, B., Horwege, S., and Leimeister, C.A. (2015).

89. Estimating evolutionary distances between genomic sequences

90. from spaced-word matches. Algorithms for Molecular Biology,

91. 10, 5.

92. Muir, P., Li, S., Lou, S., Wang, D., Spakowicz, D.J., Salichos, L., Zhang,

93. J., Weinstock, G.M., Isaacs, F., Rozowsky, J., and Gerstein, M.

94. (2016). The real cost of sequencing: Scaling computation to keep

95. pace with data generation. Genome Biology, 17, 53.

96. Neilsen, R., Paul, J. S., Albrechtsen, A., and Song, Y.S. (2011).

97. Genotype and SNP calling from next-generation sequencing data.

98. Nature Reviews Genetics, 12, 443-451.

99. Needleman, S.B., and Wunsch, C.D. (1970). A general method

100. applicable to the search for similarities in the amino acid sequence

101. of two proteins. Journal of Molecular Biology, 48, 443-453.

102. Nowrousian, M. (2010). Next-generation sequencing techniques

103. for eukaryotic microorganisms: Sequencing-based solutions to

104. biological problems. Eukaryotic Cell, 9(9), 1300-1310.

105. Ondov, B.D., Treangen, TJ., Melsted, P., Mallonee, A. B., Bergman,

106. N. H., Koren, S., and Phillippy, A.M. (2016). Mash: Fast genome

107. and metagenome distance estimation using MinHash. Genome

108. Biology, 17(1), 132.

109. Pathirana, T., Bandara, S., Gamage, G., Gimhana, N., Wickramarachchi,

110. A., Mallawaarachchi, V., and Perera, I. (2020). Genetic distance

111. calculation based on locality sensitive hashing. bioRxiv, 2020-04.

112. https://doi.org/10.1101/2020.04.06.027250

113. Roberts, M., Hayes, W., Hunt, B.R., Mount, S.M., and Yorke, J.A.

114. (2004). Reducing storage requirements for biological sequence

115. comparison. Bioinformatics, 20(18), 3363-3369.

116. Schleimer, S., Wilkerson, D. S., and Aiken, A. (2003). Winnowing:

117. Local algorithms for document fingerprinting. In Proceedings of

118. the ACM SIGMOD International Conference on Management of

119. Data (pp. 76-85). ACM.

120. Smith, T.F., and Waterman, M.S. (1981). Identification of common

121. molecular subsequences. Journal of Molecular Biology, 147,

122. 195-197.

123. Stephens, Z.D., Lee, S.Y., Faghri, F., Campbell, R.H., Zhai, C., Efron,

124. M.J., Iyer, R., Schatz, M.C., Sinha, S., and Robinson, G.E. (2015).

125. Big data: Astronomical or genomical? PLoS Biology, 13(7),

126. e1002195.

127. Tørresen, O.K., Star, B., Mier, P., Andrade-Navarro, M.A., Bateman,

128. A., Jarnot, P., Gruca, A., Grynberg, M., Kajava, A.V., Promponas,

129. V.J., Anisimova, M., Jakobsen, K.S., and Linke, D. (2019).

130. Tandem repeats lead to sequence assembly errors and impose

131. multi-level challenges for genome and protein databases. Nucleic

132. Acids Research, 47(21), 10994-11006.

133. Trapnell, C., Pachter, L., and Salzberg, S.L. (2009). TopHat: Discovering

134. splice junctions with RNA-Seq. Bioinformatics, 25(9), 1105-1111.

135. Treangen, T.J., and Salzberg, S.L. (2012). Repetitive DNA and next

136. generation sequencing: Computational challenges and solutions.

137. Nature Reviews Genetics, 13, 36-46.

138. Wang, Y., Parthasarathy, S., and Tatikonda, S. (2011). Locality sensitive

139. outlier detection: A ranking driven approach. In Proceedings of

140. the IEEE International Conference on Data Engineering.

141. Wood, D.E., and Salzberg, S.L. (2014). Kraken: Ultrafast metagenomic

142. sequence classification using exact alignments. Genome Biology,

143. 15, R46.

144. Zhu, E., Markovtsev, V., Astafiev, A., Khan, A., Ha, C., Łukasiewicz,

145. W., Foster, A., Sinusoidal, S., Thakur, S., Ortolani, S., Titusz,

146. Letal, V., Bentley, Z., fpug, hguhlich, long2ice, oisincar, Assa, R.,

147. Ibraimoski, S., Kumar, R., TianHuan, Q., Rosenthal, M.J., Joshi,

148. K., Mann, K., JonR, and Halliwell, J. (2024). ekzhu/datasketch:

149. v1. 5.9. Zenodo.https://doi.org/10.5281/zenodo.11462182

Downloads

Published

2026-07-27

Issue

Section

Articles

How to Cite

Prakash Kumar, Raju Kumar, Deepak Singh, Himadri Shekhar Roy, & Md. Yeasin. (2026). Sequence Alignment and Mapping Algorithms used in Big Data Bioinformatics. Journal of the Indian Society of Agricultural Statistics, 79(03), 279-294. https://doi.org/10.56093/JISAS.V79I3.8
Citation