Mining Metabolic and Enzyme Databases for the Composition of Non-canonical Pathways

This project will develop and implement a set of algorithms for the discovery of complex metabolic pathways using information on metabolic pathways from different species available in databases such as KEGG and MetaCyc, and enzyme information available in databases such as BRENDA. The increasing availability of experimentally elucidated metabolic pathways together with the availability of enzyme functional data have ignited research in metabolic engineering and metabolomics. Recently, metabolic engineering has facilitated the production of complex pharmaceutical molecules by combining and manipulating metabolic pathways from multiple organisms. Metabolomic studies have revealed underlying causes of complex diseases and have helped diagnostic, prognostic, and treatment regimens as these evolve toward more individualized protocols. These spectacular advances have mostly relied upon laborious manual processes that are infeasible as more and more metabolic data are generated. The ability of the algorithms that will developed herein to discover known pathways will be investigated thoroughly and will include wetlab experimentation with two model studies. The studies involve niacin and shikonin, two therapeutic agents. Computational and wetlab experimentation will be conducted in parallel, with the computation feeding the experiment and the experiment providing valuable feedback for the tuning of the parameters of the corresponding algorithms. A web server will be built to facilitate the use of our tools and to widely disseminate our work in the scientific community. The research is timely and directed toward an important area of broad scientific interest with implications extending to fields such as health and energy. The project will provide training opportunities for graduate and undergraduate students. Participation in this type of research will provide graduate students with interdisciplinary training in metabolic engineering, metabolomics, systems biology, biochemistry, and molecular biology, as well as in mathematical modeling, algorithms, and computer science. The project will provide training opportunities and mentoring for women and minority graduate, undergraduate, and high school students.

This work has been supported by grant NSF ABI 1262491.

Related Publications

