همایش ملی بیوانفورماتیک ایران

صفحه اصلی / 4th international edition and 13th Iranian Conference on Bioinformatics

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

نویسندگان :

Masih Hajsaeedi¹ Mohsen Hooshmand²

1- Dept. of Computer Science and Information Technology, Institute for Advanced Studies in Basic Sciences (IASBS), Zanjan, Iran. 2- Dept. of Computer Science and Information Technology, Institute for Advanced Studies in Basic Sciences (IASBS), Zanjan, Iran.

کلمات کلیدی :

Multiple Sequence alignment،algorithms،phylogenetic trees،dynamic programming،protein sequences

چکیده :

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) and improves the clustering and sorting steps. For enhancing the clustering step, we use the repeated random walk algorithm (RRW); for the sorting step, we simply replace A* with quicksort. The result shows that these modifications can efficiently improve the performance of the algorithm.