Whole-Genome Alignment: Methods, Challenges, and Future Directions
Source abstract
Abstract
Whole-genome alignment (WGA) is a critical process in comparative genomics, facilitating the detection of genetic variants and aiding our understanding of evolution. This paper offers a detailed overview and categorization of WGA techniques, encompassing suffix tree-based, hash-based, anchor-based, and graph-based methods. It elaborates on the algorithmic properties of these tools, focusing on performance and methodological aspects. This paper underscores the latest progress in WGA, emphasizing the increasing capacity to manage the growing intricacy and volume of genomic data. However, the field still grapples with computational and biological hurdles affecting the precision and speed of WGA. We explore these challenges and potential future solutions. This paper aims to provide a comprehensive resource for researchers, deepening our understanding of WGA tools and their applications, constraints, and prospects.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Genomics and Phylogenetic Studies · Biofuel production and bioconversion · Chromosomal and Genetic Variations
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Animal Biosciences Department, University of Guelph, Guelph, ON N1G 2W1, Canada
School of Information Science & Engineering, Chongqing Jiaotong University, Chongqing 400074, China
School of Information Science and Engineering, University of Jinan, Jinan 250022, China
Shandong Provincial Key Laboratory of Network-Based Intelligent Computing, Jinan 250022, China
Funding
National Natural Science Foundation of China · Shandong Natural Science Foundation in China · Science and Technology on Underwater Vehicle Technology Laboratory
References (87)
Show source-provided references
1. Guerfali, F., Laouini, D., Boudabous, A., and Tekaia, F. (2019). Designing and running an advanced Bioinformatics and genome analyses course in Tunisia. PLoS Comput. Biol., 15.10.1371/journal.pcbi.1006373 ↗
2. Human Genome Sequencing at the Population Scale: A Primer on High-Throughput DNA Sequencing and Analysis10.1093/aje/kww224 ↗
3. A general method applicable to the search for similarities in the amino acid sequence of two proteins10.1016/0022-2836(70)90057-4 ↗
4. Identification of common molecular subsequences10.1016/0022-2836(81)90087-5 ↗
5. Tandem repeats lead to sequence assembly errors and impose multi-level challenges for genome and protein databases10.1093/nar/gkz841 ↗
6. Medina-Medina, N., Broka, A., Lacey, S., Lin, H., Klings, E., Baldwin, C., Steinberg, M., and Sebastiani, P. (2012, January 28–30). Comparing Bowtie and BWA to align short reads from a RNA-Seq experiment. Proceedings of the 6th International Conference on Practical Applications of Computational Biology & Bioinformatics, Salamanca, Spain.10.1007/978-3-642-28839-5_23 ↗
7. Advantages of genome sequencing by long-read sequencer using SMRT technology in medical area10.1007/s13577-017-0168-8 ↗
8. The Medical Genome Reference Bank contains whole genome and phenotype data of 2570 healthy elderly10.1038/s41467-019-14079-0 ↗
9. International network of cancer genome projects10.1038/nature08987 ↗
10. Mouse Genome Database (MGD): Knowledgebase for mouse–human comparative biology10.1093/nar/gkaa1083 ↗
11. Expanded encyclopaedias of DNA elements in the human and mouse genomes10.1038/s41586-020-2493-4 ↗
12. DIALIGN 2: Improvement of the segment-to-segment approach to multiple sequence alignment10.1093/bioinformatics/15.3.211 ↗
13. Fast algorithms for large-scale genome alignment and comparison10.1093/nar/30.11.2478 ↗
14. Algorithms on stings, trees, and sequences: Computer science and computational biology10.1145/270563.571472 ↗
15. Relative Suffix Trees10.1093/comjnl/bxx108 ↗
16. Practical methods for constructing suffix trees10.1007/s00778-005-0154-8 ↗
17. Alignment of whole genomes10.1093/nar/27.11.2369 ↗
18. Marcais, G., Delcher, A.L., Phillippy, A.M., Coston, R., Salzberg, S.L., and Zimin, A. (2018). MUMmer4: A fast and versatile genome alignment system. PLoS Comput. Biol., 14.10.1371/journal.pcbi.1005944 ↗
19. Kurtz, S., Phillippy, A., Delcher, A.L., Smoot, M., Shumway, M., Antonescu, C., and Salzberg, S.L. (2004). Versatile and open software for comparing large genomes. Genome Biol., 5.10.1186/gb-2004-5-2-r12 ↗
20. Improved pea reference genome and pan-genome highlight genomic features and evolutionary characteristics10.1038/s41588-022-01172-2 ↗
21. Sequence comparison alignment-free approach based on suffix tree and L-words frequency10.1100/2012/450124 ↗
22. Compressed full-text indexes10.1145/1216370.1216372 ↗
23. Multiple sequence alignment based on a suffix tree and center-star strategy: A linear method for multiple nucleotide sequence alignment on spark parallel framework10.1089/cmb.2017.0040 ↗
24. An Algorithm for DNA Multiple Sequence Alignment Based on Center Star Method and Keyword Tree
25. Multiple sequence alignment modeling: Methods and applications10.1093/bib/bbv099 ↗
26. Thompson, J.D., Linard, B., Lecompte, O., and Poch, O. (2011). A comprehensive benchmark study of multiple sequence alignment methods: Current challenges and future perspectives. PLoS ONE, 6.10.1371/journal.pone.0018093 ↗
27. Mauve: Multiple alignment of conserved genomic sequence with rearrangements10.1101/gr.2289704 ↗
28. LAGAN and Multi-LAGAN: Efficient tools for large-scale multiple alignment of genomic DNA10.1101/gr.926603 ↗
29. An adaptive multi-element generalized polynomial chaos method for stochastic differential equations10.1016/j.jcp.2005.03.023 ↗
30. Sparse dynamic programming I: Linear cost functions10.1145/146637.146650 ↗
31. Popendorf, K., Tsuyoshi, H., Osana, Y., and Sakakibara, Y. (2010). Murasaki: A fast, parallelizable algorithm to find anchors from multiple genomes. PLoS ONE, 5.10.1371/journal.pone.0012651 ↗
32. Darling, A.E., Mau, B., and Perna, N.T. (2010). progressiveMauve: Multiple genome alignment with gene gain, loss and rearrangement. PLoS ONE, 5.10.1371/journal.pone.0011147 ↗
33. CLUSTAL W: Improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice10.1093/nar/22.22.4673 ↗
34. BLAST 2 Sequences, a new tool for comparing protein and nucleotide sequences10.1111/j.1574-6968.1999.tb13575.x ↗
35. PatternHunter: Faster and more sensitive homology search10.1093/bioinformatics/18.3.440 ↗
36. Human–mouse alignments with BLASTZ10.1101/gr.809403 ↗
37. Harris, R.S. (2007). Improved Pairwise Alignment of Genomic DNA, The Pennsylvania State University.
38. Improving read alignment through the generation of alternative reference via iterative strategy10.1038/s41598-020-74526-7 ↗
39. Scalable multiple whole-genome alignment and locally collinear block construction with SibeliaZ10.1038/s41467-020-19777-8 ↗
40. DIALIGN at GOBICS—Multiple sequence alignment using various sources of external information10.1093/nar/gkt283 ↗
41. Subramanian, A.R., Kaufmann, M., and Morgenstern, B. (2008). DIALIGN-TX: Greedy and progressive approaches for segment-based multiple sequence alignment. Algorithms Mol. Biol., 3.10.1186/1748-7188-3-6 ↗
42. AnchorWave: Sensitive alignment of genomes with high sequence diversity, extensive structural polymorphism, and whole-genome duplication10.1073/pnas.2113075119 ↗
43. New strategies to improve minimap2 alignment accuracy10.1093/bioinformatics/btab705 ↗
44. Minimap2: Pairwise alignment for nucleotide sequences10.1093/bioinformatics/bty191 ↗
45. Dewey, C.N. (2008). Aligning multiple whole genomes with Mercator and MAVID. Comp. Genom., 221–235.10.1007/978-1-59745-514-5_14 ↗
46. Mugsy: Fast multiple alignment of closely related whole genomes10.1093/bioinformatics/btq665 ↗
47. Scalable pairwise whole-genome homology mapping of long genomes with BubbZ10.1016/j.isci.2020.101224 ↗
48. BubbleGun: Enumerating bubbles and superbubbles in genome graphs10.1093/bioinformatics/btac448 ↗
49. Progressive Cactus is a multiple-genome aligner for the thousand-genome era10.1038/s41586-020-2871-y ↗
50. Rautiainen, M., and Marschall, T. (2020). GraphAligner: Rapid and versatile sequence-to-graph alignment. Genome Biol., 21.10.1186/s13059-020-02157-2 ↗
51. SOAP: Short oligonucleotide alignment program10.1093/bioinformatics/btn025 ↗
52. Stampy: A statistical algorithm for sensitive and fast mapping of Illumina sequence reads10.1101/gr.111120.110 ↗
53. GMAP: A genomic mapping and alignment program for mRNA and EST sequences10.1093/bioinformatics/bti310 ↗
54. Cui, Y., Liao, X., Peng, S., Lu, Y., Yang, C., Wang, B., and Wu, C. (2015, January 12–16). Large-scale neo-heterogeneous programming and optimization of SNP detection on Tianhe-2. Proceedings of the High Performance Computing: 30th International Conference, ISC High Performance 2015, Frankfurt, Germany. Proceedings 30.10.1007/978-3-319-20119-1_6 ↗
55. Whole-exome sequencing reveals a long-term decline in effective population size of red spruce (Picea rubens)10.1111/eva.12985 ↗
56. Kuznetsov, A., and Bollin, C.J. (2021). NCBI genome workbench: Desktop software for comparative genomics, visualization, and GenBank data submission. Mult. Seq. Alignment Methods Protoc., 261–295.10.1007/978-1-0716-1036-7_16 ↗
57. Saada, B., and Zhang, J. (2015, January 21–23). DNA sequences compression algorithm based on extended-ASCII representation. Proceedings of the World Congress on Engineering and Computer Science, San Francisco, CA, USA.
58. Efficient DNA sequence compression with neural networks10.1093/gigascience/giaa119 ↗
59. A distributed whole genome sequencing benchmark study10.3389/fgene.2020.612515 ↗
60. Marco-Sola, S., Eizenga, J.M., Guarracino, A., Paten, B., Garrison, E., and Moreto, M. (2023). Optimal gap-affine alignment in O(s) space. Bioinformatics, 39.10.1093/bioinformatics/btad074 ↗
61. Alser, M., Rotman, J., Deshpande, D., Taraszka, K., Shi, H., Baykal, P.I., Yang, H.T., Xue, V., Knyazev, S., and Singer, B.D. (2021). Technology dictates algorithms: Recent developments in read alignment. Genome Biol., 22.10.1186/s13059-021-02443-7 ↗
62. The complete sequence of a human Y chromosome10.1038/s41586-023-06457-y ↗
63. Zhou, Y., Zheng, J., Wu, Y., Zhang, W., and Jin, J. (2020). A completeness-independent method for pre-selection of closely related genomes for species delineation in prokaryotes. BMC Genom., 21.10.1186/s12864-020-6597-x ↗
64. Multiplex primer prediction software for divergent targets10.1093/nar/gkp659 ↗
65. Anisimova, M. (2012). Evolutionary Genomics: Statistical and Computational Methods, Volume 1, Humana Press.10.1007/978-1-61779-582-4 ↗
66. Löytynoja, A. (2012). Volutionary Genomics: Statistical and Computational Methods, Volume 1, Springer.
67. Strategies and tools for whole-genome alignments10.1101/gr.762503 ↗
68. Govek, K.W., Yamajala, V.S., and Camara, P.G. (2019). Clustering-independent analysis of genomic data using spectral simplicial theory. PLoS Comput. Biol., 15.10.1371/journal.pcbi.1007509 ↗
69. A multiple alignment workflow shows the effect of repeat masking and parameter tuning on alignment in plants10.1002/tpg2.20204 ↗
70. Multiple genome alignment in the telomere-to-telomere assembly era10.1186/s13059-022-02735-6 ↗
71. Huang, C., Li, R., and Li, A. (2023). Parallel Implementation of Key Algorithms for Intelligent Processing of Graphic Signal Data of Consumer Digital Equipment. Mob. Netw. Appl.10.1007/s11036-023-02208-5 ↗
72. Nolle, T., Seeliger, A., Thoma, N., and Mühlhäuser, M. (2020, January 8–12). DeepAlign: Alignment-based process anomaly correction using recurrent neural networks. Proceedings of the International Conference on Advanced Information Systems Engineering, Grenoble, France.10.1007/978-3-030-49435-3_20 ↗
73. Peltzer, A., Jäger, G., Herbig, A., Seitz, A., Kniep, C., Krause, J., and Nieselt, K. (2016). EAGER: Efficient ancient genome reconstruction. Genome Biol., 17.10.1186/s13059-016-0918-z ↗
74. New whole-genome alignment tools are needed for tapping into plant diversity10.1016/j.tplants.2023.08.013 ↗
75. Alignathon: A competitive assessment of whole-genome alignment methods10.1101/gr.174920.114 ↗
76. Computational solutions to large-scale data management and analysis10.1038/nrg2857 ↗
77. DBG2OLC: Efficient Assembly of Large Genomes Using Long Erroneous Reads of the Third Generation Sequencing Technologies10.1038/srep31900 ↗
78. Kshemkalyani, A.D., and Singhal, M. (2011). Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press.
79. Volozonoka, L., Miskova, A., and Gailite, L. (2022). Whole genome amplification in preimplantation genetic testing in the era of massively parallel sequencing. Int. J. Mol. Sci., 23.10.3390/ijms23094819 ↗
80. Genome-wide association studies10.1038/s43586-021-00056-9 ↗
81. Girisha, M.N., Badiger, V.P., and Pattar, S. (2022). A comprehensive review of global alignment of multiple biological networks: Background, applications and open issues. Netw. Model. Anal. Health Inform. Bioinform., 11.10.1007/s13721-022-00353-7 ↗
82. Efficient merging of genome profile alignments10.1093/bioinformatics/btz377 ↗
83. Whole-genome alignment and comparative annotation10.1146/annurev-animal-020518-115005 ↗
84. Macaulay, I.C., and Voet, T. (2014). Single cell genomics: Advances and future perspectives. PLoS Genet., 10.10.1371/journal.pgen.1004126 ↗
85. Shi, L., and Wang, Z. (2019). Computational strategies for scalable genomics analysis. Genes, 10.10.3390/genes10121017 ↗
86. Wheat germ agglutinin as a potential therapeutic agent for leukemia10.3389/fonc.2019.00100 ↗
87. Taylor, J., Yudkowsky, E., LaVictoire, P., and Critch, A. (2016). Alignment for advanced machine learning systems. Ethics Artif. Intell., 342–382.10.1093/oso/9780190905033.003.0013 ↗