PDMClust

PDMClust clusters aligned sequences from distances in a phylogenetic tree. It calculates raw patristic distances with PhyloDM, converts each distance d to the edge weight 1 - d, filters edges by a user-supplied cutoff, and runs the Markov Cluster Algorithm (MCL).

--tax-level splits clusters by taxonomy, and --count ranks members by sample prevalence. Extraction writes the first member of each cluster to FASTA.

Method

For each cutoff, PDMClust:

1. Loads the Newick tree and calculates one raw PhyloDM distance matrix with norm=False.
2. Converts each off-diagonal distance d to 1 - d and keeps one edge per pair when the weight is greater than the cutoff.
3. Runs MCL with inflation 1.5.
4. Adds alignment sequences without retained edges as singleton clusters.
5. Splits taxonomically mixed clusters when --tax-level is set.
6. Orders cluster members by sample prevalence when --count is set.

Cutoffs must fall between 0 and 1; they are not sequence-identity percentages. Their meaning depends on the branch-length scale of the input tree. PDMClust keeps the raw distance scale and does not normalize trees from different analyses.

The full distance matrix requires quadratic memory in the number of tips. PhyloDM reports about 14 GB for 30,000 taxa; the edge table and MCL require more memory when many pairs pass the cutoff.

Install with Pixi

Pixi installs Python, PhyloDM, and MCL from the tracked lock file. Pixi installs the test and format tools when a development task runs.

git clone https://github.com/NeLLi-team/pdmclust.git
cd pdmclust
pixi install --frozen

The Pixi workspace targets Linux x86-64. The lock file pins the package builds used by the local and Apptainer workflows.

Run the bundled example

pixi run run-test

The command auto-detects the tree, alignment, and taxonomy files in test/ and writes test_results/. The bundled 178-sequence data set produces:

Cutoff	Clusters	Singletons	Mean size	Largest cluster
0.99	178	178	1.00	1
0.95	173	168	1.03	2
0.90	170	162	1.05	2
0.80	160	146	1.11	4
0.70	152	133	1.17	4

Command line

pixi run python phylodm_clustering.py \
  --input-dir test \
  --output-dir test_results \
  --cutoffs 0.99,0.95,0.9,0.8,0.7

--help prints every option:

pixi run python phylodm_clustering.py --help

Hyphenated option names are canonical. Underscored forms such as --input_dir, --output_dir, --tax_level, --extract_tax_level, and --extract_only remain accepted.

Input discovery

--input-dir is required. PDMClust detects one file of each type in that directory:

Input	Recognized suffixes	Required
Newick tree	.tree, .nwk, .tre, .treefile, .contree	For clustering
FASTA alignment	.aln, .mafft, .mafft_t, .faa, .fa, .fasta	Yes
Taxonomy table	.tsv, .tax, .taxonomy	For taxonomy operations

Auto-detection stops when more than one candidate exists. Pass --tree, --seqfile, or --taxonomy to select a file. Tree tip labels must match the FASTA record IDs. PDMClust stops and reports examples from each unmatched set when they differ.

Taxonomy table

The taxonomy file is a tab-separated table without a header. Column one contains the sequence ID. Column two contains a pipe-delimited lineage from the broadest available rank to the narrowest:

seq1	Viruses|PhylumA|ClassA|OrderA|FamilyA|GenusA|SpeciesA
seq2	Viruses|PhylumA|ClassA|OrderA|FamilyA|GenusB|SpeciesB

PDMClust anchors ranks from the right side of the lineage:

Level	Rank
1	species
2	genus
3	family
4	order
5	class
6	phylum
7	domain

Duplicate sequence IDs trigger a warning. The last row for an ID wins. Taxonomy statistics ignore members without a value at the requested rank. A rank absent from all alignment sequences is reported as n/a.

Split mixed clusters

pixi run python phylodm_clustering.py \
  --input-dir test \
  --tax-level family

PDMClust keeps a cluster when its annotated members share one value at the selected rank. It splits a mixed cluster into rank-specific groups and turns its unannotated members into singletons.