1. S. M. Kim, M. I. Peña, M. Moll, G. N. Bennett, and L. E. Kavraki, “Improving the organization and interactivity of metabolic pathfinding with precomputed pathways,” BMC Bioinformatics, vol. 21, no. 1, p. 13, Jan. 2020. PMID: 31924164, PMCID: PMC6954563
   
   pdf publisher bibtex abstract details

   BibTeX

   ×

   @article{kim2020improving-the-organization-and-interactivity-of-metabolic,
     title = {Improving the organization and interactivity of metabolic pathfinding with precomputed
         pathways},
     author = {Kim, Sarah M. and Pe{\~n}a, Matthew I. and Moll, Mark and Bennett, George N. and Kavraki, Lydia E.},
     journal = {BMC Bioinformatics},
     month = jan,
     year = {2020},
     volume = {21},
     pages = {13},
     doi = {10.1186/s12859-019-3328-x},
     abstract = {Background: The rapid growth of available knowledge on metabolic processes across
         thousands of species continues to expand the possibilities of producing chemicals by
         combining pathways found in different species. Several computational search algorithms have
         been developed for automating the identification of possible heterologous pathways; however,
         these searches may return thousands of pathway results. Although the large number of results
         are in part due to the large number of possible compounds and reactions, a subset of core
         reaction modules is repeatedly observed in pathway results across multiple searches,
         suggesting that some subpaths between common compounds were more consistently explored than
         others.
         
         To reduce the resources spent on searching the same metabolic space, a new meta-algorithm
         for metabolic pathfinding, Hub Pathway search with Atom Tracking (HPAT), was developed to
         take advantage of a precomputed network of subpath modules. To investigate the efficacy of
         this method, we created a table describing a network of common hub metabolites and how they
         are biochemically connected and only offloaded searches to and from this hub network onto an
         interactive webserver capable of visualizing the resulting pathways.
         
         Results: A test set of nineteen known pathways taken from literature and metabolic databases
         were used to evaluate if HPAT was capable of identifying known pathways. HPAT found the
         exact pathway for eleven of the nineteen test cases using a diverse set of precomputed
         subpaths, whereas a comparable pathfinding search algorithm that does not use precomputed
         subpaths found only seven of the nineteen test cases. The capability of HPAT to find novel
         pathways was demonstrated by its ability to identify novel 3-hydroxypropanoate (3-HP)
         synthesis pathways. As for pathway visualization, the new interactive pathway filters enable
         a reduction of the number of displayed pathways from hundreds down to less than ten pathways
         in several test cases, illustrating their utility in reducing the amount of presented
         information while retaining pathways of interest.
         
         Conclusions: This work presents the first step in incorporating a precomputed subpath
         network into metabolic pathfinding and demonstrates how this leads to a concise, interactive
         visualization of pathway results. The modular nature of metabolic pathways is exploited to
         facilitate efficient discovery of alternate pathways.},
     issue = {1},
     keyword = {metabolic pathfinding; precomputation; atom mapping; graph search},
     note = {PMID: 31924164, PMCID: PMC6954563}
   }
   

   Abstract

   ×

   Background: The rapid growth of available knowledge on metabolic processes across thousands of species continues to expand the possibilities of producing chemicals by combining pathways found in different species. Several computational search algorithms have been developed for automating the identification of possible heterologous pathways; however, these searches may return thousands of pathway results. Although the large number of results are in part due to the large number of possible compounds and reactions, a subset of core reaction modules is repeatedly observed in pathway results across multiple searches, suggesting that some subpaths between common compounds were more consistently explored than others. To reduce the resources spent on searching the same metabolic space, a new meta-algorithm for metabolic pathfinding, Hub Pathway search with Atom Tracking (HPAT), was developed to take advantage of a precomputed network of subpath modules. To investigate the efficacy of this method, we created a table describing a network of common hub metabolites and how they are biochemically connected and only offloaded searches to and from this hub network onto an interactive webserver capable of visualizing the resulting pathways. Results: A test set of nineteen known pathways taken from literature and metabolic databases were used to evaluate if HPAT was capable of identifying known pathways. HPAT found the exact pathway for eleven of the nineteen test cases using a diverse set of precomputed subpaths, whereas a comparable pathfinding search algorithm that does not use precomputed subpaths found only seven of the nineteen test cases. The capability of HPAT to find novel pathways was demonstrated by its ability to identify novel 3-hydroxypropanoate (3-HP) synthesis pathways. As for pathway visualization, the new interactive pathway filters enable a reduction of the number of displayed pathways from hundreds down to less than ten pathways in several test cases, illustrating their utility in reducing the amount of presented information while retaining pathways of interest. Conclusions: This work presents the first step in incorporating a precomputed subpath network into metabolic pathfinding and demonstrates how this leads to a concise, interactive visualization of pathway results. The modular nature of metabolic pathways is exploited to facilitate efficient discovery of alternate pathways.
   Details
