# Whole-Genome Alignment: Methods, Challenges, and Future Directions
## 2 Classification of Whole-Genome Alignment Algorithms
### Supflix Tree-Based Alignment Methods
#### 2.1.2 Other Sequence Comparison Approaches Based on the Suffix Tree Method  
Suffix tree approaches provide fast computational time to detect exact matches between sequences. Different algorithms rely on the construction of suffix trees between the two sequences to detect similar regions (words). The Lwords algorithm is a sequence comparison alignment-free approach based on the construction of a generalized suffix tree of all sequences. The Lwords algorithm aims to represent repeated substrings in a string using a dictionary of unique codes. This algorithm is primarily used for data compression, enabling efficient storage and transmission of repetitive data [21]. The algorithm scans the input string and builds a dictionary of unique substrings, assigning each substring a unique code. Following the construction of the suffix tree, the frequency of all possible words with length L, provided as a parameter, is calculated. Then, based on the L-words \begin{table}
\begin{tabular}{c c c c} \hline \hline
**MUMmer Version** & **Complexity** & **Main Steps** & **Main Improvement** \\ \hline \multirow{2}{*}{MUMmer 1} & \(O(n^{2})\) & Construct suffix trees, identify MEMs, extend MEMs, cluster MUMs & Initial implementation of suffix tree-based matching \\ \hline \multirow{2}{*}{MUMmer 2} & \(O(n^{2})\) & Construct suffix trees, identify MEMs, extend MEMs, cluster MUMs & Improved optimization and refinement of suffix tree algorithms \\ \hline \multirow{2}{*}{MUMmer 3.1} & \(O(n\lg n)\) & Construct enhanced suffix arrays, efficient MEM identification, extend MEMs, cluster MUMs & Introduction of enhanced suffix arrays for improved efficiency \\ \hline \multirow{2}{*}{MUMmer 4} & \(O(n\lg n)\) & Construct suffix trees, efficient MEM identification, extend MEMs, cluster MUMs & Optimization of suffix tree usage for enhanced algorithm performance \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Overview of the differences between various versions of MUMmer software. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Approach** & **Method** & **Type** \\ \hline \multirow{5}{*}{Suffix tree-based methods} & MUMmer & Local alignment \\ \cline{2-3}  & MUMmer 4.0 & Global multiple genome alignment \\ \cline{2-3}  & Suffix tree \& Lword & Global multiple genome alignment \\ \cline{2-3}  & Multiple Sequence Alignment (MSA) & Local alignment \\ \hline \multirow{5}{*}{Anchor-based methods} & LAGAN/Multi-LAGAN & Global multiple genome alignment \\ \cline{2-3}  & ProgressiveMauve & Hierarchical WGA mapping \\ \cline{2-3}  & BlastZ & Local alignment \\ \cline{2-3}  & STELLAR & Local alignment \\ \cline{2-3}  & LASTZ & Local alignment \\ \cline{2-3}  & DIALIGN & Global multiple genome alignment \\ \hline \multirow{5}{*}{Graph-based methods} & AnchorWave & Global alignment \\ \cline{2-3}  & MERCATOR & Homology mapping \\ \cline{2-3}  & Mugsy & Hierarchical WGA mapping \\ \cline{2-3}  & BubbZ & Homology mapping \\ \cline{2-3}  & SibeliaZ & Hierarchical WGA mapping \\ \cline{2-3}  & Progressive Cactus & Global multiple genome alignment \\ \cline{2-3}  & GraphAligner & Global multiple genome alignment \\ \hline \multirow{5}{*}{Hash-based alignment algorithms} & SOAP & Hash-based mapping \\ \cline{2-3}  & Stampy & Hybrid local alignment \\ \cline{1-1} \cline{2-3}  & BLAST & Local similarity search \\ \cline{1-1} \cline{2-3}  & GMAP & Spliced alignment mapping \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Whole-genome alignment (WGA) algorithm classification based on approaches to alignment. frequency profile for each sequence, a pairwise Euclidean distance is computed, producing a symmetrical genetic distance matrix between the sequences. The efficiency of the Lwords algorithm depends on the frequency and length of repeated substrings in the input string. It performs well when there are significant repetitions in the input data; however, it can be ineffective for data with minimal redundancy [22]. The execution time of the Lwords algorithm is satisfactory when the algorithm is applied to complete intra/inter mitochondrial species' genomes.