1. WHAT IS MECHEM? MECHEM is a multi-year project whose goal is to provide a highly capable interactive software tool for exploring reaction mechanisms. 2. HOW DOES THE PROGRAM WORK? The basic approach in MECHEM is to comprehensively search the possible elementary reactions and pathways in a ``first principles'' spirit. The principle involved is that an elementary step involves a small (user-adjustable) number of changes in the bonding of the reactants. Since in mechanism elucidation the reaction starting materials are known (unlike the case of synthesis), MECHEM builds elementary steps of the form "known reactants => X + Y" and then solves for all possible structures of the unknowns X and Y by using ad-hoc graph algorithms and assuming, say, at most three or four total changes (cleavage or formation) to the connectivity of the step's molecular graphs, including X and Y. One could contrast this ``logical'' approach to generating elementary steps with an alternative empirical approach that, say, only generates steps that follow specific reaction schemata such as migratory insertion, reductive elimination, radical recombination, dissociative adsorption, and so on. Thus, it is clear how the program generates initial elementary steps from the starting materials. After X and Y become specific species, then the program can consider all possible second steps in a similar manner. The ``space'' of possible pathways is simply the set of possible lists of such elementary steps. The only unchangeable assumption in MECHEM is that all elementary steps have at most two reactants and at most two products; there are no significant unchangeable assumptions about either elementary steps or mechanisms. The program organizes its search in stages of simplicity, by first trying to find mechanisms that involve no machine-generated species, then one such species, then two, three, and so on. Also, for a fixed number of species, it looks first for mechanisms having fewer steps. Thus, a preference for parsimony is inherent in the search process. The relative absence of built-in assumptions also means that the program has no factual knowledge of any specific chemistry. Thus, one might expect that its output mechanisms will not be very credible. For example, in a catalytic oxidation reaction the program might ignore the catalyst and propose mechanisms that directly oxidize the starting materials. It is the chemist/user's responsibility to drive the process by supplying the right assumptions, based on experimental evidence and background knowledge, so that the final output mechanisms are the simplest plausible ones. The program is designed so that these assumptions (constraints) constrain mechanism generation as early as possible, so that the program will not waste time exploring partial pathways that already violate a constraint. Such efficiencies are crucial for a practical program, given the huge combinatorial spaces that are involved. The final choice of best mechanism, if such a choice is needed in the face of several plausible alternatives, is left to the user. 3. WHAT TASKS DOES MECHEM HELP ON? A. Elucidation of reaction mechanisms. Given the available experimental evidence and other background knowledge which are input by the user/chemist as constraints, the program finds all simplest (fewest species and elementary steps) mechanisms that are consistent with these constraints. Currently there are around 120 constraints to choose from. B. Prediction of catalyst activity and/or selectivity. Given an overall reaction, a number of alternative catalysts, a reaction network of elementary steps, and the energetics (e.g., activation energies) of these steps on the different catalysts, predict which are the more active (or selective) catalysts, i.e., rank them. The output is a ranking supplemented by specific pathways (and their energetics) that justify the ranking. C. Prediction of the results of isotopic labelling experiments. Given a reaction mechanism, a designation of which steps are reversible, and labelled starting materials, the program calculates which labelled products and intermediates can be formed via the mechanisms. 4. WHY SHOULD I USE A COMPUTER PROGRAM TO FIND MECHANISMS? Our experience on every reaction we have tried is that the simpler mechanisms consistent with the available evidence are surprisingly numerous. It is very easy to miss simple plausible mechanisms without a comprehensive search. Also, getting a fuller set of mechanisms at the start of an experimental study helps to design better discriminating experiments. In short, we believe that chemist + mechem >> chemist. 5. WHAT CHEMISTRY HAS MECHEM BEEN USED ON? MECHEM has been applied mostly to heterogeneous and homogeneous catalysis, because that has been the expertise of its developers and the collaborators to date. Exploratory applications to atmospheric and chemical vapor deposition chemistries have also been done. 6. WHAT CHEMISTRY IS MECHEM (IN)APPROPRIATE FOR? MECHEM's application is not limited to any specific chemistry, although some limitations do exist: (1) MECHEM cannot deal with mechanisms that have too many steps and conjectured species or that contain large reacting molecules for reasons of combinatorics. These problems can sometimes be overcome by declaring some fragments of the starting materials as unreactable. As a rule, MECHEM works reasonably fast on the mechanisms with up to 7-10 conjectured species and 10-14 steps, which means that it works better on the more selective chemistries. (2) MECHEM does not currently represent ions. They are not hard to represent, but the resulting increase in combinatorics appears, at this point, to outweigh the gain in the program's scope. (3) On heterogeneous catalytic reactions, the program does not consider transport phenomena, weakness/strength of adsorption, catalyst phases, and other surface science aspects. These factors can be taken into account when the chemist interprets the output mechanisms. (4) MECHEM does not deal with multicentered and delocalized bonds. That is, a benzene ring has to be represented by the system of conjugated double bonds. Pi-coordinated molecules also cannot be represented directly, but can be modeled in most cases by other species, e.g.,, a pi-acetylene complex with a metal M can be modeled by a three-membered cycle of two carbon and one metal ions with a double bond between carbons. (5) MECHEM distinguishes only structural isomers, it does not recognize stereochemistry. For example, cis/trans isomers are not distinguished. (6) MECHEM does not itself calculate the thermodynamic and activation parameters of elementary reactions, nor does it simulate kinetics or estimate kinetic parameters. Instead, external specialized methods and software can be used for these purposes. (7) The program can build on the chemist's prior knowledge only if that kind of knowledge has been anticipated in the design and programming of the constraints. However, the set of constraints is constantly enlarged as the need arises during applications. Moreover, the user can prohibit specific steps or species even if the more general reason for the prohibition has not been anticipated in the current constraints. 7. WHAT IS NEEDED TO RUN THE PROGRAM? MECHEM is written entirely in Common Lisp, which is available for Unix, Linux, and Windows, among others. It is best to have substantial RAM. We run the program just fine on a 300 MHz, 192Mb laptop running Linux. Nothing besides a Lisp compiler/interpreter is needed for the plain version, which uses a simple but convenient command-line interface. A nice graphical user interface written in Tcl/Tk runs on Unix. 8. IS THE PROGRAM AVAILABLE? The program is available on a case-by-case basis. Note that we are not currently set up to widely distribute and support the program. However, we have done a number of collaborations with interested chemists, where we identify whether MECHEM is appropriate, formulate the problem jointly, run the program from here, and exchange results and problem refinements by email. Inquiries about program availability can be addressed to valdes@cs.cmu.edu. 9. WHAT PUBLICATIONS ARE THERE? View www.cs.cmu.edu/~sci-disc/chemistry for chemistry publications by the program's developers and some of their collaborators. 10. WHO HAS WORKED ON THE PROJECT? Raul E. Valdes-Perez, Senior Research Scientist, Computer Science Department, Carnegie Mellon University (www.cs.cmu.edu/~sci-disc). Algorithms, knowledge engineering, software, applications. Andrew V. Zeigarnik, Assistant Professor, Lomonosov Academy of Fine Chemical Technology Moscow, Russia (www.mitht.rssi.ru/~azeigarn). Knowledge engineering, applications, algorithms. Brian S. White, formerly Carnegie Mellon undergraduate student. Graphical user interface.