MYCOLab Ai Logo - gold and army green

A Discretized Overlap Resolution Algorithm (DORA) for resolving spatial overlaps in individual-based models of microbes

Summary

Scientists developed a new computer algorithm called DORA that helps simulate how microbes grow in crowded environments. The algorithm tracks where individual microbes are located and prevents them from overlapping by using a grid system instead of comparing every microbe to every other microbe. This makes simulations much faster, especially when there are tens of thousands of microbes present, allowing researchers to study biofilm formation and microbial colonies more efficiently.

Background

Individual-based modeling (IbM) is used to simulate spatial microbial growth in ecology and biochemical engineering. A major computational challenge in IbMs is resolving spatial overlaps between cells, traditionally managed using arrays or kd-trees, which require numerous pairwise comparisons that become inefficient with large populations.

Objective

To introduce and validate the Discretized Overlap Resolution Algorithm (DORA), a grid-based framework that efficiently resolves spatial overlaps between cells in individual-based models of microbial growth with reduced computational complexity compared to conventional methods.

Results

DORA demonstrated superior computational efficiency compared to kd-tree methods, particularly in dense cell populations exceeding 10^4 cells, while maintaining overlap ratios below 1%. The algorithm successfully captured complex spatial patterns including uniform growth, fractal branching under nutrient scarcity, and biofilm mushroom-like structures across all tested conditions.

Conclusion

DORA significantly reduces computational complexity from O(N log N) to O(N) for overlap resolution, enabling simulation of densely populated microbial communities within practical timeframes. The algorithm successfully bridges individual-based models and PDE approximations while maintaining high spatial accuracy in modeling microbial growth dynamics.
  • Published in:PLoS Computational Biology,
  • Study Type:Algorithm Development and Validation Study,
  • Source: PMID: 40258091, DOI: 10.1371/journal.pcbi.1012974
Scroll to Top