2. E. E. Litsa, M. I. Pena, M. Moll, G. Giannakopoulos, G. N. Bennett, and L. E. Kavraki, “Machine Learning Guided Atom Mapping of Metabolic Reactions,” Journal of Chemical Information and Modeling, vol. 59, no. 3, pp. 1121–1135, 2019. PMID: 30500191
   
   pdf publisher bibtex abstract details

   BibTeX

   ×

   @article{litsa2019atom-mapping,
     title = {Machine Learning Guided Atom Mapping of Metabolic Reactions},
     author = {Litsa, Eleni E. and Pena, Matthew I. and Moll, Mark and Giannakopoulos, George and Bennett, George N. and Kavraki, Lydia E.},
     journal = {Journal of Chemical Information and Modeling},
     year = {2019},
     volume = {59},
     number = {3},
     pages = {1121--1135},
     doi = {10.1021/acs.jcim.8b00434},
     abstract = {Atom mapping of a chemical reaction is a mapping between the atoms in the reactant
         molecules and the atoms in the product molecules. It encodes the underlying reaction
         mechanism and, as such, constitutes essential information in computational studies in
         metabolic engineering. Various techniques have been investigated for the automatic
         computation of the atom mapping of a chemical reaction, approaching the problem as a graph
         matching problem. The graph abstraction of the chemical problem, though, eliminates crucial
         chemical information. There have been efforts for enhancing the graph representation by
         introducing the bond stabilities as edge weights, as they are estimated based on
         experimental evidence. Here, we present a fully automated optimization-based approach, named
         AMLGAM, (Automated Machine Learning Guided Atom Mapping), that uses machine learning
         techniques for the estimation of the bond stabilities based on the chemical environment of
         each bond. The optimization method finds the reaction mechanism which favors the
         breakage/formation of the less stable bonds. We evaluated our method on a manually curated
         data set of 382 chemical reactions and ran our method on a much larger and diverse data set
         of 7400 chemical reactions. We show that the proposed method improves the accuracy over
         existing techniques based on results published by earlier studies on a common data set and
         is capable of handling unbalanced reactions.},
     keyword = {metabolic networks},
     note = {PMID: 30500191}
   }
   

   Abstract

   ×

   Atom mapping of a chemical reaction is a mapping between the atoms in the reactant molecules and the atoms in the product molecules. It encodes the underlying reaction mechanism and, as such, constitutes essential information in computational studies in metabolic engineering. Various techniques have been investigated for the automatic computation of the atom mapping of a chemical reaction, approaching the problem as a graph matching problem. The graph abstraction of the chemical problem, though, eliminates crucial chemical information. There have been efforts for enhancing the graph representation by introducing the bond stabilities as edge weights, as they are estimated based on experimental evidence. Here, we present a fully automated optimization-based approach, named AMLGAM, (Automated Machine Learning Guided Atom Mapping), that uses machine learning techniques for the estimation of the bond stabilities based on the chemical environment of each bond. The optimization method finds the reaction mechanism which favors the breakage/formation of the less stable bonds. We evaluated our method on a manually curated data set of 382 chemical reactions and ran our method on a much larger and diverse data set of 7400 chemical reactions. We show that the proposed method improves the accuracy over existing techniques based on results published by earlier studies on a common data set and is capable of handling unbalanced reactions.
   Details
3. S. M. Kim, M. I. Peña, M. Moll, G. N. Bennett, and L. E. Kavraki, “A Review of Parameters and Heuristics for Guiding Metabolic Pathfinding,” Journal of Cheminformatics, vol. 9, no. 1, p. 51, Sep. 2017. PMCID: PMC5602787, PMID: 29086092
   
   pdf publisher bibtex abstract details

   BibTeX

   ×

   @article{kim2017_pathfinding_review,
     title = {A Review of Parameters and Heuristics for Guiding Metabolic Pathfinding},
     author = {Kim, Sarah M. and Pe\~{n}a, Matthew I. and Moll, Mark and Bennett, George N. and Kavraki, Lydia E.},
     journal = {Journal of Cheminformatics},
     month = sep,
     year = {2017},
     volume = {9},
     number = {1},
     pages = {51},
     doi = {10.1186/s13321-017-0239-6},
     abstract = {Recent developments in metabolic engineering have led to the successful biosynthesis
         of valuable products, such as the precursor of the antimalarial compound, artemisinin, and
         opioid precursor, thebaine. Synthesizing these traditionally plant-derived compounds in
         genetically modified yeast cells introduces the possibility of significantly reducing the
         total time and resources required for their production, and in turn, allows these valuable
         compounds to become cheaper and more readily available. Most biosynthesis pathways used in
         metabolic engineering applications have been discovered manually, requiring a tedious search
         of existing literature and metabolic databases. However, the recent rapid development of
         available metabolic information has enabled the development of automated approaches for
         identifying novel pathways. Computer-assisted pathfinding has the potential to save
         biochemists time in the initial discovery steps of metabolic engineering. In this paper, we
         review the parameters and heuristics used to guide the search in recent pathfinding
         algorithms. These parameters and heuristics capture information on the metabolic network
         structure, compound structures, reaction features, and organism-specificity of pathways. No
         one metabolic pathfinding algorithm or search parameter stands out as the best to use
         broadly for solving the pathfinding problem, as each method and parameter has its own
         strengths and shortcomings. As assisted pathfinding approaches continue to become more
         sophisticated, the development of better methods for visualizing pathway results and
         integrating these results into existing metabolic engineering practices is also important
         for encouraging wider use of these pathfinding methods.},
     keyword = {metabolic networks},
     note = {PMCID: PMC5602787, PMID: 29086092}
   }
   

   Abstract

   ×

   Recent developments in metabolic engineering have led to the successful biosynthesis of valuable products, such as the precursor of the antimalarial compound, artemisinin, and opioid precursor, thebaine. Synthesizing these traditionally plant-derived compounds in genetically modified yeast cells introduces the possibility of significantly reducing the total time and resources required for their production, and in turn, allows these valuable compounds to become cheaper and more readily available. Most biosynthesis pathways used in metabolic engineering applications have been discovered manually, requiring a tedious search of existing literature and metabolic databases. However, the recent rapid development of available metabolic information has enabled the development of automated approaches for identifying novel pathways. Computer-assisted pathfinding has the potential to save biochemists time in the initial discovery steps of metabolic engineering. In this paper, we review the parameters and heuristics used to guide the search in recent pathfinding algorithms. These parameters and heuristics capture information on the metabolic network structure, compound structures, reaction features, and organism-specificity of pathways. No one metabolic pathfinding algorithm or search parameter stands out as the best to use broadly for solving the pathfinding problem, as each method and parameter has its own strengths and shortcomings. As assisted pathfinding approaches continue to become more sophisticated, the development of better methods for visualizing pathway results and integrating these results into existing metabolic engineering practices is also important for encouraging wider use of these pathfinding methods.
   Details
