A Discretized Overlap Resolution Algorithm (DORA) for resolving spatial overlaps in individual-based models of microbes. - Ihab Hashem; Jian Wang; Jan F M Van Impe (PLoS Computational Biology)
Individual-based modeling (IbM) is an instrumental tool for simulating spatial microbial growth, with applications in both microbial ecology and biochemical engineering. Unlike Cellular Automata (CA), which use a fixed grid of cells with predefined rules for interactions, IbMs model the individual behaviors of cells, allowing complex population dynamics to emerge. IbMs require more detailed modeling of individual interactions, which introduces significant computational challenges, particularly in resolving spatial overlaps between cells. Traditionally, this is managed using arrays or kd-trees, which require numerous pairwise comparisons and become inefficient as population size increases. To address this bottleneck, we introduce the Discretized Overlap Resolution Algorithm (DORA), which employs a grid-based framework to efficiently manage overlaps. By discretizing the simulation space further and assigning circular cells to specific grid units, DORA transforms the computationally intensive pairwise comparison process into a more efficient grid-based operation. This approach significantly reduces the computational load, particularly in simulations with large cell populations. Our evaluation of DORA, through simulations of microbial colonies and biofilms under varied nutrient conditions, demonstrates its superior computational efficiency and ability to accurately capture microbial growth dynamics compared to conventional methods. DORA's grid-based strategy enables the modeling of densely populated microbial communities within practical computational timeframes, thereby expanding the scope and applicability of individual-based modeling.