Count table and representative priority

--count accepts a headered, tab-separated matrix. The first column contains sequence IDs; each other column contains numeric counts for one sample.

genome_id	sample1	sample2	sample3
seq1	10	5	0
seq2	8	0	0

PDMClust counts the samples with a positive value for each sequence and places members with higher prevalence first. Missing IDs receive prevalence zero. The first member becomes the representative during extraction.

Extract representatives

Run one cutoff and write the first member of each cluster to FASTA:

pixi run python phylodm_clustering.py \
  --input-dir test \
  --extract 0.7

Reuse an existing cluster file without recalculating the tree distances:

pixi run python phylodm_clustering.py \
  --input-dir test \
  --output-dir test_results \
  --extract 0.7 \
  --extract-only

The example writes pimascovirales_faa--GVOG7-fasttree-perc3_pdm70.mafft_t under the output directory.

--extract-only writes the representative FASTA and leaves the existing run report unchanged.

--extract by itself runs one cutoff. When --cutoffs is also present, PDMClust keeps those results and adds the extraction cutoff when needed.

Select a cutoff from taxonomy

pixi run python phylodm_clustering.py \
  --input-dir test \
  --extract-tax-level family

PDMClust tests 0.99, 0.95, each tenth from 0.9 through 0.1, and each hundredth from 0.09 through 0.01. It scans from strict to relaxed cutoffs and selects the last consistent value before consistency first fails, then extracts representatives from that cluster file. If every tested cutoff is consistent, it selects 0.01. The command fails when the taxonomy lacks the requested rank or the strictest tested cutoff is inconsistent. --cutoffs cannot override this fixed scan.

--tax-level cannot be combined with --extract-tax-level; splitting clusters before measuring consistency would make the selection circular.

Output

test_results/
├── README.md
├── combined_stats.tsv
├── clusters/
│   ├── threshold_0.70.txt
│   ├── threshold_0.80.txt
│   ├── threshold_0.90.txt
│   ├── threshold_0.95.txt
│   └── threshold_0.99.txt
└── phylodm_out/
    ├── threshold_0.70.3c
    ├── threshold_0.70.3c.mcl
    └── ...

Cluster files contain one tab-delimited cluster per line. The .3c files contain one headerless MCL ABC edge per sequence pair (source, target, weight without a header row). The .mcl files preserve raw MCL output. Empty graph and MCL files are valid when no pair passes a cutoff.

combined_stats.tsv reports cluster counts, singleton counts, size statistics, and taxonomy consistency from species through domain. The generated README.md records the inputs, method, statistics, selected taxonomy cutoff, and representative file for that run.

PDMClust accepts an empty directory or a directory produced by PDMClust. It refuses other non-empty directories so it cannot overwrite an unrelated README.md. PDMClust overwrites files for cutoffs in the current command. Use an empty output directory when changing cutoff sets so older files do not remain beside the current results.

Apptainer

Build the image from the tracked Pixi lock file:

apptainer build --fakeroot phylodm-clustering.sif phylodm-clustering.def

Run the bundled data through the image:

mkdir -p test_container_results
apptainer run \
  --bind "$(pwd)/test:/input:ro" \
  --bind "$(pwd)/test_container_results:/output" \
  phylodm-clustering.sif \
  --input-dir /input \
  --output-dir /output

Sites without unprivileged fakeroot support can use a remote builder or ask an administrator to build the SIF file.

Development

pixi run lint
pixi run test
pixi run format

pixi run test includes an end-to-end run on the bundled tree, alignment, and taxonomy data. The test checks that all 178 IDs appear exactly once at five cutoffs and verifies the raw MCL artifacts.

Citation

PDMClust uses:

• Aaron Müssig, PhyloDM.
• Stijn van Dongen. “Graph Clustering Via a Discrete Uncoupling Process.” SIAM Journal on Matrix Analysis and Applications 30(1):121–141 (2008). doi:10.1137/040608635.

License

PDMClust is available under the MIT License.

Support

Open an issue at https://github.com/NeLLi-team/pdmclust/issues.