Atom mapping with constraint programming

Algorithms for Molecular Biology

Christoph Flamm¹  Peter F Stadler³  Rolf Backofen²  Norah Schnorr⁴  Feras Nahar⁴  Martin Mann⁴ 

[1]Institute for Theoretical Chemistry, University of Vienna, Währingerstrasse 17, Vienna 1090, Austria

[2]Center for non-coding RNA in Technology and Health, University of Copenhagen, Grønnegårdsvej 3, Frederiksberg 1870, Denmark

[3]Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe 87501, NM, USA

[4]Bioinformatics Group, Department of Computer Science, University of Freiburg, Georges-Koehler-Allee 106, Freiburg 79110, Germany

关键词: Imaginary transition state;    Chemical reaction;    Constraint programming;    Atom-atom mapping;   

Others  :  1083783
DOI  :  10.1186/s13015-014-0023-3

 received in 2014-04-17, accepted in 2014-10-30,  发布年份 2014

【 摘 要 】

Chemical reactions are rearrangements of chemical bonds. Each atom in an educt molecule thus appears again in a specific position of one of the reaction products. This bijection between educt and product atoms is not reported by chemical reaction databases, however, so that the “Atom Mapping Problem” of finding this bijection is left as an important computational task for many practical applications in computational chemistry and systems biology. Elementary chemical reactions feature a cyclic imaginary transition state (ITS) that imposes additional restrictions on the bijection between educt and product atoms that are not taken into account by previous approaches. We demonstrate that Constraint Programming is well-suited to solving the Atom Mapping Problem in this setting. The performance of our approach is evaluated for a manually curated subset of chemical reactions from the KEGG database featuring various ITS cycle layouts and reaction mechanisms.

【 授权许可】

   
2014 Mann et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

【 参考文献 】

