Sequence Alignment and Mapping Algorithms used in Big Data Bioinformatics
20 / 13
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
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
Ait Lahcen, L., Yamak, Z., and Morgenstern, B. (2013). DIALIGN at
GOBICS Multiple sequence alignment using various sources of
external information. Nucleic Acids Research, 41(W1), W3–W7.
Altschul, S.F., Gish, W., Miller, W., Myers, E.W., and Lipman, D.J.
(1990). Basic local alignment search tool. Journal of Molecular
Biology, 215(3), 403-410.
Baker, D.N., and Langmead, B. (2019). Dashing: Fast and accurate
genomic distances with HyperLogLog. Genome Biology, 20, 265.
Brinda, K. (2016). Novel computational techniques for mapping
and classifying next-generation sequencing data. (Doctoral
dissertation). University Paris-Est.
Broder, A.Z. (1997). On the resemblance and containment of documents.
In Proceedings. Compression and Complexity of SEQUENCES
1997 (Cat. No. 97TB100171) (pp. 21-29). IEEE.
Burrows, M., and Wheeler, D.J. (1994). A block-sorting lossless data
compression algorithm (SRC Research Report No. 124). Palo
Alto, CA.
Canzar, S., and Salzberg, S.L. (2017). Short read mapping: An
algorithmic tour. Proceedings of the IEEE, 105(3), 436-458.
Cazenave, T. (2007). Overestimation for multiple sequence alignment.
In Proceedings of the IEEE Symposium on Computational
Intelligence in Bioinformatics and Computational Biology (pp.
159-164).
Durbin, R., Eddy, S.R., Krogh, A., and Mitchison, G. (1998). Biological
sequence analysis: Probabilistic models of proteins and nucleic
acids. Cambridge University Press.
Ferragina, P., and Manzini, G. (2000). Opportunistic data structures
with applications. In Proceedings of the 41st IEEE Symposium on
Foundations of Computer Science (pp. 390-398). IEEE Computer
Society.
Feng, D.F., and Doolittle, R.F. (1987). Progressive sequence alignment
as a prerequisite to correct phylogenetic trees. Journal of
Molecular Evolution, 25, 351-360.
Flajolet, P., Fusy, E., Gandouet, O., and Meunier, F. (2007).
HyperLogLog: The analysis of a near-optimal cardinality
estimation algorithm. In Analysis of Algorithms (pp. 127-146).
Gibbs, A. J., and McIntyre, G.A. (1970). The diagram, a method for
comparing sequences. European Journal of Biochemistry, 16,
1-11.
Gotoh, O. (1982). An improved algorithm for matching biological
sequences. Journal of Molecular Biology, 162, 705-708.
Indyk, P., and Motwani, R. (1998). Approximate nearest neighbors:
Towards removing the curse of dimensionality. In Proceedings of
the Thirtieth Annual ACM Symposium on Theory of Computing
(pp. 604-613). ACM.
Ioffe, M.V., Nishnianidze, D.N., and Valinevich, P.A. (2010). A new
exactly solvable two-dimensional quantum model not amenable to
separation of variables. Journal of Physics A: Mathematical and
Theoretical, 43, 485303.
Kucherov, G. (2019). Evolution of biosequence search algorithms: A
brief survey. Bioinformatics, 35(19), 3547-3552.
Kucherov, G., Salikhov, K., and Tsur, D. (2016). Approximate string
matching using a bidirectional index. Theoretical Computer
Science, 638, 145-158.
Lam, T. W., Li, R., Tam, A., Wong, S., Wu, E., and Yiu, S.M. (2009).
High throughput short read alignment via bi-directional BWT.
In Proceedings of the IEEE International Conference on
Bioinformatics and Biomedical Engineering (pp. 31-36).
Langmead, B., and Nellore, A. (2018). Cloud computing for genomic
data analysis and collaboration. Nature Reviews Genetics, 19(4),
208-219.
Langmead, B., and Salzberg, S.L. (2012). Fast gapped-read alignment
with Bowtie 2. Nature Methods, 9(4), 357-359.
Lee, C.Y., Chiu, Y.C., Wang, L.B., Kuo, Y.L., Chuang, E.Y., Lai, L.C.,
and Tsai, M.H. (2013). Common applications of next-generation
sequencing technologies in genomic research. Translational
Cancer Research, 2(1), 33-45.
Li, H. (2013). Aligning sequence reads, clone sequences and assembly
contigs with BWA-MEM. arXiv, 1303.3997.
Li, H., and Durbin, R. (2009). Fast and accurate short read alignment
with Burrows–Wheeler transform. Bioinformatics, 25(14),
1754-1760.
Lindner, R., and Friedel, C. C. (2012). A comprehensive evaluation
of alignment algorithms in the context of RNA-seq. PLoS ONE,
7(12), e52403.
Magi, A., Benelli, M., Gozzini, A., Girolami, F., Torricelli, F.,
and Brandi, M.L. (2010). Bioinformatics for next generation
sequencing data. Genes, 1(2), 294-307.
294
Prakash Kumar et al. / Journal of the Indian Society of Agricultural Statistics
Makinen, V., Belazzougui, D., Cunial, F., and Tomescu, A.I. (2015).
Genome-scale algorithm design. Cambridge University Press.
Marco-Sola, S., Sammeth, M., Guigo, R., and Ribeca, P. (2012). The
GEM mapper: Fast, accurate and versatile alignment by filtration.
Nature Methods, 9, 1185-1188.
Morris, R. (1978). Counting large numbers of events in small registers.
Communications of the ACM, 21(10), 840-842.
Morgenstern, B., Zhu, B., Horwege, S., and Leimeister, C.A. (2015).
Estimating evolutionary distances between genomic sequences
from spaced-word matches. Algorithms for Molecular Biology,
10, 5.
Muir, P., Li, S., Lou, S., Wang, D., Spakowicz, D.J., Salichos, L., Zhang,
J., Weinstock, G.M., Isaacs, F., Rozowsky, J., and Gerstein, M.
(2016). The real cost of sequencing: Scaling computation to keep
pace with data generation. Genome Biology, 17, 53.
Neilsen, R., Paul, J. S., Albrechtsen, A., and Song, Y.S. (2011).
Genotype and SNP calling from next-generation sequencing data.
Nature Reviews Genetics, 12, 443-451.
Needleman, S.B., and Wunsch, C.D. (1970). A general method
applicable to the search for similarities in the amino acid sequence
of two proteins. Journal of Molecular Biology, 48, 443-453.
Nowrousian, M. (2010). Next-generation sequencing techniques
for eukaryotic microorganisms: Sequencing-based solutions to
biological problems. Eukaryotic Cell, 9(9), 1300-1310.
Ondov, B.D., Treangen, TJ., Melsted, P., Mallonee, A. B., Bergman,
N. H., Koren, S., and Phillippy, A.M. (2016). Mash: Fast genome
and metagenome distance estimation using MinHash. Genome
Biology, 17(1), 132.
Pathirana, T., Bandara, S., Gamage, G., Gimhana, N., Wickramarachchi,
A., Mallawaarachchi, V., and Perera, I. (2020). Genetic distance
calculation based on locality sensitive hashing. bioRxiv, 2020-04.
https://doi.org/10.1101/2020.04.06.027250
Roberts, M., Hayes, W., Hunt, B.R., Mount, S.M., and Yorke, J.A.
(2004). Reducing storage requirements for biological sequence
comparison. Bioinformatics, 20(18), 3363-3369.
Schleimer, S., Wilkerson, D. S., and Aiken, A. (2003). Winnowing:
Local algorithms for document fingerprinting. In Proceedings of
the ACM SIGMOD International Conference on Management of
Data (pp. 76-85). ACM.
Smith, T.F., and Waterman, M.S. (1981). Identification of common
molecular subsequences. Journal of Molecular Biology, 147,
195-197.
Stephens, Z.D., Lee, S.Y., Faghri, F., Campbell, R.H., Zhai, C., Efron,
M.J., Iyer, R., Schatz, M.C., Sinha, S., and Robinson, G.E. (2015).
Big data: Astronomical or genomical? PLoS Biology, 13(7),
e1002195.
Tørresen, O.K., Star, B., Mier, P., Andrade-Navarro, M.A., Bateman,
A., Jarnot, P., Gruca, A., Grynberg, M., Kajava, A.V., Promponas,
V.J., Anisimova, M., Jakobsen, K.S., and Linke, D. (2019).
Tandem repeats lead to sequence assembly errors and impose
multi-level challenges for genome and protein databases. Nucleic
Acids Research, 47(21), 10994-11006.
Trapnell, C., Pachter, L., and Salzberg, S.L. (2009). TopHat: Discovering
splice junctions with RNA-Seq. Bioinformatics, 25(9), 1105-1111.
Treangen, T.J., and Salzberg, S.L. (2012). Repetitive DNA and next
generation sequencing: Computational challenges and solutions.
Nature Reviews Genetics, 13, 36-46.
Wang, Y., Parthasarathy, S., and Tatikonda, S. (2011). Locality sensitive
outlier detection: A ranking driven approach. In Proceedings of
the IEEE International Conference on Data Engineering.
Wood, D.E., and Salzberg, S.L. (2014). Kraken: Ultrafast metagenomic
sequence classification using exact alignments. Genome Biology,
15, R46.
Zhu, E., Markovtsev, V., Astafiev, A., Khan, A., Ha, C., Łukasiewicz,
W., Foster, A., Sinusoidal, S., Thakur, S., Ortolani, S., Titusz,
Letal, V., Bentley, Z., fpug, hguhlich, long2ice, oisincar, Assa, R.,
Ibraimoski, S., Kumar, R., TianHuan, Q., Rosenthal, M.J., Joshi,
K., Mann, K., JonR, and Halliwell, J. (2024). ekzhu/datasketch:
v1. 5.9. Zenodo.https://doi.org/10.5281/zenodo.11462182
Downloads
Submitted
Published
Issue
Section
How to Cite
