RetSynth: Solving all optimal retrosynthesis solutions using dynamically constrained integer linear programming

Motivation Naive determination of all the optimal pathways to production of a target chemical on an arbitrarily defined chassis organism is computationally intractable. Methods like linear integer programming can provide a singular solution to this problem, but fail to provide all optimal pathways. Results Here we present RetSynth, an algorithm for determining all optimal biological retrosynthesis solutions, given a starting biological chassis and target chemical. By dynamically scaling constraints, additional pathway search scales relative to the number of fully independent branches in the optimal pathways, and not relative to the number of reactions in the database or size of the metabolic network. This feature allows all optimal pathways to be determined for a very large number of chemicals and for a large corpus of potential chassis organisms. Availability This algorithm is distributed as part of the RetSynth software package, under a BSD 2-clause license at https://www.github.com/sandialabs/RetSynth/