title: SPABBATS: A pathway-discovery method based on Boolean satisfiability that facilitates the characterization of suppressor mutants.
abstract: BACKGROUND
  Several computational methods exist to suggest rational genetic interventions that improve the productivity of industrial strains. Nonetheless, these methods are less effective to predict possible genetic responses of the strain after the intervention. This problem requires a better understanding of potential alternative metabolic and regulatory pathways able to counteract the targeted intervention.
  
  
  RESULTS
  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.
  
  
  CONCLUSIONS
  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.
authors.affiliation: Department of General Microbiology, Georg-August-University of Göttingen, Germany.
authors.forename: Lope A
authors.initials: LA
authors.lastname: Flórez
authors.forename: Katrin
authors.initials: K
authors.lastname: Gunka
authors.forename: Rafael
authors.initials: R
authors.lastname: Polanía
authors.forename: Stefan
authors.initials: S
authors.lastname: Tholen
authors.forename: Jörg
authors.initials: J
authors.lastname: Stülke
mesh_terms: D000465:Algorithms; D001412:Bacillus subtilis / Q000166:cytology / Q000235:genetics / Q000378:metabolism; D002470:Cell Survival; D019295:Computational Biology / Q000379:methods*; D005969:Glutamate Dehydrogenase / Q000378:metabolism; D018698:Glutamic Acid / Q000378:metabolism; D008128:Logic; D053858:Metabolic Networks and Pathways / Q000235:genetics*; D015203:Reproducibility of Results; D013489:Suppression, Genetic
chemical_list: D018698:Glutamic Acid; D005969:Glutamate Dehydrogenase