title: Efficient searching and annotation of metabolic networks using chemical similarity.
abstract: BACKGROUND
  The urgent need for efficient and sustainable biological production of fuels and high-value chemicals has elicited a wave of in silico techniques for identifying promising novel pathways to these compounds in large putative metabolic networks. To date, these approaches have primarily used general graph search algorithms, which are prohibitively slow as putative metabolic networks may exceed 1 million compounds. To alleviate this limitation, we report two methods--SimIndex (SI) and SimZyme--which use chemical similarity of 2D chemical fingerprints to efficiently navigate large metabolic networks and propose enzymatic connections between the constituent nodes. We also report a Byers-Waterman type pathway search algorithm for further paring down pertinent networks.
  
  
  RESULTS
  Benchmarking tests run with SI show it can reduce the number of nodes visited in searching a putative network by 100-fold with a computational time improvement of up to 10(5)-fold. Subsequent Byers-Waterman search application further reduces the number of nodes searched by up to 100-fold, while SimZyme demonstrates ∼ 90% accuracy in matching query substrates with enzymes. Using these modules, we have designed and annotated an alternative to the methylerythritol phosphate pathway to produce isopentenyl pyrophosphate with more favorable thermodynamics than the native pathway. These algorithms will have a significant impact on our ability to use large metabolic networks that lack annotation of promiscuous reactions.
  
  
  METHODS
  Python files will be available for download at http://tyolab.northwestern.edu/tools/.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Chemical and Biological Engineering, Northwestern University, Evanston, IL 60208, USA.
authors.forename: Dante A
authors.initials: DA
authors.lastname: Pertusi
authors.affiliation: Department of Chemical and Biological Engineering, Northwestern University, Evanston, IL 60208, USA.
authors.forename: Andrew E
authors.initials: AE
authors.lastname: Stine
authors.affiliation: Department of Chemical and Biological Engineering, Northwestern University, Evanston, IL 60208, USA.
authors.forename: Linda J
authors.initials: LJ
authors.lastname: Broadbelt
authors.affiliation: Department of Chemical and Biological Engineering, Northwestern University, Evanston, IL 60208, USA.
authors.forename: Keith E J
authors.initials: KE
authors.lastname: Tyo
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D062126:Databases, Chemical; D045782:Hemiterpenes / Q000378:metabolism*; D053858:Metabolic Networks and Pathways; D055432:Metabolomics / Q000379:methods*; D058977:Molecular Sequence Annotation; D009943:Organophosphorus Compounds / Q000378:metabolism*; D004364:Pharmaceutical Preparations / Q000737:chemistry*; D012984:Software
chemical_list: D045782:Hemiterpenes; D009943:Organophosphorus Compounds; D004364:Pharmaceutical Preparations; C004809:isopentenyl pyrophosphate