4. S. M. Kim, M. I. Peña, M. Moll, G. Giannakopoulos, G. N. Bennett, and L. E. Kavraki, “An Evaluation of Different Clustering Methods and Distance Measures Used for Grouping Metabolic Pathways,” in 2016 International Conference on Bioinformatics and Computational Biology. ISCA, 2016, pp. 115–122.
   
   pdf publisher bibtex abstract details

   BibTeX

   ×

   @inproceedings{kim-pena2016an-evaluation-of-different-clustering-methods,
     title = {An Evaluation of Different Clustering Methods and Distance Measures Used for Grouping
         Metabolic Pathways},
     author = {Kim, Sarah M. and Pe{\~n}a, Matthew I. and Moll, Mark and Giannakopoulos, George and Bennett, George N. and Kavraki, Lydia E.},
     booktitle = {2016 International Conference on Bioinformatics and Computational Biology. ISCA},
     year = {2016},
     pages = {115--122},
     abstract = {Large-scale annotated metabolic databases, such as KEGG and MetaCyc, provide a
         wealth of information to researchers designing novel biosynthetic pathways. However, many
         metabolic pathfinding tools that assist in identifying possible solution pathways fail to
         facilitate the grouping and interpretation of these pathway results. Clustering possible
         solution pathways can help users of pathfinding tools quickly identify major patterns and
         unique pathways without having to sift through individual results one by one. In this paper,
         we assess the ability of three separate clustering methods (hierarchical, k -means, and k
         -medoids) along with three pair-wise distance measures (Levenshtein, Jaccard, and n -gram)
         to expertly group lysine, isoleucine, and 3-hydroxypropanoic acid (3-HP) biosynthesis
         pathways. The quality of the resulting clusters were quantitatively evaluated against
         expected pathway groupings taken from the literature. Hierarchical clustering and
         Levenshtein distance seemed to best match external pathway labels across the three
         biosynthesis pathways. The lysine biosynthesis pathways, which had the most distinct
         separation of pathways, had better quality clusters than isoleucine and 3-HP, suggesting
         that grouping pathways with more complex underlying topologies may require more tailored
         clustering methods.},
     keyword = {metabolic networks}
   }
   

   Abstract

   ×

   Large-scale annotated metabolic databases, such as KEGG and MetaCyc, provide a wealth of information to researchers designing novel biosynthetic pathways. However, many metabolic pathfinding tools that assist in identifying possible solution pathways fail to facilitate the grouping and interpretation of these pathway results. Clustering possible solution pathways can help users of pathfinding tools quickly identify major patterns and unique pathways without having to sift through individual results one by one. In this paper, we assess the ability of three separate clustering methods (hierarchical, k -means, and k -medoids) along with three pair-wise distance measures (Levenshtein, Jaccard, and n -gram) to expertly group lysine, isoleucine, and 3-hydroxypropanoic acid (3-HP) biosynthesis pathways. The quality of the resulting clusters were quantitatively evaluated against expected pathway groupings taken from the literature. Hierarchical clustering and Levenshtein distance seemed to best match external pathway labels across the three biosynthesis pathways. The lysine biosynthesis pathways, which had the most distinct separation of pathways, had better quality clusters than isoleucine and 3-HP, suggesting that grouping pathways with more complex underlying topologies may require more tailored clustering methods.
   Details
