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

Abstract

MotivationNaive 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.\n\nResultsHere 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.\n\nAvailabilityThis algorithm is distributed as part of the RetSynth software package, under a BSD 2-clause license at https://www.github.com/sandialabs/RetSynth/