Large-scale identification of genetic design strategies using local search

Desmond Lun, Graham Rockwell, Nicholas J. Guido, Michael Baym, Jonathan A. Kelner, Bonnie Berger, James E. Galagan, George M. Church

Research output: Contribution to journalArticle

106 Citations (Scopus)

Abstract

In the past decade, computational methods have been shown to be well suited to unraveling the complex web of metabolic reactions in biological systems. Methods based on flux-balance analysis (FBA) and bi-level optimization have been used to great effect in aiding metabolic engineering. These methods predict the result of genetic manipulations and allow for the best set of manipulations to be found computationally. Bi-level FBA is, however, limited in applicability because the required computational time and resources scale poorly as the size of the metabolic system and the number of genetic manipulations increase. To overcome these limitations, we have developed Genetic Design through Local Search (GDLS), a scalable, heuristic, algorithmic method that employs an approach based on local search with multiple search paths, which results in effective, low-complexity search of the space of genetic manipulations. Thus, GDLS is able to find genetic designs with greater in silico production of desired metabolites than can feasibly be found using a globally optimal search and performs favorably in comparison with heuristic searches based on evolutionary algorithms and simulated annealing.

Original languageEnglish (US)
Article number296
JournalMolecular Systems Biology
Volume5
DOIs
StatePublished - Jan 20 2009

Fingerprint

Local Search
genetic engineering
Manipulation
Fluxes
Metabolic engineering
Biological systems
Metabolites
Computational methods
Simulated annealing
Metabolic Engineering
Evolutionary algorithms
metabolic engineering
annealing
methodology
Computer Simulation
Bilevel Optimization
Heuristic Search
metabolites
Biological Systems
Simulated Annealing

All Science Journal Classification (ASJC) codes

  • Agricultural and Biological Sciences(all)
  • Applied Mathematics
  • Biochemistry, Genetics and Molecular Biology(all)
  • Immunology and Microbiology(all)

Keywords

  • Bi-level optimization
  • Flux-balance analysis
  • Metabolic engineering
  • Mixed-integer linear programming
  • Strain optimization

Cite this

Lun, D., Rockwell, G., Guido, N. J., Baym, M., Kelner, J. A., Berger, B., ... Church, G. M. (2009). Large-scale identification of genetic design strategies using local search. Molecular Systems Biology, 5, [296]. https://doi.org/10.1038/msb.2009.57
Lun, Desmond ; Rockwell, Graham ; Guido, Nicholas J. ; Baym, Michael ; Kelner, Jonathan A. ; Berger, Bonnie ; Galagan, James E. ; Church, George M. / Large-scale identification of genetic design strategies using local search. In: Molecular Systems Biology. 2009 ; Vol. 5.
@article{596c0971e0c2416d85e1ae9c03b263e9,
title = "Large-scale identification of genetic design strategies using local search",
abstract = "In the past decade, computational methods have been shown to be well suited to unraveling the complex web of metabolic reactions in biological systems. Methods based on flux-balance analysis (FBA) and bi-level optimization have been used to great effect in aiding metabolic engineering. These methods predict the result of genetic manipulations and allow for the best set of manipulations to be found computationally. Bi-level FBA is, however, limited in applicability because the required computational time and resources scale poorly as the size of the metabolic system and the number of genetic manipulations increase. To overcome these limitations, we have developed Genetic Design through Local Search (GDLS), a scalable, heuristic, algorithmic method that employs an approach based on local search with multiple search paths, which results in effective, low-complexity search of the space of genetic manipulations. Thus, GDLS is able to find genetic designs with greater in silico production of desired metabolites than can feasibly be found using a globally optimal search and performs favorably in comparison with heuristic searches based on evolutionary algorithms and simulated annealing.",
keywords = "Bi-level optimization, Flux-balance analysis, Metabolic engineering, Mixed-integer linear programming, Strain optimization",
author = "Desmond Lun and Graham Rockwell and Guido, {Nicholas J.} and Michael Baym and Kelner, {Jonathan A.} and Bonnie Berger and Galagan, {James E.} and Church, {George M.}",
year = "2009",
month = "1",
day = "20",
doi = "https://doi.org/10.1038/msb.2009.57",
language = "English (US)",
volume = "5",
journal = "Molecular Systems Biology",
issn = "1744-4292",
publisher = "Nature Publishing Group",

}

Lun, D, Rockwell, G, Guido, NJ, Baym, M, Kelner, JA, Berger, B, Galagan, JE & Church, GM 2009, 'Large-scale identification of genetic design strategies using local search', Molecular Systems Biology, vol. 5, 296. https://doi.org/10.1038/msb.2009.57

Large-scale identification of genetic design strategies using local search. / Lun, Desmond; Rockwell, Graham; Guido, Nicholas J.; Baym, Michael; Kelner, Jonathan A.; Berger, Bonnie; Galagan, James E.; Church, George M.

In: Molecular Systems Biology, Vol. 5, 296, 20.01.2009.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Large-scale identification of genetic design strategies using local search

AU - Lun, Desmond

AU - Rockwell, Graham

AU - Guido, Nicholas J.

AU - Baym, Michael

AU - Kelner, Jonathan A.

AU - Berger, Bonnie

AU - Galagan, James E.

AU - Church, George M.

PY - 2009/1/20

Y1 - 2009/1/20

N2 - In the past decade, computational methods have been shown to be well suited to unraveling the complex web of metabolic reactions in biological systems. Methods based on flux-balance analysis (FBA) and bi-level optimization have been used to great effect in aiding metabolic engineering. These methods predict the result of genetic manipulations and allow for the best set of manipulations to be found computationally. Bi-level FBA is, however, limited in applicability because the required computational time and resources scale poorly as the size of the metabolic system and the number of genetic manipulations increase. To overcome these limitations, we have developed Genetic Design through Local Search (GDLS), a scalable, heuristic, algorithmic method that employs an approach based on local search with multiple search paths, which results in effective, low-complexity search of the space of genetic manipulations. Thus, GDLS is able to find genetic designs with greater in silico production of desired metabolites than can feasibly be found using a globally optimal search and performs favorably in comparison with heuristic searches based on evolutionary algorithms and simulated annealing.

AB - In the past decade, computational methods have been shown to be well suited to unraveling the complex web of metabolic reactions in biological systems. Methods based on flux-balance analysis (FBA) and bi-level optimization have been used to great effect in aiding metabolic engineering. These methods predict the result of genetic manipulations and allow for the best set of manipulations to be found computationally. Bi-level FBA is, however, limited in applicability because the required computational time and resources scale poorly as the size of the metabolic system and the number of genetic manipulations increase. To overcome these limitations, we have developed Genetic Design through Local Search (GDLS), a scalable, heuristic, algorithmic method that employs an approach based on local search with multiple search paths, which results in effective, low-complexity search of the space of genetic manipulations. Thus, GDLS is able to find genetic designs with greater in silico production of desired metabolites than can feasibly be found using a globally optimal search and performs favorably in comparison with heuristic searches based on evolutionary algorithms and simulated annealing.

KW - Bi-level optimization

KW - Flux-balance analysis

KW - Metabolic engineering

KW - Mixed-integer linear programming

KW - Strain optimization

UR - http://www.scopus.com/inward/record.url?scp=69249146187&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=69249146187&partnerID=8YFLogxK

U2 - https://doi.org/10.1038/msb.2009.57

DO - https://doi.org/10.1038/msb.2009.57

M3 - Article

C2 - 19690565

VL - 5

JO - Molecular Systems Biology

JF - Molecular Systems Biology

SN - 1744-4292

M1 - 296

ER -