MAGUS

MAGUS estimates large multiple sequence alignments (MSAs) by dividing datasets into subsets, aligning subsets, and merging them via graph clustering to improve scalability and alignment accuracy for downstream phylogenetic and comparative analyses.

Key Features:

• Divide-and-Conquer Strategy: Divides sequence datasets into disjoint subsets and recombines subset results to scale MSA estimation to large datasets.
• Subset Alignment with MAFFT: Aligns each subset using MAFFT (Multiple Alignment using Fast Fourier Transform) to produce high-quality local alignments.
• Graph Clustering Merger: Merges disjoint subset alignments using the Graph Clustering Merger algorithm to produce a cohesive full-dataset alignment.
• Performance: Empirical studies report that MAGUS outperforms PASTA on large datasets with improved accuracy and faster processing times while producing comparable results to PASTA on smaller datasets.

Scientific Applications:

• Phylogenetic Analysis: Produces MSAs for constructing phylogenetic trees from sequences across diverse species or strains.
• Protein Structure Prediction: Provides aligned protein sequences for use in structural and functional prediction workflows.
• Comparative Genomics: Generates alignments for analyzing evolutionary relationships and genomic variation across organisms.

Methodology:

Constructs a starting tree (as in PASTA), decomposes the dataset into disjoint subsets, aligns each subset with MAFFT, and merges subset alignments using the Graph Clustering Merger.