Oriole - Sub-graph Partitioning Algorithm

Table of Contents

• Overview
• Install
• Usage
  • Small Graph Benchmarks
  • Regular Electronic Circuit Benchmarks
  • Big circuit Benchmarks
• Maintainers
• Contributing
  • Contributors
• License

Overview

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 developed a three-stage algorithm, named Oriole, that verifies and optimizes the subgroup distribution of all entities within a network, considering constraints, objectives, and other biological considerations essential for engineering these systems. We validated our algorithm on three types of networks, including 30 small-graph benchmarks, 537 regular electronic circuit designs, and 43 large circuit benchmarks. One large circuit benchmark was recently implemented in the wet lab. Compared with the published sub-graph partitioning solution, 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.

Install

Download the repository from GitHub, create a venv environment, and install the necessary packages. Here we use python3.8 as the python interpreter.

$ git clone https://github.com/CIDARLAB/Oriole.git
$ cd algorithm
$ python3 -m venv venv/
$ venv/bin/pip3 install -r requirements.txt

After you install all the packages, you are able to run the algorithm.

Usage

Generate edge list from a ".JSON" file

The desired input graph format for Oriole algorithm is ".edgelist". Users can use this command to create the graphs of their own benchmarks. Since many the schematics of regular electronic circuits can be represented in JSON format, we provide an edge list generator for users to get the desired input format of Oriole algorithm.

$ venv/bin/python3 generateEdgeList.py -settings ./settings.txt -samples md5_opt_nor2

Create constraint set for your target benchmark

In the "settings.txt" file, users can create a new row and modify constraints for their benchmark.

Verification stage for a 2-bit MD5 benchmark

You can run the verification stage of Oriole algorithm to verify the 2-bit MD5 benchmarks with the following command. The algorithm outputs a verified subgroup solution after passing this stage. Otherwise, it reports error. Don't forget to comment the command "Merge()" in merging.py and command "EdgeColoring()" in EdgeColoring.py.

$ venv/bin/python3 algorithm/verification.py -settings ./settings.txt -samples md5_opt_nor2

Merging stage for a 2-bit MD5 benchmark

You can run the merging stage of Oriole algorithm to find more optimal subgroup solutions for the 2-bit MD5 benchmarks with the following command. Don't forget to comment the command "Verification()" in verification.py and command "EdgeColoring()" in EdgeColoring.py.

$ venv/bin/python3 algorithm/merging.py -settings ./settings.txt -samples md5_opt_nor2

Edge Coloring stage for a 2-bit MD5 benchmark

You can run the edge coloring stage of Oriole algorithm to find color assignment and the corresponding subgroup solution for the 2-bit MD5 benchmarks with the following command. Don't forget to comment the command "Verification()" in verification.py and command "Merge()" in merging.py.

$ venv/bin/python3 algorithm/EdgeColoring.py -settings ./settings.txt -samples md5_opt_nor2

Maintainers

@zyrrron.

Contributing

Feel free to dive in! Open an issue or submit PRs.

Contributors

This project exists thanks to all the people who contribute.

License

BSD 2-Clause License

Copyright (c) 2024, CIDAR LAB All rights reserved.

See LICENSE for more information.