Sequence Alignment and Mapping Algorithms used in Big Data Bioinformatics
95 / 138
Keywords:
BWT; FM-Index; HyperLogLog; MinHash and LSHAbstract
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
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