Designing gene manipulation schedules for high throughput parallel construction of objective strains

Recent advances in biofoundries have enabled the construction of a large quantity of strains in parallel, accelerating the design-build-test-learn (DBTL) cycles for strain development. However, the construction of a large number of strains by iterative gene manipulation is still time-consuming and costly, posing a challenge for the development of commercial strains. Common gene manipulations among different objective strains open up the possibility of reducing cost and time for strain construction in biofoundries by optimizing genetic manipulation schedules. A method is introduced consisting of two complementary algorithms for designing optimal parent-children manipulation schedules for strain construction: greedy search of common ancestor strains (GSCAS) and minimizing total manipulations (MTM). By reusing common ancestor strains, the number of strains to be constructed can be effectively reduced, resulting in a tree-like structure of descendants instead of linear lineages for each strain. The GSCAS algorithm can quickly find common ancestor strains and clusters them together based on their genetic makeup, and the MTM algorithm subsequently minimize the genetic manipulations required, resulting in a further reduction in the total number of genetic manipulations. The effectiveness of our method is demonstrated through a case study of 94 target strains, where GSCAS reduces an average of 36% of the total gene manipulations, and MTM reduces an additional 10%. The performance of both algorithms is robust among case studies with different average occurrences of gene manipulations across objective strains. Our method potentially improves cost efficiency and accelerate the development of commercial strains significantly. The implementation of the methods can be freely accessed via https://gscas-mtm.biodesign.ac.cn/.