SPABBATS: A pathway-discovery method based on Boolean satisfiability that facilitates the characterization of suppressor mutants

Here we present SPABBATS, an algorithm based on Boolean satisfiability (SAT) that computes alternative metabolic pathways between input and output species in a reconstructed network. The pathways can be constructed iteratively in order of increasing complexity. SPABBATS allows the accumulation of intermediates in the pathways, which permits discovering pathways missed by most traditional pathway analysis methods. In addition, we provide a proof of concept experiment for the validity of the algorithm. We deleted the genes for the glutamate dehydrogenases of the Gram-positive bacterium Bacillus subtilis and isolated suppressor mutant strains able to grow on glutamate as single carbon source. Our SAT approach proposed candidate alternative pathways which were decisive to pinpoint the exact mutation of the suppressor strain.SPABBATS is the first application of SAT techniques to metabolic problems. It is particularly useful for the characterization of metabolic suppressor mutants and can be used in a synthetic biology setting to design new pathways with specific input-output requirements.A holistic understanding of cellular metabolism is central to systems biology and metabolic engineering: In order to amplify the flux through production pathways in industrial strains we have to understand how the metabolic network responds to our interventions.Several methods can suggest rational interventions that may lead to favourable industrial phenotypes (see [1] for a review). Their goal is to optimize the distribution of metabolic fluxes towards the product of interest, either directly (e.g. FBA, MOMA or ROOM) or indirectly by coupling it to another characteristic (e.g. OptKnock) that facilitates further strain improvements via mutation and screening.While these methods can predict a final flux distribution, they do not predict the range of genetic and metabolic responses of the organism after the targeted mutation. At the same time, it would be highly desirable to have tools tha