Automated reaction mapping: enhanced algorithms and applications

Reaction mapping is an NP-Complete optimization problem. This dissertation makes four contributions that enhance reaction mapping algorithms and develop its applications. Our four contributions include: (1) The design of five algorithms that obtain optimal solutions to reaction mapping with significantly improved run times relative to the previous Constructive Count Vector algorithm, (2) The development of classification rules for a rule-based expert system which organizes reactions into classes, such as hydrogen abstraction and beta-scission, using the results from our reaction mapping software, (3) The development of a technique to perform isomer analysis by using a new all-pairs reaction mapping algorithm followed by an analysis using social network metrics, and (4) The development of two random graph models used to model chemical graphs that are more relevant to cheminformatics than previous random graph models.