# Whole-Genome Alignment: Methods, Challenges, and Future Directions
## 2 Classification of Whole-Genome Alignment Algorithms
### Supflix Tree-Based Alignment Methods
#### 2.1.1 MUMmer Technique  
MUMmer uses a suffix tree-based algorithm called a \"Maximal Unique Match\" (MUM) finding algorithm, which is an alignment algorithm based on suffix tree representation,  
Figure 1: Suffix Tree for the Sequence TATTATTAA with 9 Suffixes and $ marking the termination of each suffix.  
being a suite of bioinformatics tools designed for whole-genome alignment and comparison tasks. The main idea of this algorithm is to find all distinct matches for two given genomes [17]. To better align the two given genomes, it is assumed that they are closely homologous. MUMmer is widely used in bioinformatics for tasks such as genome alignment, genome assembly validation, sequence annotation, and comparative genomics studies. Its suffix tree-based MUM finding algorithm provides an efficient and accurate method for identifying conserved regions and similarities between large genomic sequences [18]. This accuracy is crucial in NGS alignment tasks where even small errors can lead to misinterpretation of genetic variations or structural variations. While newer alignment methods continue to emerge, suffix tree-based methods remain a key method in NGS alignment due to their accuracy, efficiency, and ability to handle large-scale genomic data effectively. Researchers and bioinformaticians often choose these methods based on their specific alignment requirements, data characteristics, and the need for accurate and reliable alignment results.  
MUMmer constructs a suffix tree for each input genome sequence. Its algorithm is based on the following four main steps:  
1. Perform a maximal unique match (MUM) decomposition of the two genomes. The algorithm identifies all MUMs between pairs of genomes, which are subsequences that occurs exactly once in genome A and once in genome B. This decomposition identifies all maximal unique matches between the two genomes. To detect these MUMs, the two genomes are represented by a suffix tree. The common substrings detected on the tree represent all the MUMs between the two genomes (Figure 2). MUMs represent regions of high similarity or conserved regions between genomes;
2. Apply filtering techniques to remove spurious matches and improve the accuracy of the alignment results. Organize the MUMs and identify the most extended sequence of matches found in both genomes, maintaining their original order;
3. Fill in the spaces within the alignment by detecting significant insertions, repetitions, altered sections, and single nucleotide variations (SNVs);
4. Perform a Smith-Waterman alignment for the regions between the MUMs and construct the final alignment;
5. Output alignments, allowing visualization and analysis to understand the evolutionary relationships and structural similarities between the input genomes.  
Figure 2: MUMs detected between Seq1 and Seq2. The maximal exact match is ATCG. $ is marking the termination of each suffix. MUMmer 2.1  
MUMmer 1.0 was first used to detect large-scale inversions in bacterial genomes. The bacterial genomes' sizes did not exceed a few Mbp. This means that MUMmer 1.0 would require powerful computational resources to align genomes comprising billions of nucleotides. In addition, when the human genome was sequenced, it was necessary to implement a new algorithm able to align entire human chromosomes rapidly and accurately. For that reason, the authors proposed a new method that required less memory and ran the four steps faster [13]. In addition, a new parameter \(k\) was introduced. This parameter represents the maximum gap length allowed between MUMs. If the gap is lower than \(k\), the two adjacent MUMs are regrouped in the same cluster (Figure 3). Unique MUMs occur exactly once in both genomes. However, in certain cases, the exact match may be duplicated within the subject genome. To overcome this problem, the new MUMmer 3.0 uses all maximal matches including non-unique ones to align the two genomes [19]. In addition, the execution time of MUMmer 3.0 and the memory usage have been improved.