Enhancing the Clustering and Sorting Procedures in the MAGUS Method for Multiple Sequence Alignment

Multiple sequence alignment (MSA) is a foundational computational technique in bioinformatics, enabling the comparative analysis of sequences to uncover evolutionary, structural, and functional relationships among DNA, RNA, or protein sequences. By aligning homologous sequences, MSA identifies conserved regions, variations, and patterns critical for understanding biological processes and guiding experimental studies. It serves as a cornerstone for applications such as phylogenetic tree construction, protein structure prediction, and gene annotation. Modern MSA methods leverage sophisticated algorithms, including dynamic programming, heuristic approaches, and machine learning, to balance accuracy and computational efficiency for large datasets. This work adopts MAGUS (Multiple Sequence Alignment using Graph Clustering) (Smirnov et al. ۲۰۲۱) and improves the clustering step along with the sorting steps. For improving the clustering step, we use the repeated random walk algorithm (RRW) (Macropol et al. ۲۰۰۹) and for sorting step we simply replace A* with quicksort. The result shows that these modifications can efficiently improve the performance of the algorithm.

کلیدواژه ها:

multiple sequence alignment ، algorithms ، phylogenetic trees ، dynamic programming ، protein sequences