As increasing amounts of anthropogenic chemicals are released into the environment, it is vital to human health and the preservation of ecosystems to evaluate the fate of these chemicals in the environment. It is useful to predict whether a particular compound is biodegradable and if alternate routes can be engineered for compounds already known to be biodegradable. In this work, we describe a computational framework (called BNICE) that can be used for the prediction of novel biodegradation pathways of xenobiotics. The framework was applied to 4-chlorobiphenyl, phenanthrene, g-hexachlorocyclohexane, and 1,2,4-trichlorobenzene, compounds representing various classes of xenobiotics with known biodegradation routes. BNICE reproduced the proposed biodegradation routes found experimentally, and in addition, it expanded the biodegradation reaction networks through the generation of novel compounds and reactions. The novel reactions involved in the biodegradation of 1,2,4-trichlorobenzene were studied in depth, where pathway and thermodynamic analyses were performed. This work demonstrates that BNICE can be applied to generate novel pathways to degrade xenobiotic compounds that are thermodynamically feasible alternatives to known biodegradation routes and attractive targets for metabolic engineering. Biotechnol. Bioeng. 2009; 104: 1086-1097. (C) 2009 Wiley Periodicals, Inc.