{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T04:22:20Z","timestamp":1747196540326,"version":"3.40.5"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T00:00:00Z","timestamp":1747094400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T00:00:00Z","timestamp":1747094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100011958","name":"Danmarks Frie Forskningsfond","doi-asserted-by":"publisher","award":["DFF-0135-00018B"],"award-info":[{"award-number":["DFF-0135-00018B"]}],"id":[{"id":"10.13039\/501100011958","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cheminform"],"abstract":"<jats:sec>\n            <jats:title>Abstract<\/jats:title>\n            <jats:p>Chemical synthesis planning has considerably benefited from advances in the field of machine learning. Neural networks can reliably and accurately predict reactions leading to a given, possibly complex, molecule. In this work we focus on algorithms for assembling such predictions to a full synthesis plan that, starting from simple building blocks, produces a given target molecule, a procedure known as retrosynthesis. Objective functions for this task are hard to define and context-specific. In order to generate a diverse set of synthesis plans for chemists to select from, we capture the concept of diversity in a novel chemical diversity score (CDS). Our experiments show that our algorithm outperforms the algorithm predominantly employed in this domain, Monte-Carlo Tree Search, with respect to diversity in terms of our score as well as time efficiency.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Scientific Contribution:<\/jats:title>\n            <jats:p>We adapt Depth-First Proof-Number Search (DFPN) (Please refer to <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"https:\/\/github.com\/Bayer-Group\/bayer-retrosynthesis-search\" ext-link-type=\"uri\">https:\/\/github.com\/Bayer-Group\/bayer-retrosynthesis-search<\/jats:ext-link> for the accompanying source code.) and its variants, which have been applied to retrosynthesis before, to produce a set of solutions, with an explicit focus on diversity. We also make progress on understanding DFPN in terms of completeness, i.e., the ability to find a solution whenever there exists one. DFPN is known to be incomplete, for which we provide a much cleaner example, but we also show that it is complete when reinforced with a threshold-controlling routine from the literature.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/s13321-025-00981-x","type":"journal-article","created":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:54:11Z","timestamp":1747162451000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Generating diversity and securing completeness in algorithmic retrosynthesis"],"prefix":"10.1186","volume":"17","author":[{"given":"Florian","family":"Mrugalla","sequence":"first","affiliation":[]},{"given":"Christopher","family":"Franz","sequence":"additional","affiliation":[]},{"given":"Yannic","family":"Alber","sequence":"additional","affiliation":[]},{"given":"Georg","family":"Mogk","sequence":"additional","affiliation":[]},{"given":"Mart\u00edn","family":"Villalba","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Mrziglod","sequence":"additional","affiliation":[]},{"given":"Kevin","family":"Schewior","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,13]]},"reference":[{"issue":"4698","key":"981_CR1","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1126\/science.3838594","volume":"228","author":"EJ Corey","year":"1985","unstructured":"Corey EJ, Long AK, Rubenstein SD (1985) Computer-assisted analysis in organic synthesis. Science 228(4698):408\u2013418","journal-title":"Science"},{"issue":"1","key":"981_CR2","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1351\/pac196714010019","volume":"14","author":"EJ Corey","year":"1967","unstructured":"Corey EJ (1967) General methods for the construction of complex molecules. Pure Appl Chem 14(1):19\u201338","journal-title":"Pure Appl Chem"},{"issue":"3902","key":"981_CR3","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1126\/science.166.3902.178","volume":"166","author":"EJ Corey","year":"1969","unstructured":"Corey EJ, Wipke WT (1969) Computer-assisted design of complex organic syntheses: pathways for molecular synthesis can be devised with a computer and equipment for graphical communication. Science 166(3902):178\u2013192","journal-title":"Science"},{"key":"981_CR4","unstructured":"Chen B, Li C, Dai H, Song L. Retro* (2020) Learning retrosynthetic planning with neural guided A* search. In International Conference on Machine Learning (ICML), 1608\u20131616"},{"issue":"12","key":"981_CR5","doi-asserted-by":"publisher","first-page":"1237","DOI":"10.1021\/acscentsci.7b00355","volume":"3","author":"CW Coley","year":"2017","unstructured":"Coley CW, Rogers L, Green WH, Jensen KF (2017) Computer-assisted retrosynthesis based on molecular similarity. ACS Cent Sci 3(12):1237\u20131245","journal-title":"ACS Cent Sci"},{"issue":"1","key":"981_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13321-020-00472-1","volume":"12","author":"Samuel Genheden","year":"2020","unstructured":"Genheden Samuel, Thakkar Amol, Chadimov\u00e1 Veronika, Reymond Jean-Louis, Engkvist Ola, Bjerrum Esben (2020) Aizynthfinder: a fast, robust and flexible open-source software for retrosynthetic planning. J Cheminform 12(1):1\u20139","journal-title":"J Cheminform"},{"issue":"16","key":"981_CR7","doi-asserted-by":"publisher","first-page":"8667","DOI":"10.1021\/acs.jmedchem.9b02120","volume":"63","author":"TJ Struble","year":"2020","unstructured":"...Struble TJ, Alvarez JC, Brown SP, Chytil M, Cisar J, DesJarlais RL, Engkvist O, Frank SA, Greve DR, Griffin DJ, Hou X, Johannes JW, Kreatsoulas C, Lahue B, Mathea M, Mogk G, Nicolaou CA, Palmer AD, Price DJ, Robinson RI, Salentin S, Xing L, Jaakkola T, Green WH, Barzilay R, Coley CW, Jensen KF (2020) Current and future roles of artificial intelligence in medicinal chemistry synthesis. J Med Chem 63(16):8667\u20138682","journal-title":"J Med Chem"},{"key":"981_CR8","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1186\/s13321-020-00452-5","volume":"12","author":"R Shibukawa","year":"2020","unstructured":"Shibukawa R, Ishida S, Yoshizoe K, Wasa K, Takasu K, Okuno Y, Terayama K, Tsuda K (2020) CompRet: a comprehensive recommendation framework for chemical synthesis planning with algorithmic enumeration. J Cheminform 12:52","journal-title":"J Cheminform"},{"issue":"7698","key":"981_CR9","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1038\/nature25978","volume":"555","author":"MHS Segler","year":"2018","unstructured":"Segler MHS, Preuss M, Waller MP (2018) Planning chemical syntheses with deep neural networks and symbolic AI. Nature 555(7698):604\u2013610","journal-title":"Nature"},{"issue":"12","key":"981_CR10","doi-asserted-by":"publisher","first-page":"3316","DOI":"10.1039\/C9SC05704H","volume":"11","author":"P Schwaller","year":"2020","unstructured":"Schwaller P, Petraglia R, Zullo V, Nair VH, Haeuselmann RA, Pisoni R, Bekas C, Iuliano A, Laino T (2020) Predicting retrosynthetic pathways using transformer-based models and a hyper-graph exploration strategy. Chem Sci 11(12):3316\u20133325","journal-title":"Chem Sci"},{"issue":"1","key":"981_CR11","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1039\/C9SC04944D","volume":"11","author":"A Thakkar","year":"2020","unstructured":"Thakkar A, Kogej T, Reymond J-L, Engkvist O, Bjerrum EJ (2020) Datasets and their influence on the development of computer assisted synthesis planning tools in the pharmaceutical domain. Chem Sci 11(1):154\u2013168","journal-title":"Chem Sci"},{"issue":"9","key":"981_CR12","doi-asserted-by":"publisher","first-page":"1572","DOI":"10.1021\/acscentsci.9b00576","volume":"5","author":"P Schwaller","year":"2019","unstructured":"Schwaller P, Laino T, Gaudin T, Bolgar P, Hunter CA, Bekas C, Lee AA (2019) Molecular transformer: a model for uncertainty-calibrated chemical reaction prediction. ACS Cent Sci 5(9):1572\u20131583","journal-title":"ACS Cent Sci"},{"issue":"3","key":"981_CR13","doi-asserted-by":"publisher","first-page":"992","DOI":"10.1021\/jacsau.3c00737","volume":"4","author":"L Yao","year":"2024","unstructured":"Yao L, Guo W, Wang Z, Xiang S, Liu W, Ke G (2024) Node-aligned graph-to-graph: elevating template-free deep learning approaches in single-step retrosynthesis. JACS Au 4(3):992\u20131003","journal-title":"JACS Au"},{"issue":"1","key":"981_CR14","doi-asserted-by":"publisher","first-page":"e18244","DOI":"10.1002\/aic.18244","volume":"70","author":"K Zhang","year":"2024","unstructured":"Zhang K, Mann V, Venkatasubramanian V (2024) G-matt: single-step retrosynthesis prediction using molecular grammar tree transformer. AIChE J 70(1):e18244","journal-title":"AIChE J"},{"key":"981_CR15","doi-asserted-by":"crossref","unstructured":"Heifets A, Jurisica I (2012) Construction of new medicines via game proof search. In AAAI Conference on Artificial Intelligence (AAAI), 1564\u20131570","DOI":"10.1609\/aaai.v26i1.8331"},{"key":"981_CR16","unstructured":"Kishimoto A, Buesser B, Chen B, Botea A (2019) Depth-first proof-number search with heuristic edge cost and application to chemical synthesis planning. In Advances in Neural Information Processing Systems (NeurIPS), 7224\u20137234"},{"issue":"1","key":"981_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TCIAIG.2012.2186810","volume":"4","author":"Cameron Browne","year":"2012","unstructured":"Browne Cameron, Powley Edward Jack, Lucas Simon M, Cowling Peter I, Rohlfshagen Philipp, Tavener Stephen, Liebana Diego Perez, Samothrakis Spyridon, Colton Simon (2012) A survey of monte carlo tree search methods. IEEE Trans Comput Intell AI Games 4(1):1\u201343","journal-title":"IEEE Trans Comput Intell AI Games"},{"key":"981_CR18","unstructured":"Nagai A (2002) Df-pn algorithm for searching AND\/OR trees and its applications. PhD thesis, Department of Information Science, University of Tokyo"},{"key":"981_CR19","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-0-387-35706-5_9","volume-title":"Advances in computer games (ACG)","author":"A Kishimoto","year":"2004","unstructured":"Kishimoto A, M\u00fcller M (2004) Df-pn in go: an application to the one-eye problem. In: Herik HJ, Iida H, Heinz EA (eds) Advances in computer games (ACG). Springer, Boston, pp 125\u2013141"},{"key":"981_CR20","unstructured":"Schaeffer J, Bj\u00f6rnsson Y, Burch N, Kishimoto A, M\u00fcller M, Lake R, Lu P, Sutphen S (2005) Solving checkers. In International Joint Conference on Artificial Intelligence (IJCAI). 292\u2013297"},{"issue":"1","key":"981_CR21","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0004-3702(94)90004-3","volume":"66","author":"LV Allis","year":"1994","unstructured":"Allis LV, van der Meulen Maarten, Jaap van den Herik H (1994) Proof-number search. Artif Intell 66(1):91\u2013124","journal-title":"Artif Intell"},{"key":"981_CR22","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-540-87608-3_14","volume-title":"Computers and games","author":"A Kishimoto","year":"2008","unstructured":"Kishimoto A, M\u00fcller M (2008) About the completeness of depth-first proof-number search. In: van den Herik HJ, Xu X, Ma Z, Winands MHM (eds) Computers and games. Springer, Berlin, pp 146\u2013156"},{"key":"981_CR23","unstructured":"Kishimoto A (2005) Correct and efficient search algorithms in the presence of repetitions. PhD thesis, Department of Computing Science, University of Alberta"},{"key":"981_CR24","doi-asserted-by":"crossref","unstructured":"Kishimoto A (2010) Dealing with infinite loops, underestimation, and overestimation of depth-first proof-number search. In AAAI Conference on Artificial Intelligence (AAAI). 108\u2013113","DOI":"10.1609\/aaai.v24i1.7534"},{"key":"981_CR25","doi-asserted-by":"publisher","first-page":"4640","DOI":"10.1039\/C8SC05611K","volume":"10","author":"Tomasz Badowski","year":"2019","unstructured":"Badowski Tomasz, Molga Karol, Grzybowski Bartosz A (2019) Selection of cost-effective yet chemically diverse pathways from the networks of computer-generated retrosynthetic plans. Chem Sci 10:4640\u20134651","journal-title":"Chem Sci"},{"key":"981_CR26","doi-asserted-by":"publisher","first-page":"1469","DOI":"10.1039\/D0SC05078D","volume":"12","author":"Y Mo","year":"2021","unstructured":"Mo Y, Guan Y, Verma P, Guo J, Fortunato ME, Zhaohong L, Coley CW, Jensen KF (2021) Evaluating and clustering retrosynthesis pathways with learned strategy. Chem Sci 12:1469\u20131478","journal-title":"Chem Sci"},{"key":"981_CR27","unstructured":"Xie Y, Xu Z, Ma J, Mei Q (2023) How much space has been explored? measuring the chemical space covered by databases and machine-generated molecules"},{"issue":"8","key":"981_CR28","doi-asserted-by":"publisher","first-page":"3899","DOI":"10.1021\/acs.jcim.1c00232","volume":"61","author":"Samuel Genheden","year":"2021","unstructured":"Genheden Samuel, Engkvist Ola, Bjerrum Esben (2021) Clustering of synthetic routes using tree edit distance. J Chem Inf Model 61(8):3899\u20133907","journal-title":"J Chem Inf Model"},{"issue":"1","key":"981_CR29","doi-asserted-by":"publisher","first-page":"015018","DOI":"10.1088\/2632-2153\/ac4a91","volume":"3","author":"Samuel Genheden","year":"2022","unstructured":"Genheden Samuel, Engkvist Ola, Bjerrum Esben (2022) Fast prediction of distances between synthetic routes with deep learning. Mach Learn Sci Technol 3(1):015018","journal-title":"Mach Learn Sci Technol"},{"key":"981_CR30","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1039\/D2DD00015F","volume":"1","author":"Samuel Genheden and Esben Bjerrum","year":"2022","unstructured":"Samuel Genheden and Esben Bjerrum (2022) Paroutes: towards a framework for benchmarking retrosynthesis route predictions. Digit Discov 1:527\u2013539","journal-title":"Digit Discov"},{"key":"981_CR31","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1039\/D4FD00093E","volume":"256","author":"K Maziarz","year":"2025","unstructured":"Maziarz K, Tripp A, Liu G, Stanley M, Xie S, Gai\u0144ski P, Seidl P, Segler MHS (2025) Re-evaluating retrosynthesis algorithms with syntheseus. Faraday Discuss 256:568\u2013586","journal-title":"Faraday Discuss"},{"key":"981_CR32","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1039\/D2DD00110A","volume":"2","author":"A Toniato","year":"2023","unstructured":"Toniato A, Vaucher AC, Schwaller P, Laino T (2023) Enhancing diversity in language based models for single-step retrosynthesis. Digit Discov 2:489\u2013501","journal-title":"Digit Discov"},{"key":"981_CR33","doi-asserted-by":"publisher","first-page":"2457","DOI":"10.1021\/cr00039a007","volume":"95","author":"A Suzuki","year":"1995","unstructured":"Suzuki A, Miyaura N (1995) Palladium-catalyzed cross-coupling reactions of organoboron compounds. Chem Rev 95:2457\u20132483","journal-title":"Chem Rev"},{"key":"981_CR34","unstructured":"MLPDS (2020) Askcos: Software tools for organic synthesis. https:\/\/askcos.mit.edu\/. Accessed 23 Nov 2021"},{"key":"981_CR35","unstructured":"Tripp A, Maziarz K, Lewis S, Segler M, Hern\u00e1ndez-Lobato JM (2024) Retro-fallback: retrosynthetic planning in an uncertain world. In The Twelfth International Conference on Learning Representations"},{"key":"981_CR36","unstructured":"Gao C (2021) On computation complexity of true proof number search. arXiv\/cs.CC, arXiv: abs\/2102.04907"},{"key":"981_CR37","unstructured":"Palay AJ (1983) Searching with probabilities. PhD thesis, Department of Computer Science, Carnegie Mellon University"},{"key":"981_CR38","unstructured":"Kishimoto A, M\u00fcller M (2004). A general solution to the graph history interaction problem. In AAAI Conference on Artificial Intelligence (AAAI). 644\u2013649"},{"issue":"1","key":"981_CR39","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1186\/s13321-020-00472-1","volume":"12","author":"S Genheden","year":"2020","unstructured":"Genheden S, Thakkar A, Chadimov\u00e1 V, Reymond J-L, Engkvist O, Bjerrum E (2020) AiZynthFinder: a fast, robust and flexible open-source software for retrosynthetic planning. J Cheminform 12(1):70","journal-title":"J Cheminform"},{"issue":"5","key":"981_CR40","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.1021\/acs.accounts.8b00087","volume":"51","author":"Connor W Coley","year":"2018","unstructured":"Coley Connor W, Green William H, Jensen Klavs F (2018) Machine learning in computer-aided synthesis planning. Acc Chem Res 51(5):1281\u20131289","journal-title":"Acc Chem Res"},{"issue":"14","key":"981_CR41","doi-asserted-by":"publisher","first-page":"6582","DOI":"10.1021\/jm300687e","volume":"55","author":"MM Mysinger","year":"2012","unstructured":"Mysinger MM, Carchia M, Irwin JJ, Shoichet BK (2012) Directory of useful decoys, enhanced (dud-e): better ligands and decoys for better benchmarking. J Med Chem 55(14):6582\u20136594","journal-title":"J Med Chem"},{"key":"981_CR42","unstructured":"Landrum G, Tosco P, Kelley B, sriniker, gedeck, Schneider N, Vianello R, Ric, Dalke A, Cole B, Savelyev A, Swain M, Turk S, Dan N, Vaucher A, Kawashima E, W\u00f3jcikowski M, Probst D, Godin G, Cosgrove D, Pahl A, J\u00a0P, Berenger F, strets123, JL Varjo, O\u2019Boyle N, Fuller P, Jensen JH, Sforna G, Gavid D. RDKit: Open-source cheminformatics. https:\/\/www.rdkit.org"},{"key":"981_CR43","unstructured":"Biovia, dassault syst\u00e8mes (2022) biovia pipeline pilot, 5, san diego: Dassault syst\u00e8mes,"},{"key":"981_CR44","unstructured":"Nextmove software: Namerxn"},{"issue":"6","key":"981_CR45","doi-asserted-by":"publisher","first-page":"2529","DOI":"10.1021\/acs.jcim.9b00286","volume":"59","author":"Connor W Coley","year":"2019","unstructured":"Coley Connor W, Green William H, Jensen Klavs F (2019) Rdchiral: an rdkit wrapper for handling stereochemistry in retrosynthetic template extraction and application. J Chem Inf Model 59(6):2529\u20132537","journal-title":"J Chem Inf Model"},{"issue":"5","key":"981_CR46","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1021\/acscentsci.7b00064","volume":"3","author":"Connor W Coley","year":"2017","unstructured":"Coley Connor W, Barzilay Regina, Jaakkola Tommi S, Green William H, Jensen Klavs F (2017) Prediction of organic reaction outcomes using machine learning. ACS Central Sci 3(5):434\u2013443","journal-title":"ACS Central Sci"},{"key":"981_CR47","doi-asserted-by":"crossref","unstructured":"Goodman J (2009) Computer software review: Reaxys. J Chem Inf Model 49(12):2897\u20132898","DOI":"10.1021\/ci900437n"},{"key":"981_CR48","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1021\/bk-2014-1164.ch008","volume-title":"The future of the history of chemical information","author":"AJ Lawson","year":"2014","unstructured":"Lawson AJ, Swienty-Busch J, G\u00e9oui T, Evans D (2014) The making of reaxys-towards unobstructed access to relevant chemistry information. In: McEwen LR, Buntrock RE (eds) The future of the history of chemical information. ACS Publications, Washington, D.C., pp 127\u2013148"}],"container-title":["Journal of Cheminformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13321-025-00981-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13321-025-00981-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13321-025-00981-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:54:29Z","timestamp":1747162469000},"score":1,"resource":{"primary":{"URL":"https:\/\/jcheminf.biomedcentral.com\/articles\/10.1186\/s13321-025-00981-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,13]]},"references-count":48,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["981"],"URL":"https:\/\/doi.org\/10.1186\/s13321-025-00981-x","relation":{},"ISSN":["1758-2946"],"issn-type":[{"value":"1758-2946","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,13]]},"assertion":[{"value":"2 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing financial interest. Bayer AG was part of the MIT-led MLPDS consortium in the years 2018\u20132022.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"72"}}