Clumppling: cluster matching and permutation program with integer linear programming.

Area of Science:

• Population genetics
• Computational biology
• Bioinformatics

Background:

• Mixed-membership unsupervised clustering is vital in population genetics.
• Replicate analyses can yield different clustering solutions, hindering interpretation.
• Existing alignment algorithms face challenges in optimality and computation time.

Purpose of the Study:

• To introduce Clumppling, a novel method for aligning replicate clustering solutions.
• To address limitations in optimality and computational efficiency of current alignment techniques.
• To enable alignment across replicates with multiple arbitrary values for the number of clusters (K).

Main Methods:

• Utilizes integer linear programming to solve the cluster alignment problem.
• Embeds cluster alignment within standard combinatorial optimization frameworks.
• Applies the method to example population genetics datasets.

Main Results:

• Clumppling achieves optimal alignments with preferred objective function values.
• Outperforms existing methods like Pong in solution quality.
• Demonstrates significantly reduced computation time compared to Clumpak.
• First method capable of aligning replicates with multiple arbitrary K values.

Conclusions:

• Clumppling provides an efficient and optimal solution for aligning mixed-membership clustering replicates.
• Enhances the interpretability and combined analysis of population genetics data.
• Offers a flexible tool for researchers dealing with variable cluster numbers.