We present the application of heuristic search to in silico metabolic pathway engineering. In particular, we discuss a new computational approach to elucidate complex pathways and to address the practical challenge of combinatorial complexity in pathway inference. We have implemented this approach in a new computational framework, called PathMiner, which is useful for designing metabolic engineering strategies. In this paper, we describe our approach to analyze pathways for the de novo synthesis of vanillin, as well as a transgenic strategy to implement these in a number of hosts. Using PathMiner we are able to automatically elucidate a 19-step pathway for de novo vanillin synthesis from D-glucose, which is in close agreement with the routes reported in the literature. This paper represents a novel integration of artificial intelligence and biochemistry for computational metabolic engineering. As high-throughput biology generates increasing amounts of genomic and metabolic data, automated in silico approaches will become increasingly useful for making biologically useful predictions. (c) 2004 Published by Elsevier Ltd.