{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T01:20:34Z","timestamp":1778721634980,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Syst Biol"],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>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 <jats:italic>Bacillus subtilis<\/jats:italic> 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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1752-0509-5-5","type":"journal-article","created":{"date-parts":[[2011,1,21]],"date-time":"2011-01-21T19:17:28Z","timestamp":1295637448000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["SPABBATS: A pathway-discovery method based on Boolean satisfiability that facilitates the characterization of suppressor mutants"],"prefix":"10.1186","volume":"5","author":[{"given":"Lope A","family":"Fl\u00f3rez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katrin","family":"Gunka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafael","family":"Polan\u00eda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Tholen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg","family":"St\u00fclke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,1,11]]},"reference":[{"key":"595_CR1","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1038\/nbt1401","volume":"26","author":"AM Feist","year":"2008","unstructured":"Feist AM, Palsson B\u00d8: The growing scope of applications of genome-scale metabolic reconstructions using Escherichia coli. Nat Biotechnol. 2008, 26: 659-667. 10.1038\/nbt1401","journal-title":"Nat Biotechnol"},{"key":"595_CR2","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1093\/bib\/bbn018","volume":"9","author":"FJ Planes","year":"2008","unstructured":"Planes FJ, Beasley JE: A critical examination of stoichiometric and path-finding approaches to metabolic pathways. Brief Bioinform. 2008, 9: 422-436. 10.1093\/bib\/bbn018","journal-title":"Brief Bioinform"},{"key":"595_CR3","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1023\/A:1020390132244","volume":"29","author":"S Klamt","year":"2002","unstructured":"Klamt S, Stelling J: Combinatorial complexity of pathway analysis in metabolic networks. Mol Biol Rep. 2002, 29: 233-236. 10.1023\/A:1020390132244","journal-title":"Mol Biol Rep"},{"key":"595_CR4","doi-asserted-by":"publisher","first-page":"3158","DOI":"10.1093\/bioinformatics\/btp564","volume":"25","author":"LF de Figueiredo","year":"2009","unstructured":"de Figueiredo LF, Podhorski A, Rubio A, Kaleta C, Beasley JE, Schuster S, Planes FJ: Computing the shortest elementary flux modes in genome-scale metabolic networks. Bioinformatics. 2009, 25: 3158-3165. 10.1093\/bioinformatics\/btp564","journal-title":"Bioinformatics"},{"key":"595_CR5","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s10626-009-0081-8","volume":"19","author":"K Claessen","year":"2009","unstructured":"Claessen K, Een N, Sheeran M, S\u00f6rensson N, Voronov A, \u00c5kesson K: SAT-solving in practice, with a tutorial example from supervisory control. Discrete Event Dyn Syst. 2009, 19: 495-524. 10.1007\/s10626-009-0081-8.","journal-title":"Discrete Event Dyn Syst"},{"key":"595_CR6","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1038\/msb.2009.60","volume":"5","author":"J Yuan","year":"2009","unstructured":"Yuan J, Doucette CD, Fowler WU, Feng XJ, Piazza M, Rabitz HA, Wingreen NS, Rabinowitz JD: Metabolomics-driven quantitative analysis of ammonia assimilation in E. coli. Mol Syst Biol. 2009, 5: 302- 10.1038\/msb.2009.60","journal-title":"Mol Syst Biol"},{"key":"595_CR7","doi-asserted-by":"publisher","first-page":"2527","DOI":"10.1099\/00221287-136-12-2527","volume":"136","author":"AM Whatmore","year":"1990","unstructured":"Whatmore AM, Chudek JA, Reed RH: The effects of osmotic upshock on the intracellular solute pools of Bacillus subtilis. J Gen Microbiol. 1990, 136: 2527-2535.","journal-title":"J Gen Microbiol"},{"key":"595_CR8","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.mib.2006.01.001","volume":"9","author":"FM Commichau","year":"2006","unstructured":"Commichau FM, Forchhammer K, St\u00fclke J: Regulatory links between carbon and nitrogen metabolism. Curr Opin Microbiol. 2006, 9: 167-172. 10.1016\/j.mib.2006.01.001","journal-title":"Curr Opin Microbiol"},{"key":"595_CR9","doi-asserted-by":"publisher","first-page":"28791","DOI":"10.1074\/jbc.M703759200","volume":"282","author":"YK Oh","year":"2007","unstructured":"Oh YK, Palsson B\u00d8, Park SM, Schilling CH, Mahadevan R: Genome-scale reconstruction of metabolic network in Bacillus subtilis based on high-throughput phenotyping and gene essentiality data. J Biol Chem. 2007, 282: 28791-28799. 10.1074\/jbc.M703759200","journal-title":"J Biol Chem"},{"key":"595_CR10","doi-asserted-by":"crossref","first-page":"6298","DOI":"10.1128\/JB.180.23.6298-6305.1998","volume":"180","author":"BR Belitsky","year":"1998","unstructured":"Belitsky BR, Sonenshein AL: Role and regulation of Bacillus subtilis glutamate dehydrogenase genes. J Bacteriol. 1998, 180: 6298-6305.","journal-title":"J Bacteriol"},{"key":"595_CR11","doi-asserted-by":"publisher","first-page":"3557","DOI":"10.1128\/JB.00099-08","volume":"190","author":"FM Commichau","year":"2008","unstructured":"Commichau FM, Gunka K, Landmann JJ, St\u00fclke J: Glutamate metabolism in Bacillus subtilis: gene expression and enzyme activities evolved to avoid futile cycles and to allow rapid responses to perturbations of the system. J Bacteriol. 2008, 190: 3557-3564. 10.1128\/JB.00099-08","journal-title":"J Bacteriol"},{"key":"595_CR12","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1111\/j.1365-2958.2007.05816.x","volume":"65","author":"FM Commichau","year":"2007","unstructured":"Commichau FM, Herzberg C, Tripal P, Valerius O, St\u00fclke J: A regulatory protein-protein interaction governs glutamate biosynthesis in Bacillus subtilis: the glutamate dehydrogenase RocG moonlights in controlling the transcription factor GltC. Mol Microbiol. 2007, 65: 642-654. 10.1111\/j.1365-2958.2007.05816.x","journal-title":"Mol Microbiol"},{"key":"595_CR13","doi-asserted-by":"publisher","first-page":"3399","DOI":"10.1128\/JB.186.11.3399-3407.2004","volume":"186","author":"BR Belitsky","year":"2004","unstructured":"Belitsky BR, Sonenshein AL: Modulation of activity of Bacillus subtilis regulatory proteins GltC and TnrA by glutamate dehydrogenase. J Bacteriol. 2004, 186: 3399-3407. 10.1128\/JB.186.11.3399-3407.2004","journal-title":"J Bacteriol"},{"key":"595_CR14","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1159\/000096465","volume":"12","author":"FM Commichau","year":"2007","unstructured":"Commichau FM, Wacker I, Schleider J, Blencke HM, Reif I, Tripal P, St\u00fclke J: Characterization of Bacillus subtilis mutants with carbon source-independent glutamate biosynthesis. J Mol Microbiol Biotechnol. 2007, 12: 106-113. 10.1159\/000096465","journal-title":"J Mol Microbiol Biotechnol"},{"key":"595_CR15","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF00425702","volume":"211","author":"IM Feavers","year":"1998","unstructured":"Feavers IM, Price V, Moir A: The regulation of the fumarase (citG) gene of Bacillus subtilis 168. Mol Gen Genet. 1998, 211: 465-471. 10.1007\/BF00425702.","journal-title":"Mol Gen Genet"},{"key":"595_CR16","doi-asserted-by":"crossref","first-page":"4680","DOI":"10.1128\/jb.176.15.4680-4690.1994","volume":"176","author":"S Jin","year":"1994","unstructured":"Jin S, Sonenshein AL: Transcriptional regulation of Bacillus subtilis citrate synthase genes. J Bacteriol. 1994, 176: 4680-4690.","journal-title":"J Bacteriol"},{"key":"595_CR17","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S1096-7176(03)00009-0","volume":"5","author":"HM Blencke","year":"2003","unstructured":"Blencke HM, Homuth G, Ludwig H, M\u00e4der U, Hecker M, St\u00fclke J: Transcriptional profiling of gene expression in response to glucose in Bacillus subtilis: regulation of the central metabolic pathways. Metab Engn. 2003, 5: 133-149. 10.1016\/S1096-7176(03)00009-0.","journal-title":"Metab Engn"},{"key":"595_CR18","doi-asserted-by":"crossref","first-page":"3831","DOI":"10.1128\/jb.173.12.3831-3845.1991","volume":"173","author":"DX Sun","year":"1991","unstructured":"Sun DX, Setlow P: Cloning, nucleotide sequence, and expression of the Bacillus subtilis ans operon, which codes for L-asparaginase and L-aspartase. J Bacteriol. 1991, 173: 3831-3845.","journal-title":"J Bacteriol"},{"key":"595_CR19","doi-asserted-by":"crossref","first-page":"2501","DOI":"10.1128\/jb.175.9.2501-2506.1993","volume":"175","author":"D Sun","year":"1993","unstructured":"Sun D, Setlow P: Cloning and nucleotide sequence of the Bacillus subtilis ansR gene, which encodes a repressor for the ans operon coding for L-asparaginase and L-aspartase. J Bacteriol. 1993, 175: 2501-2506.","journal-title":"J Bacteriol"},{"issue":"8","key":"595_CR20","doi-asserted-by":"publisher","first-page":"2148","DOI":"10.1128\/JB.184.8.2148-2154.2002","volume":"184","author":"SH Fisher","year":"2002","unstructured":"Fisher SH, Wray LV: Bacillus subtilis 168 contains two differentially regulated genes encoding L-asparaginase. J Bacteriol. 2002, 184 (8): 2148-54. 10.1128\/JB.184.8.2148-2154.2002","journal-title":"J Bacteriol"},{"key":"595_CR21","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1038\/nbt.1614","volume":"28","author":"JD Orth","year":"2010","unstructured":"Orth JD, Thiele I, Palsson B\u00d8: What is flux balance analysis?. Nat Biotechnol. 2010, 28: 245-248. 10.1038\/nbt.1614","journal-title":"Nat Biotechnol"},{"key":"595_CR22","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-540-73433-8_10","volume-title":"Algebraic Biology","author":"A Gra\u00e7a","year":"2007","unstructured":"Gra\u00e7a A, Marques-Silva J, Lynce I, Oliveira AL: Efficient haplotype inference with pseudo-Boolean optimization. Algebraic Biology. 2007, 125-139. Springer Verlag Berlin\/Heidelberg"},{"key":"595_CR23","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1186\/1752-0509-2-20","volume":"2","author":"A Goelzer","year":"2008","unstructured":"Goelzer A, Bekkal Brikci F, Martin-Verstraete I, Noirot P, Bessi\u00e8res P, Aymerich S, Fromion V: Reconstruction and analysis of the genetic and metabolic regulatory networks of the central metabolism of Bacillus subtilis. BMC Syst Biol. 2008, 2: 20- 10.1186\/1752-0509-2-20","journal-title":"BMC Syst Biol"},{"key":"595_CR24","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1099\/mic.0.035790-0","volume":"156","author":"CR Lammers","year":"2010","unstructured":"Lammers CR, Fl\u00f3rez LA, Schmeisky AG, Roppel SF, M\u00e4der U, Hamoen L, St\u00fclke J: Connecting parts with processes: Subti Wiki and Subti Pathways integrate gene and pathway annotation for Bacillus subtilis. Microbiology. 2010, 156: 849-859. 10.1099\/mic.0.035790-0","journal-title":"Microbiology"},{"key":"595_CR25","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1038\/msb.2010.2","volume":"6","author":"C Lou","year":"2010","unstructured":"Lou C, Liu X, Ni M, Huang Y, Huang Q, Huang L, Jiang L, Lu D, Wang M, Liu C, Chen D, Chen C, Chen X, Yang L, Ma H, Chen J, Ouyang Q: Synthesizing a novel genetic sequential logic circuit: a push-on push-off switch. Mol Syst Biol. 2010, 6: 350- 10.1038\/msb.2010.2","journal-title":"Mol Syst Biol"},{"key":"595_CR26","doi-asserted-by":"publisher","first-page":"S6","DOI":"10.1186\/1471-2105-9-S6-S6","volume":"9","author":"G Chin Jr","year":"2008","unstructured":"Chin G, Chavarria DG, Nakamura GC, Sofia HJ: BioGraphE: high-performance bionetwork analysis using the Biological Graph Environment. BMC Bioinformatics. 2008, 9: S6- 10.1186\/1471-2105-9-S6-S6","journal-title":"BMC Bioinformatics"},{"key":"595_CR27","doi-asserted-by":"publisher","first-page":"3831","DOI":"10.1242\/dev.041764","volume":"136","author":"R Piran","year":"2009","unstructured":"Piran R, Halperin E, Guttmann-Raviv N, Keinan E, Reshef R: Algorithm of myogenic differentiation in higher-order organisms. Development. 2009, 136: 3831-3840. 10.1242\/dev.041764","journal-title":"Development"},{"key":"595_CR28","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-540-73433-8_12","volume-title":"Algebraic Biology","author":"A Tiwari","year":"2007","unstructured":"Tiwari A, Talcott C, Knapp M, Lincoln P, Laderoute K: Analyzing Pathways Using SAT-Based Approaches. Algebraic Biology. 2007, 155-169. full_text. Springer Verlag Berlin\/Heidelberg"},{"key":"595_CR29","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1109\/TCBB.2007.70254","volume":"5","author":"H de Jong","year":"2008","unstructured":"de Jong H, Page M: Search for steady states of piecewise-linear differential equation models of genetic regulatory networks. IEEE\/ACM Trans Comput Biol Bioinform. 2008, 5: 208-22. 10.1109\/TCBB.2007.70254","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"595_CR30","first-page":"209","volume":"1","author":"M Fr\u00e4nzle","year":"2007","unstructured":"Fr\u00e4nzle M, Herde C, Teige T: Efficient solving of large non-linear arithmetic constraint systems with complex Boolean structure. Journal on Satisfiability. 2007, 1: 209-236.","journal-title":"Journal on Satisfiability"},{"key":"595_CR31","volume-title":"Molecular cloning: a laboratory manual","author":"J Sambrook","year":"1989","unstructured":"Sambrook J, Fritsch EF, Maniatis T: Molecular cloning: a laboratory manual. 1989, Cold Spring Harbor Laboratory, Cold Spring Harbor, N.Y, 2","edition":"2"},{"key":"595_CR32","doi-asserted-by":"publisher","first-page":"3001","DOI":"10.1099\/mic.0.26479-0","volume":"149","author":"I Wacker","year":"2003","unstructured":"Wacker I, Ludwig H, Reif I, Blencke HM, Detsch C, St\u00fclke J: The regulatory link between carbon and nitrogen metabolism in Bacillus subtilis: regulation of the gltAB operon by the catabolite control protein CcpA. Microbiology. 2003, 149: 3001-3009. 10.1099\/mic.0.26479-0","journal-title":"Microbiology"},{"key":"595_CR33","doi-asserted-by":"crossref","first-page":"2403","DOI":"10.1128\/jb.177.9.2403-2407.1995","volume":"177","author":"F Kunst","year":"1995","unstructured":"Kunst F, Rapoport G: Salt stress is an environmental signal affecting degradative enzyme synthesis in Bacillus subtilis. J Bacteriol. 1995, 177: 2403-2407.","journal-title":"J Bacteriol"},{"key":"595_CR34","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1006\/jmbi.1994.1487","volume":"241","author":"I Martin-Verstraete","year":"1994","unstructured":"Martin-Verstraete I, D\u00e9barbouill\u00e9 M, Klier A, Rapoport G: Interaction of wild-type truncated LevR of Bacillus subtilis with the upstream activating sequence of the levanase operon. J Mol Biol. 1994, 241: 178-192. 10.1006\/jmbi.1994.1487","journal-title":"J Mol Biol"},{"key":"595_CR35","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0378-1119(95)00652-4","volume":"167","author":"AM Gu\u00e9rout-Fleury","year":"1995","unstructured":"Gu\u00e9rout-Fleury AM, Shazand K, Frandsen N, Stragier P: Antibiotic-resistance cassettes for Bacillus subtilis. Gene. 1995, 167: 335-336.","journal-title":"Gene"},{"key":"595_CR36","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1002\/(SICI)1097-0061(19960315)12:3<259::AID-YEA901>3.0.CO;2-C","volume":"12","author":"A Wach","year":"1996","unstructured":"Wach A: PCR-synthesis of marker cassettes with long flanking homology regions for gene disruptions in Saccharomyces cerevisiae. Yeast. 1996, 12: 259-265. 10.1002\/(SICI)1097-0061(19960315)12:3<259::AID-YEA901>3.0.CO;2-C","journal-title":"Yeast"},{"key":"595_CR37","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1046\/j.1365-2958.2001.02523.x","volume":"41","author":"H Ludwig","year":"2001","unstructured":"Ludwig H, Homuth G, Schmalisch M, Dyka FM, Hecker M, St\u00fclke J: Transcription of glycolytic genes and operons in Bacillus subtilis: Evidence for the presence of multiple levels of control of the gapA operon. Mol Microbiol. 2001, 41: 409-422. 10.1046\/j.1365-2958.2001.02523.x","journal-title":"Mol Microbiol"},{"key":"595_CR38","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1111\/j.1365-2958.2008.06194.x","volume":"68","author":"E Rietk\u00f6tter","year":"2008","unstructured":"Rietk\u00f6tter E, Hoyer D, Mascher T: Bacitracin sensing in Bacillus subtilis. Mol Microbiol. 2008, 68: 768-785.","journal-title":"Mol Microbiol"}],"container-title":["BMC Systems Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1752-0509-5-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T13:41:10Z","timestamp":1630503670000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcsystbiol.biomedcentral.com\/articles\/10.1186\/1752-0509-5-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,11]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["595"],"URL":"https:\/\/doi.org\/10.1186\/1752-0509-5-5","relation":{},"ISSN":["1752-0509"],"issn-type":[{"value":"1752-0509","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,11]]},"assertion":[{"value":"4 August 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2011","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2011","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"5"}}