• [1]Fujita S: Description of organic reactions based on imaginary transition structures. 1. Introduction of new concepts. J Chem Inf Comput Sci 1986, 26:205-212.
• [2]Hendrickson JB: Comprehensive system for classification and nomenclature of organic reactions. J Chem Inf Comput Sci 1997, 37:852-860.
• [3]Kotera M, Okuno Y, Hattori M, Goto S, Kanehisa M: Computational assignment of the EC numbers for genomic-scale analysis of enzymatic reactions. J Am Chem Soc 2004, 126(50):16487-16498.
• [4]Leber M, Egelhofer V, Schomburg I, Schomburg D: Automatic assignment of reaction operators to enzymatic reactions. Bioinformatics 2009, 25:3135-3142.
• [5]Yamanishi Y, Hattori M, Kotera M, Goto S, Kanehisa M: E-zyme: predicting potential EC numbers from the chemical transformation pattern of substrate-product pairs. Bioinformatics 2009, 25(12):179-186. doi:10.1093/bioinformatics/btp223
• [6]Arita M: Scale-freeness and biological networks. J Biochem 2005, 138:1-4. doi:10.1093/jb/mvi094
• [7]Blum T, Kohlbacher O: Using atom mapping rules for an improved detection of relevant routes in weighted metabolic networks. J Comput Biol 2008, 15:565-576.
• [8]Hogiri T, Furusawaa C, Shinfukua Y, Onoa N, Shimizua H: Analysis of metabolic network based on conservation of molecular structure. Biosystems 2009, 95(3):175-178. doi:10.1016/j.biosystems.2008.09.002
• [9]Rautio J, Kumpulainen H, Heimbach T, Oliyai R, Oh D, Järvinen T, Savolainen J: Prodrugs: design and clinical applications. Nat Rev Drug Discov 2008, 7(3):255-270.
• [10]Wiechert W: C13 metabolic flux analysis. Meta Eng 2001, 3:195-206. doi:10.1006/mben.2001.0187
• [11]Warr WA: A short review of chemical reaction database systems, computer-aided synthesis design, reaction prediction and synthetic feasibility. Mol Inform 2014, 33:469-476. doi:10.1002/minf.201400052
• [12]Chen WL, Chen DZ, Taylor KT: Automatic reaction mapping and reaction center detection. WIREs Comput Mol Sci 2013, 3(6):560-593. doi:10.1002/wcms.1140
• [13]Ehrlich H-C, Rarey M: Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review. WIREs Comput Mol Sci 2011, 1(1):68-79. doi:10.1002/wcms.5
• [14]Dugundji J, Ugi I: An algebraic model of constitutional chemistry as a basis for chemical computer programs. Topics Cur Chem 1973, 39:19-64.
• [15]Lynch M, Willett P: The automatic detection of chemical reaction sites. J Chem Inf Comput Sci 1978, 18:154-159.
• [16]Jochum C, Gasteiger J, Ugi I: The principle of minimum chemical distance (PMCD). Angew Chem Int Ed 1980, 19:495-505.
• [17]de Groot MJL, van Berlo RJP, van Winden WA, Verheijen PJT, Reinders MJT, de Ridder D: Metabolite and reaction inference based on enzyme specificities. Bioinformatics 2009, 25(22):2975-2983.
• [18]Hattori M, Okuno Y, Goto S, Kanehisa M: Heuristics for chemical compound matching. Genome Inform 2003, 14:144-153.
• [19]Heinonen M, Lappalainen S, Mielikäinen T, Rousu J: Computing atom mappings for biochemical reactions without subgraph isomorphism. J Comp Biol 2011, 18:43-58.
• [20]Raymond JW, Willett P: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J Computer-Aided Mol Design 2002, 16:521-533.
• [21]Apostolakis J, Sacher O, Körner R, Gasteiger J: Automatic determination of reaction mappings and reaction center information. 2. Validation on a biochemical reaction database. J Chem Inf Mod 2008, 48:1190-1198.
• [22]Körner R, Apostolakis J: Automatic determination of reaction mappings and reaction center information. 1. The imaginary transition state energy approach. J Chem Inf Mod 2008, 48:1181-1189.
• [23]Latendresse M, Malerich JP, Travers M, Karp PD: Accurate atom-mapping computation for biochemical reactions. J Chem Inf Model 2013, 52(11):2970-2982. doi:10.1021/ci3002217
• [24]Bahiense L, Manić G, Piva B, de Souza CC: The maximum common edge subgraph problem: a polyhedral investigation. Discr Appl Math 2012, 160:2523-2541.
• [25]Akutsu T: Efficient extraction of mapping rules of atoms from enzymatic reaction data. J Comp Biol 2004, 11:449-462. doi:10.1089/1066527041410337
• [26]Huang X, Lai J, Jennings SF: Maximum common subgraph: some upper bound and lower bound results. BMC Bioinformatics 2006, 7(S4):6. BioMed Central Full Text
• [27]Crabtree JD, Mehta DP: Automated reaction mapping. J Exp Algor 2009, 13(1.15):1-29. doi:10.1145/1412228.1498697
• [28]Crabtree JD, Mehta DP, Kouri TM: An open-source Java platform for automated reaction mapping. J Chem Inf Model 2010, 50:1751-1756. doi:10.1021/ci100061d
• [29]First EL, Gounaris CE, Floudas CA: Stereochemically consistent reaction mapping and identification of multiple reaction mechanisms through integer linear optimization. J Chem Inf Model 2012, 52(1):84-92. doi:10.1021/ci200351b
• [30]Herges R: Organizing principle of complex reactions and theory of coarctate transition states. Angewandte Chemie Int Ed 1994, 33:255-276.
• [31]Fujita S: Description of organic reactions based on imaginary transition structures. 2. Classification of one-string reactions having an even-membered cyclic reaction graph. J Chem Inf Comput Sci 1986, 26:212-223.
• [32]Fujita S: Description of organic reactions based on imaginary transition structures. 3. Classification of one-string reactions having an odd-membered cyclic reaction graph. J Chem Inf Comput Sci 1986, 26:224-230.
• [33]Mann M, Nahar F, Ekker H, Backofen R, Stadler PF, Flamm C: Atom mapping with constraint programming. In Proc. of the 19th International Conference on Principles and Practice of Constraint Programming (CP’13). LNCS, vol. 8124 . Edited by Schulte C. Springer, Berlin; 2013:805-822. doi:10.1007/978-3-642-40627-0_59
• [34]Muller C, Marcou G, Horvath D, Aires-de-Sousa J, Varnek A: Models for identification of erroneous atom-to-atom mapping of reactions performed by automated algorithms. J Chem Inf Mod 2012, 52(12):3116-3122. doi:10.1021/ci300418q
• [35][http://www.gecode.org] webcite Gecode Team: Gecode: Generic Constraint Development Environment. Available as an open-source library from [], 2014.
• [36]Regin J-C: A filtering algorithm for constraints of difference. In Proceedings of the 12th National Conference of the American Association for Artificial Intelligence . American Association for Artificial Intelligence, Menlo Park; 1994:362-367.
• [37]Meisenheimer J: Über eine eigenartige Umlagerung des Methyl-allyl-anilin-N-oxyds. Chemische Berichte 1919, 52:1667-1677.
• [38]Weininger D: SMILES:a chemical language and information system. 1 Introduction to methodology and encoding rules. J Chem Inf Comp Sci 1988, 28(1):31-36. doi:10.1021/ci00057a005
• [39]Mann M, Ekker H, Flamm C: The graph grammar library - a generic framework for chemical graph rewrite systems. [http://arxiv.org/abs/1304.1356] webciteIn Theory and Practice of Model Transformations, Proc. of ICMT 2013. LNCS, vol. 7909 Edited by Duddy K, Kappel G. Springer, Berlin; 2013, 52-53. doi:10.1007/978-3-642-38883-5_5. Extended abstract at, ICMT, long version at arXiv [http://arxiv.org/abs/1304.1356]
• [40]Cordella LP, Foggia P, Sansone C, Vento M: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans Pattern Anal Mach Intell 2004, 26(10):1367-1372.
• [41]Cordella LP, Foggia P, Sansone C, Vento M: Performance evaluation of the VF graph matching algorithm. In Proceedings of the 10th International Conference on Image Analysis and Processing. ICIAP ‘99 . IEEE Computer Society, Washington, DC; 1999:1172-1177.
• [42]Kanehisa M, Goto S, Sato Y, Furumichi M, Tanabe M: KEGG for integration and interpretation of large-scale molecular data sets. Nuc Acids Res 2012, 40(Database issue):109-114. doi:10.1093/nar/gkr988
• [43][http://arxiv.org/abs/0805.1030v1] webcite Zampelli S, Mann M, Deville Y, Backofen R: Techniques de decomposition pour l’isomorphisme de sous-graphe. In Proc. of the 4th Journees Francophones de Programmation Par Contraintes (JFPC’08); 2008. An english version of the article is available at [].
• [44]Dooms G, Deville Y, Dupont P: CP(Graph)Introducing a graph computation domain in constraint programming. In Principles and Practice of Constraint Programming - CP 2005. LNCS, vol. 3709 . Springer, Berlin; 2005:211-225.
• [45]Rudolf M: Utilizing constraint satisfaction techniques for efficient graph pattern matching. In Theory and Application of Graph Transformations. LNCS, vol 1764 . Springer, Berlin; 2000:381-394.
• [46]Zampelli S, Deville Y, Solnon C: Solving subgraph isomorphism problems with constraint programming. Constraints 2010, 15(3):327-353.
• [47]Solnon C: Alldifferent-based filtering for subgraph isomorphism. Artif Intell 2010, 174:850-864.
• [48]Eppstein D: Subgraph isomorphism in planar graphs and related problems. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ‘95 . Society for Industrial and Applied Mathematics, Philadelphia; 1995:632-640.
• [49]Gent IP, Jefferson C, Miguel I, Nightingale P: Data structures for generalised arc consistency for extensional constraints. In Proceedings of the Twenty Second Conference on Artificial Intelligence (AAAI-07), Vancouver, British Columbia, Canada . AAAI Press, Menlo Park; 2007:191-197.
• [50]Fujita S: Description of organic reactions based on imaginary transition structures. 5. Recombination of reaction strings in a synthesis space and its application to the description of synthetic pathways. J Chem Inf Comput Sci 1986, 26:238-242.