5. D. A. Antunes, D. Devaurs, and L. E. Kavraki, “Understanding the challenges of protein flexibility in drug design,” Expert Opinion on Drug Discovery, vol. 10, no. 12, pp. 1301–1313, 2015. PMID: 26414598
   
   pdf publisher bibtex abstract details

   BibTeX

   ×

   @article{antunes-15-eodd,
     title = {Understanding the challenges of protein flexibility in drug design},
     author = {Antunes, Dinler A. and Devaurs, Didier and Kavraki, Lydia E.},
     journal = {Expert Opinion on Drug Discovery},
     year = {2015},
     volume = {10},
     number = {12},
     pages = {1301--1313},
     doi = {10.1517/17460441.2015.1094458},
     abstract = {Protein-ligand interactions play key roles in various metabolic pathways, and the
         proteins involved in these interactions represent major targets for drug discovery.
         Molecular docking is widely used to predict the structure of protein-ligand complexes, and
         protein flexibility stands out as one of the most important and challenging issues for
         binding mode prediction. Various docking methods accounting for protein flexibility have
         been proposed, tackling problems of ever-increasing dimensionality. This paper presents an
         overview of conformational sampling methods treating target flexibility during molecular
         docking. Special attention is given to approaches considering full protein flexibility.
         Contrary to what is frequently done, this review does not rely on classical biomolecular
         recognition models to classify existing docking methods. Instead, it applies algorithmic
         considerations, focusing on the level of flexibility accounted for. This review also
         discusses the diversity of docking applications, from virtual screening of small drug-like
         compounds to geometry prediction of protein-peptide complexes. Considering the diversity of
         docking methods presented here, deciding which one is the best at treating protein
         flexibility depends on the system under study and the research application. In virtual
         screening experiments, ensemble docking can be used to implicitly account for large-scale
         conformational changes, and selective docking can additionally consider local binding-site
         rearrangements. In other cases, on-the-fly exploration of the whole protein-ligand complex
         might be needed for accurate geometry prediction of the binding mode. Among other things,
         future methods are expected to provide alternative binding modes, which will better reflect
         the dynamic nature of protein-ligand interactions.},
     keyword = {proteins and drugs},
     note = {PMID: 26414598}
   }
   

   Abstract

   ×

   Protein-ligand interactions play key roles in various metabolic pathways, and the proteins involved in these interactions represent major targets for drug discovery. Molecular docking is widely used to predict the structure of protein-ligand complexes, and protein flexibility stands out as one of the most important and challenging issues for binding mode prediction. Various docking methods accounting for protein flexibility have been proposed, tackling problems of ever-increasing dimensionality. This paper presents an overview of conformational sampling methods treating target flexibility during molecular docking. Special attention is given to approaches considering full protein flexibility. Contrary to what is frequently done, this review does not rely on classical biomolecular recognition models to classify existing docking methods. Instead, it applies algorithmic considerations, focusing on the level of flexibility accounted for. This review also discusses the diversity of docking applications, from virtual screening of small drug-like compounds to geometry prediction of protein-peptide complexes. Considering the diversity of docking methods presented here, deciding which one is the best at treating protein flexibility depends on the system under study and the research application. In virtual screening experiments, ensemble docking can be used to implicitly account for large-scale conformational changes, and selective docking can additionally consider local binding-site rearrangements. In other cases, on-the-fly exploration of the whole protein-ligand complex might be needed for accurate geometry prediction of the binding mode. Among other things, future methods are expected to provide alternative binding modes, which will better reflect the dynamic nature of protein-ligand interactions.
   Details