MAGUS: Multiple sequence Alignment using Graph clUStering.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Estimating large multiple sequence alignments (MSAs) is a fundamental challenge in bioinformatics.
• Divide-and-conquer strategies enhance scalability and accuracy in existing MSA methods like SATé and PASTA.
• These methods involve partitioning datasets, aligning subsets, and merging results.

Purpose of the Study:

• Introduce MAGUS (Multiple sequence Alignment using Graph clUStering), a novel technique for large-scale MSA estimation.
• Present the Graph Clustering Merger, a new algorithm for merging disjoint alignments.
• Evaluate MAGUS's performance against established methods on diverse datasets.

Main Methods:

• MAGUS employs a divide-and-conquer strategy, similar to PASTA, using an initial tree and dataset decomposition.
• Subset alignments are computed using a base MSA method, such as MAFFT.
• The novel Graph Clustering Merger is utilized to combine these subset alignments.

Main Results:

• MAGUS demonstrates improved accuracy compared to PASTA on large datasets.
• MAGUS achieves faster computation times than PASTA for large-scale alignments.
• Performance is comparable to PASTA on smaller datasets.

Conclusions:

• MAGUS offers a scalable and accurate solution for large multiple sequence alignment problems.
• The Graph Clustering Merger is an effective method for combining partitioned alignments.
• MAGUS represents a significant advancement in computational bioinformatics tools.