%0 Journal Article %1 Eng2016Algorithm %A Eng, Alexander %A Borenstein, Elhanan %D 2016 %I Oxford University Press %J Bioinformatics %K communities flux-analysis %N 13 %P 2008--2016 %R 10.1093/bioinformatics/btw107 %T An algorithm for designing minimal microbial communities with desired metabolic capacities %U http://dx.doi.org/10.1093/bioinformatics/btw107 %V 32 %X Motivation: Recent efforts to manipulate various microbial communities, such as fecal microbiota transplant and bioreactor systems' optimization, suggest a promising route for microbial community engineering with numerous medical, environmental and industrial applications. However, such applications are currently restricted in scale and often rely on mimicking or enhancing natural communities, calling for the development of tools for designing synthetic communities with specific, tailored, desired metabolic capacities.Results: Here, we present a first step toward this goal, introducing a novel algorithm for identifying minimal sets of microbial species that collectively provide the enzymatic capacity required to synthesize a set of desired target product metabolites from a predefined set of available substrates. Our method integrates a graph theoretic representation of network flow with the set cover problem in an integer linear programming (ILP) framework to simultaneously identify possible metabolic paths from substrates to products while minimizing the number of species required to catalyze these metabolic reactions. We apply our algorithm to successfully identify minimal communities both in a set of simple toy problems and in more complex, realistic settings, and to investigate metabolic capacities in the gut microbiome. Our framework adds to the growing toolset for supporting informed microbial community engineering and for ultimately realizing the full potential of such engineering efforts.Availability and implementation: The algorithm source code, compilation, usage instructions and examples are available under a non-commercial research use only license at https://github.com/borenstein-lab/CoMiDA.Contact: elbo@uw.eduSupplementary information: Supplementary data are available at Bioinformatics online.

@article{Eng2016Algorithm, abstract = {Motivation: Recent efforts to manipulate various microbial communities, such as fecal microbiota transplant and bioreactor systems' optimization, suggest a promising route for microbial community engineering with numerous medical, environmental and industrial applications. However, such applications are currently restricted in scale and often rely on mimicking or enhancing natural communities, calling for the development of tools for designing synthetic communities with specific, tailored, desired metabolic {capacities.Results}: Here, we present a first step toward this goal, introducing a novel algorithm for identifying minimal sets of microbial species that collectively provide the enzymatic capacity required to synthesize a set of desired target product metabolites from a predefined set of available substrates. Our method integrates a graph theoretic representation of network flow with the set cover problem in an integer linear programming ({ILP}) framework to simultaneously identify possible metabolic paths from substrates to products while minimizing the number of species required to catalyze these metabolic reactions. We apply our algorithm to successfully identify minimal communities both in a set of simple toy problems and in more complex, realistic settings, and to investigate metabolic capacities in the gut microbiome. Our framework adds to the growing toolset for supporting informed microbial community engineering and for ultimately realizing the full potential of such engineering {efforts.Availability} and implementation: The algorithm source code, compilation, usage instructions and examples are available under a non-commercial research use only license at {https://github.com/borenstein-lab/CoMiDA}.Contact: {elbo@uw.eduSupplementary} information: Supplementary data are available at Bioinformatics online.}, added-at = {2018-12-02T16:09:07.000+0100}, author = {Eng, Alexander and Borenstein, Elhanan}, biburl = {https://www.bibsonomy.org/bibtex/29c9d42d7f4d3fe63f042405c618b214f/karthikraman}, citeulike-article-id = {13971540}, citeulike-linkout-0 = {http://dx.doi.org/10.1093/bioinformatics/btw107}, citeulike-linkout-1 = {http://bioinformatics.oxfordjournals.org/content/early/2016/02/25/bioinformatics.btw107.abstract}, citeulike-linkout-2 = {http://bioinformatics.oxfordjournals.org/content/early/2016/02/25/bioinformatics.btw107.full.pdf}, citeulike-linkout-3 = {http://bioinformatics.oxfordjournals.org/cgi/content/abstract/32/13/2008}, citeulike-linkout-4 = {http://view.ncbi.nlm.nih.gov/pubmed/27153571}, citeulike-linkout-5 = {http://www.hubmed.org/display.cgi?uids=27153571}, day = 1, doi = {10.1093/bioinformatics/btw107}, interhash = {bcd4006005ddbeaf9a33bafc80a1b11c}, intrahash = {9c9d42d7f4d3fe63f042405c618b214f}, issn = {1460-2059}, journal = {Bioinformatics}, keywords = {communities flux-analysis}, month = jul, number = 13, pages = {2008--2016}, pmid = {27153571}, posted-at = {2016-03-07 17:51:53}, priority = {2}, publisher = {Oxford University Press}, timestamp = {2018-12-02T16:09:07.000+0100}, title = {An algorithm for designing minimal microbial communities with desired metabolic capacities}, url = {http://dx.doi.org/10.1093/bioinformatics/btw107}, volume = 32, year = 2016 }