Constraint-Based Sub-Graph Partitioning for Multi-Cellular Biological Networks

Synthetic consortia represent an emerging research area in synthetic biology, promising to solve various industrial challenges through the metabolic diversity, division of labor, and spatial organization inherent in microbial consortia. As synthetic biology advances into multi-cellular systems, new design strategies are essential for engineering distributed functions across networks of cells. However, existing strategies either lack scalability or require extensive reformulation, limiting their usage to various applications. In this work, we propose an application-agnostic approach to partitioning networks of interacting biological components using graph-based algorithms. We develop a three-stage algorithm, named "Oriole", that verifies and optimizes the subgroup distribution of all entities within a network, considering biological constraints and objectives for engineering these systems. We validate our algorithm on three types of networks, including 30 small-graph benchmarks, 537 regular electronic circuit designs, and 56 large circuit benchmarks. One large circuit benchmark was recently implemented experimentally. Compared with the other sub-graph partitioning solutions, the results generated by our new algorithm reduced design time from days to hours and decreased the total number of cells required for the multi-cellular system by 3%. This case study demonstrates that our algorithm provides a more efficient approach to designing multi-cellular systems.