New Workflow: Multiple Genome Alignment Pipeline Using Mash, FastGA/KegAlign, and Multiz

## Summary

A Galaxy workflow for constructing a multiple sequence alignment (MSA) from a collection of related genomes (e.g. different strains of malaria). The pipeline uses pairwise distance estimation to guide a tree-directed alignment strategy, selecting alignment tools based on inter-genome similarity, and finally merges pairwise alignments into a genome-wide MSA.

> [!NOTE]
> This is related to https://github.com/galaxyproject/tools-iuc/issues/7364

---

## Background / Motivation

Comparative genomics across related species or strains requires scalable, reference-free multiple genome alignment. Existing Galaxy tooling does not provide an end-to-end workflow that:

- Efficiently estimates pairwise genome similarity at scale
- Adapts the alignment strategy based on divergence between pairs
- Produces a phylogeny-guided multiple sequence alignment from the resulting pairwise alignments

This workflow addresses that gap by combining sketch-based distance estimation, two complementary pairwise aligners suited to different divergence regimes, and a tree-guided MSA construction step.

---

## Proposed Workflow: Step-by-Step

### Step 1 — Pairwise Distance Estimation (Mash)

**Input:** A Galaxy collection of genome FASTA files (one per species/strain)

**Tool:** [Mash](https://github.com/marbl/Mash) (current working choice; subject to change)

- Compute MinHash sketches for each genome
- Estimate all-vs-all pairwise Mash distances using Mash triangle
- **Output:** A pairwise distance matrix (PHYLIP format)

---

### Step 2 — Tree Construction

**Input:** Pairwise distance matrix from Step 1

**Tool:** A distance-based tree-building tool (TBD, possibly RapidNJ)

- Construct a cladogram from the distance matrix
- The tree topology will guide the order and hierarchy of pairwise alignments in the MSA step
- **Output:** A cladogram (Newick format, most likely)

---

### Step 3 — Similarity-Directed Pairwise Alignment (FastGA / KegAlign)

**Input:** Genome collection + pairwise distance matrix from Step 1

**Logic:** For each genome pair, apply a similarity threshold to select the appropriate aligner:

| Condition | Aligner |
|---|---|
| Similarity ≥ threshold (closely related) | [FastGA](https://github.com/thegenemyers/FASTGA) |
| Similarity < threshold (more diverged) | [KegAlign](https://github.com/galaxyproject/KegAlign) |

The threshold is user-configurable and will be determined empirically. A starting value of ~70% similarity (Mash distance ~0.30) is anticipated, pending validation against real datasets.

- FastGA is optimized for highly similar genomes (e.g. strains of the same species)
- KegAlign scales to more diverged comparisons using a seeding strategy suited for larger evolutionary distances
- **Output:** A collection of pairwise alignment files (chain format or equivalent) for all genome pairs

---

### Step 4 — Multiple Sequence Alignment Construction (Multiz)

**Input:** Pairwise alignments from Step 3 + Cladogram from Step 2

**Tool:** [Multiz](http://www.bx.psu.edu/miller_lab/) (current working choice; subject to change)

- Uses the cladogram to determine the progressive alignment order
- Merges pairwise alignments into a single genome-wide multiple alignment
- **Output:** A multiple sequence alignment (MAF format)

---

## Workflow Summary Diagram

```
[Genome Collection]
|
v
[Mash]
Pairwise Distance Matrix
|
+-----------------------+
| |
v v
[Tree Builder] [Pairwise Aligner Selection]
Cladogram (Newick) For each genome pair:
| - Closely related → FastGA
| - More diverged → KegAlign
| |
| v
| Pairwise Alignments
| (chain files)
| |
+-----------+-----------+
|
v
[Multiz]
Multiple Sequence Alignment (MAF)
```

---

## Tool Wrappers Needed

| Tool | Status in Galaxy / IUC |
|---|---|
| Mash | Wrapper exists in tools-iuc (triangle-specific wrapper may be needed) |
| Distance-based tree builder | To be determined |
| FastGA | Wrapper exists in tools-iuc (contributed by me) |
| KegAlign | Wrapper exists in tools-iuc |
| Multiz | **Wrapper needs to be created** |

The primary blocker for this workflow is a Galaxy wrapper for Multiz. I will create this, alongside other wrappers and workflows needed.

---

## References

- Ondov et al. (2016) *Mash: fast genome and metagenome distance estimation using MinHash.* Genome Biology. https://doi.org/10.1186/s13059-016-0997-x
- Myers, G. *FASTGA* — https://github.com/thegenemyers/FASTGA
- KegAlign — https://github.com/galaxyproject/KegAlign
- Blanchette et al. (2004) *Aligning multiple genomic sequences with the threaded blockset aligner.* Genome Research. https://doi.org/10.1101/gr.1933104

---

## Additional Notes

- The similarity threshold separating FastGA and KegAlign is user-configurable; a value near 70% similarity (Mash distance ~0.30) is the anticipated default, to be refined through experimental validation
- Multiz is the current working choice for MSA construction but all tool selections in this workflow remain subject to change
- Target use case: strain-level comparative genomics (e.g. *Plasmodium*, bacterial populations), but the workflow is general-purpose
- All tools cited here either already have wrappers in tools-iuc or are being actively developed; the only identified gap is Multiz