Computational modeling and analysis of metabolic networks has been successful in metabolic engineering of microbial strains for biochemical production including biofuels. Among different computational approaches, constraint-based models allow for the use of genome-scale metabolic networks, and they can predict metabolic flux distributions in microbial cells. For example, flux balance analysis (FBA) predicts metabolic flux distributions in optimally growing microbial cells. FBA can also predict the effects of gene additions or deletions on metabolic behaviors by adding or removing the associated reactions, respectively. Previous studies have shown that FBA accurately predicts the behaviors of Escherichia coli strains that have undergone adaptive evolution process to optimize their fitness. FBA assumes that cells grow optimally; however, un-evolved mutant strains often exhibit suboptimal growth behaviors before adaptive evolution due to regulatory restrictions or other limitations. Therefore, mutant strains designed using FBA would need to be subjected to adaptive evolution to achieve high biochemical production, which may take several weeks to months. An alternative to FBA is minimization of metabolic adjustment (MOMA), which predicts the behaviors of un-evolved mutants by minimizing the changes in flux distributions between the mutant strains and the parental strains, and it has been used to design mutant E. coli strains for improving lycopene and L-valine production. Another approach, regulatory on/off minimization (ROOM) minimizes the number of significant flux changes in mutant strains relative to the parental strain. Both MOMA and ROOM can better predict qualitative behaviors of un-evolved (e.g., growth phenotypes), but their capabilities are still limited in predicting quantitatively accurate flux distributions. We developed a new approach (RELATCH) to more accurately predict the quantitative flux distributions in un-evolved mutants. With this approach, we first utilize metabolic flux analysis measurements and gene expression data for the parental strain to determine a reference flux distribution. Then, the flux distribution for a knockout mutant strain is predicted by minimizing relative flux changes and additional enzyme usage from the reference flux distribution. We have used RELATCH to predict flux distributions of un-evolved mutants and compared the model predictions to experimental datasets for E. coli, Saccharomyces cerevisiae, and Bacillus subtilis. The results indicate that RELATCH more accurately predicts flux distributions, as well as growth rates, for un-evolved mutants, as compared to existing approaches (MOMA and ROOM). For example, for un-evolved E. coli mutants, the sum of squared errors (between model predictions and experimental results) for the fluxes predicted by RELATCH were 13 or 15 times smaller than the sum of squared errors when MOMA or ROOM was used, respectively. We have also developed a new bi-level mixed-integer programming strain design approach, which considers un-evolved behaviors of mutants. This approach uses a quadratic inner objective function, such as MOMA or RELATCH, to identify mutant strains with improved biochemical production. Therefore, it allows us to design mutant strains which would not require adaptive evolution to achieve high biochemical production. The developed approach extends the scope of computational strain design, and can be used to identify novel metabolic engineering strategies for biofuel production.