Minimizing stochastic complexity using local search and GLA with applications to classification of bacteria

Area of Science:

• Microbiology
• Computational Biology
• Data Science

Background:

• Iterative clustering methods are crucial for analyzing complex biological datasets.
• Classifying bacterial strains, such as Enterobacteriaceae, aids in understanding microbial evolution and disease transmission.

Purpose of the Study:

• To compare the performance of two iterative clustering algorithms: generalized Lloyd algorithm (GLA) and local search (LS).
• To evaluate their effectiveness in classifying an extensive dataset of Enterobacteriaceae strains based on minimizing stochastic complexity.

Main Methods:

• The study applied two iterative clustering methods to a large dataset of Enterobacteriaceae strains.
• Both methods aimed to determine classification by minimizing stochastic complexity.
• The generalized Lloyd algorithm (GLA) used repeated application for minimization.
• Local search (LS) employed global changes and local fine-tuning for optimization.

Main Results:

• Local search (LS) consistently found classifications with lower stochastic complexity compared to GLA when the number of classes was fixed.
• The LS method demonstrated significantly smaller variance in solutions, attributed to its systematic search approach.
• Both algorithms yielded broadly similar classifications, yet differed in merging specific microbiologically relevant natural classes.

Conclusions:

• Local search (LS) is a more effective iterative clustering method than GLA for this dataset, offering improved optimization and stability.
• The choice of clustering algorithm can influence the interpretation of bacterial relationships due to differing class merging strategies.
• Further research could explore the microbiological implications of the distinct classifications produced by GLA and LS.