The identification of genetic targets that are effective in bringing about a desired phenotype change is still an open problem. While random gene knockouts have yielded improved strains in certain cases, it is also important to seek the guidance of cell-wide stoichiometric constraints in identifying promising gene knockout targets. To investigate these issues, we undertook a genome-wide stoichiometric flux balance analysis as an aid in discovering putative genes impacting network properties and cellular phenotype. Specifically, we calculated metabolic fluxes such as to optimize growth and then scanned the genome for single and multiple gene knockouts that yield improved product yield while maintaining acceptable overall growth rate. For the particular case of lycopene biosynthesis in Escherichia coli, we identified such targets that we subsequently tested experimentally by constructing the corresponding single, double and triple gene knockouts. While such strains are suggested (by the stoichiometric calculations) to increase precursor availability, this beneficial effect may be further impacted by kinetic and regulatory effects not captured by the stoichiometric model. For the case of lycopene biosynthesis, the so identified knockout targets yielded a triple knockout construct that exhibited a nearly 40% increase over an engineered, high producing parental strain.