Send to:

Choose Destination
See comment in PubMed Commons below
Bioinformatics. 2012 Jun 15;28(12):1619-23. doi: 10.1093/bioinformatics/bts255. Epub 2012 Apr 28.

Truncated branch and bound achieves efficient constraint-based genetic design.

Author information

  • 1Center for Computational and Integrative Biology and Department of Computer Science, Rutgers University, Camden, NJ 08102, USA.



Computer-aided genetic design is a promising approach to a core problem of metabolic engineering-that of identifying genetic manipulation strategies that result in engineered strains with favorable product accumulation. This approach has proved to be effective for organisms including Escherichia coli and Saccharomyces cerevisiae, allowing for rapid, rational design of engineered strains. Finding optimal genetic manipulation strategies, however, is a complex computational problem in which running time grows exponentially with the number of manipulations (i.e. knockouts, knock-ins or regulation changes) in the strategy. Thus, computer-aided gene identification has to date been limited in the complexity or optimality of the strategies it finds or in the size and level of detail of the metabolic networks under consideration.


Here, we present an efficient computational solution to the gene identification problem. Our approach significantly outperforms previous approaches--in seconds or minutes, we find strategies that previously required running times of days or more.


GDBB is implemented using MATLAB and is freely available for non-profit use at

[PubMed - indexed for MEDLINE]
Free full text
PubMed Commons home

PubMed Commons

How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for HighWire
    Loading ...
    Write to the Help Desk