CLCA: Maximum common molecular substructure queries within the MetRxn database

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


The challenge of automatically identifying the preserved molecular moieties in a chemical reaction is referred to as the atom mapping problem. Reaction atom maps provide the ability to locate the fate of individual atoms across an entire metabolic network. Atom maps are used to track atoms in isotope labeling experiments for metabolic flux elucidation, trace novel biosynthetic routes to a target compound, and contrast entire pathways for structural homology. However, rapid computation of the reaction atom mappings remains elusive despite significant research. We present a novel substructure search algorithm, canonical labeling for clique approximation (CLCA), with polynomial run-time complexity to quickly generate atom maps for all the reactions present in MetRxn. CLCA uses number theory (i.e., prime factorization) to generate canonical labels or unique IDs and identify a bijection between the vertices (atoms) of two distinct molecular graphs. CLCA utilizes molecular graphs generated by combining atomistic information on reactions and metabolites from 112 metabolic models and 8 metabolic databases. CLCA offers improvements in run time, accuracy, and memory utilization over existing heuristic and combinatorial maximum common substructure (MCS) search algorithms. We provide detailed examples on the various advantages as well as failure modes of CLCA over existing algorithms.

Original languageEnglish (US)
Pages (from-to)3417-3438
Number of pages22
JournalJournal of Chemical Information and Modeling
Issue number12
StatePublished - Dec 22 2014

All Science Journal Classification (ASJC) codes

  • General Chemistry
  • General Chemical Engineering
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'CLCA: Maximum common molecular substructure queries within the MetRxn database'. Together they form a unique fingerprint.

Cite this