{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T04:28:52Z","timestamp":1772166532811,"version":"3.50.1"},"reference-count":88,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T00:00:00Z","timestamp":1750118400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T00:00:00Z","timestamp":1750118400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["460865652"],"award-info":[{"award-number":["460865652"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["209933838"],"award-info":[{"award-number":["209933838"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009708","name":"Novo Nordisk Foundation","doi-asserted-by":"crossref","award":["0066551"],"award-info":[{"award-number":["0066551"]}],"id":[{"id":"10.13039\/501100009708","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Center of Excellence for AI-research Center for Scalable Data Analytics and Artificial Intelligence Dresden\/Leipzig","award":["SCADS24B"],"award-info":[{"award-number":["SCADS24B"]}]},{"DOI":"10.13039\/100015330","name":"Max Kade Foundation","doi-asserted-by":"publisher","award":["Fellowship"],"award-info":[{"award-number":["Fellowship"]}],"id":[{"id":"10.13039\/100015330","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["57616814"],"award-info":[{"award-number":["57616814"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NIH","award":["R01 DA046138"],"award-info":[{"award-number":["R01 DA046138"]}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt Foundation","doi-asserted-by":"crossref","award":["Humboldt Professorship"],"award-info":[{"award-number":["Humboldt Professorship"]}],"id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100018929","name":"de.NBI","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100018929","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100008678","name":"Universit\u00e4t Leipzig","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008678","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cheminform"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Genetic algorithms are a powerful method to solve optimization problems with complex cost functions over vast search spaces that rely in particular on recombining parts of previous solutions. Crossover operators play a crucial role in this context. Here, we describe a large class of these operators designed for searching over spaces of graphs. These operators are based on introducing small cuts into graphs and rejoining the resulting induced subgraphs of two parents. This form of cut-and-join crossover can be restricted in a consistent way to preserve local properties such as vertex-degrees (valency), or bond-orders, as well as global properties such as graph-theoretic planarity. In contrast to crossover on strings, cut-and-join crossover on graphs is powerful enough to ergodically explore chemical space even in the absence of mutation operators. Extensive benchmarking shows that the offspring of molecular graphs are again plausible molecules with high probability, while at the same time crossover drastically increases the diversity compared to initial molecule libraries. Moreover, desirable properties such as favorable indices of synthesizability are preserved with sufficient frequency that candidate offsprings can be filtered efficiently for such properties. As an application we utilized the cut-and-join crossover in , a GA-based system for computer-aided drug design. In optimization runs searching for ligands binding to four different target proteins we consistently found candidate molecules with binding constants exceeding the best known binders as well as candidates found in make-on-demand libraries.<\/jats:p>\n                  <jats:p>\n                    <jats:bold>Scientific contribution<\/jats:bold>\n                  <\/jats:p>\n                  <jats:p>We define cut-and-join crossover operators on a variety of graph classes including molecular graphs. This constitutes a mathematically simple and well-characterized approach to recombination of molecules that performed very well in real-life CADD tasks.<\/jats:p>","DOI":"10.1186\/s13321-025-00958-w","type":"journal-article","created":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T14:36:56Z","timestamp":1750171016000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Crossover operators for molecular graphs with an application to virtual drug screening"],"prefix":"10.1186","volume":"17","author":[{"given":"Nico","family":"Domschke","sequence":"first","affiliation":[]},{"given":"Bruno J.","family":"Schmidt","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Gatter","sequence":"additional","affiliation":[]},{"given":"Richard","family":"Golnik","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Eisenhuth","sequence":"additional","affiliation":[]},{"given":"Fabian","family":"Liessmann","sequence":"additional","affiliation":[]},{"given":"Jens","family":"Meiler","sequence":"additional","affiliation":[]},{"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,17]]},"reference":[{"key":"958_CR1","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1080\/14786447408641058","volume":"47","author":"A Cayley","year":"1874","unstructured":"Cayley A (1874) On the mathematical theory of isomers. Phil Mag 47:444\u2013446","journal-title":"Phil Mag"},{"key":"958_CR2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199591756.001.0001","volume-title":"The Structure of Complex Networks: Theory and Applications","author":"E Estrada","year":"2011","unstructured":"Estrada E (2011) The Structure of Complex Networks: Theory and Applications. Oxford University Press, Oxford, UK"},{"key":"958_CR3","doi-asserted-by":"publisher","first-page":"8091","DOI":"10.1007\/s11042-020-10139-6","volume":"80","author":"S Katoch","year":"2021","unstructured":"Katoch S, Chauhan SS, Kumar V (2021) A review on genetic algorithm: past, present, and future. Multimedia Tools Appl 80:8091\u20138126. https:\/\/doi.org\/10.1007\/s11042-020-10139-6","journal-title":"Multimedia Tools Appl"},{"key":"958_CR4","doi-asserted-by":"publisher","first-page":"19","DOI":"10.5815\/ijisa.2015.11.03","volume":"11","author":"IH Khan","year":"2015","unstructured":"Khan IH (2015) Assessing different crossover operators for Travelling Salesman Problem. Intl J Intelligent Systems and Applications 11:19\u201325. https:\/\/doi.org\/10.5815\/ijisa.2015.11.03","journal-title":"Intl J Intell Syst Appl"},{"issue":"5","key":"958_CR5","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1016\/j.cbpa.2007.08.033","volume":"11","author":"C McInnes","year":"2007","unstructured":"McInnes C (2007) Virtual screening strategies in drug discovery. Current Opinion in Chemical Biology 11(5):494\u2013502. https:\/\/doi.org\/10.1016\/j.cbpa.2007.08.033","journal-title":"Curr Opin Chem Biol"},{"key":"958_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0169-409X(00)00129-0","volume":"46","author":"CA Lipinski","year":"1997","unstructured":"Lipinski CA, Lombardo F, Dominy BW et al (1997) Experimental and computational approaches to estimate solubility and permeability in drug discovery and development settings. Advanced Drug Delivery Reviews 46:3\u201326. https:\/\/doi.org\/10.1016\/S0169-409X(00)00129-0","journal-title":"Adv Drug Delivery Rev"},{"issue":"6","key":"958_CR7","doi-asserted-by":"publisher","first-page":"2280","DOI":"10.1002\/anie.199522801","volume":"27","author":"L Weber","year":"1996","unstructured":"Weber L, Wallbaum S, Broger C et al (1996) Optimization of the biological activity of combinatorial compound libraries by a genetic algorithm. ChemInform 27(6):2280\u20132282. https:\/\/doi.org\/10.1002\/anie.199522801","journal-title":"ChemInform"},{"key":"958_CR8","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1016\/j.asoc.2014.09.042","volume":"27","author":"RV Devi","year":"2015","unstructured":"Devi RV, Sathya SS, Coumar MS (2015) Evolutionary algorithms for de novo drug design-a survey. Appl Soft Comput 27:543\u2013552. https:\/\/doi.org\/10.1016\/j.asoc.2014.09.042","journal-title":"Appl Soft Comput"},{"issue":"3","key":"958_CR9","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1021\/acs.jcim.1c01378","volume":"62","author":"L Bellmann","year":"2022","unstructured":"Bellmann L, Penner P, Gastreich M et al (2022) Comparison of combinatorial fragment spaces and its application to ultralarge make-on-demand compound catalogs. J Chem Inf Model 62(3):553\u2013566. https:\/\/doi.org\/10.1021\/acs.jcim.1c01378","journal-title":"J Chem Inf Model"},{"issue":"11","key":"958_CR10","doi-asserted-by":"publisher","first-page":"101681","DOI":"10.1016\/j.isci.2020.101681","volume":"23","author":"OO Grygorenko","year":"2020","unstructured":"Grygorenko OO, Radchenko DS, Dziuba I et al (2020) Generating multibillion chemical space of readily accessible screening compounds. iScience 23(11):101681. https:\/\/doi.org\/10.1016\/j.isci.2020.101681","journal-title":"iScience"},{"key":"958_CR11","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2404.17329","author":"P Eisenhuth","year":"2024","unstructured":"Eisenhuth P, Liessmann F, Moretti R et al (2024) REvoLd: Ultra-large library screening with an evolutionary algorithm in Rosetta. Tech Rep. https:\/\/doi.org\/10.48550\/arXiv.2404.17329","journal-title":"Tech Rep"},{"key":"958_CR12","unstructured":"Enamine (2024) Real space. URL https:\/\/enamine.net\/compound-collections\/real-compounds\/real-space-navigator"},{"key":"958_CR13","doi-asserted-by":"publisher","unstructured":"Kuck D (2009) Molecules with nonstandard topological properties: Centrohexaindane, Kuratowski\u2019s cyclophane and other graph-theoretically nonplanar molecules. In: Dodziuk H (ed) Strained Hydrocarbons: Beyond the van-t Hoff and Le Bel Hypothesis. VCH, Weinheim, https:\/\/doi.org\/10.1002\/9783527627134.ch9","DOI":"10.1002\/9783527627134.ch9"},{"key":"958_CR14","first-page":"153","volume":"45","author":"C R\u00fccker","year":"2002","unstructured":"R\u00fccker C, Meringer M (2002) How many organic compounds are graph-theoretically nonplanar? Comm Math Comp Chem 45:153\u2013172","journal-title":"Comm Math Comp Chem"},{"key":"958_CR15","doi-asserted-by":"publisher","unstructured":"Wang W, Zhou S, Yu X, et\u00a0al (2024) What can topology bring to chemistry? CCS Chemistry 2024(6):2084\u20132109. https:\/\/doi.org\/10.31635\/ccschem.024.202404398","DOI":"10.31635\/ccschem.024.202404398"},{"issue":"3","key":"958_CR16","doi-asserted-by":"publisher","first-page":"1079","DOI":"10.1021\/ci034290p","volume":"44","author":"N Brown","year":"2004","unstructured":"Brown N, McKay B, Gilardoni F et al (2004) A graph-based genetic algorithm and its application to the multiobjective evolution of median molecules. J Chem Inf Comput Sci 44(3):1079\u20131087. https:\/\/doi.org\/10.1021\/ci034290p","journal-title":"J Chem Inf Comput Sci"},{"key":"958_CR17","doi-asserted-by":"publisher","unstructured":"Globus A, Lawton WTJ, Wipke (1999) Automatic molecular design using evolutionary algorithms. Nanotechnology 10:290\u2013299. https:\/\/doi.org\/10.1088\/0957-4484\/10\/3\/312","DOI":"10.1088\/0957-4484\/10\/3\/312"},{"issue":"2","key":"958_CR18","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1021\/ci800308h","volume":"49","author":"CA Nicolaou","year":"2009","unstructured":"Nicolaou CA, Apostolakis J, Pattichis CS (2009) De novo drug design using multiobjective evolutionary graphs. J Chem Inf Model 49(2):295\u2013307. https:\/\/doi.org\/10.1021\/ci800308h","journal-title":"J Chem Inf Model"},{"key":"958_CR19","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1021\/ci970429i","volume":"38","author":"XQ Lewell","year":"1998","unstructured":"Lewell XQ, Judd DB, Watson SP et al (1998) RECAP - retrosynthetic combinatorial analysis procedure: a powerful new technique for identifying privileged molecular fragments with useful applications in combinatorial chemistry. J Chem Inf Comput Sci 38:511\u2013522. https:\/\/doi.org\/10.1021\/ci970429i","journal-title":"J Chem Inf Comput Sci"},{"key":"958_CR20","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1021\/ci6005307","volume":"47","author":"U Fechner","year":"2007","unstructured":"Fechner U, Schneider G (2007) Flux (2): Comparison of molecular mutation and crossover operators for ligand-based de novo design. J Chem Inf Model 47:656\u2013667. https:\/\/doi.org\/10.1021\/ci6005307","journal-title":"J Chem Inf Model"},{"issue":"12","key":"958_CR21","doi-asserted-by":"publisher","first-page":"3567","DOI":"10.1039\/c8sc05372c","volume":"10","author":"JH Jensen","year":"2019","unstructured":"Jensen JH (2019) A graph-based genetic algorithm and generative model\/monte carlo tree search for the exploration of chemical space. Chem Sci 10(12):3567\u20133572. https:\/\/doi.org\/10.1039\/c8sc05372c","journal-title":"Chem Sci"},{"key":"958_CR22","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1109\/TCBB.2010.100","volume":"8","author":"SSY Wong","year":"2011","unstructured":"Wong SSY, Luo W, Chan KCC (2011) EvoMD: an algorithm for evolutionary molecular design. IEEE\/ACM Trans Comput Biol Bioinform 8:987\u20131003. https:\/\/doi.org\/10.1109\/TCBB.2010.100","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"958_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13321-021-00566-4","volume":"13","author":"F Berenger","year":"2021","unstructured":"Berenger F, Tsuda K (2021) Molecular generation by fast assembly of (deep) smiles fragments. J Cheminform 13:1\u201310","journal-title":"J Cheminform"},{"issue":"1","key":"958_CR24","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1186\/s13321-021-00501-7","volume":"13","author":"Y Kwon","year":"2021","unstructured":"Kwon Y, Lee J (2021) Molfinder: an evolutionary algorithm for the global optimization of molecular properties and the extensive exploration of chemical space using smiles. Journal of cheminformatics 13(1):24","journal-title":"J Cheminform"},{"issue":"20","key":"958_CR25","doi-asserted-by":"publisher","first-page":"7079","DOI":"10.1039\/D1SC00231G","volume":"12","author":"A Nigam","year":"2021","unstructured":"Nigam A, Pollice R, Krenn M et al (2021) Beyond generative models: superfast traversal, optimization, novelty, exploration and discovery (stoned) algorithm for molecules using selfies. Chemical science 12(20):7079\u20137090","journal-title":"Chem Sci"},{"key":"958_CR26","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1021\/ja02261a002","volume":"38","author":"GN Lewis","year":"1916","unstructured":"Lewis GN (1916) The atom and the molecule. J Am Chem Soc 38:762\u2013785. https:\/\/doi.org\/10.1021\/ja02261a002","journal-title":"J Am Chem Soc"},{"key":"958_CR27","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1351\/pac199466051077","volume":"66","author":"P Muller","year":"1994","unstructured":"Muller P (1994) Glossary of terms used in physical organic chemistry (IUPAC Recommendations 1994). Pure Appl Chem 66:1077\u20131184. https:\/\/doi.org\/10.1351\/pac199466051077","journal-title":"Pure Appl Chem"},{"key":"958_CR28","doi-asserted-by":"publisher","first-page":"782","DOI":"10.1007\/s00453-023-01163-7","volume":"86","author":"J Bok","year":"2024","unstructured":"Bok J, Fiala J, Jedli\u010dkov\u00e1 N et al (2024) List covering of regular multigraphs with semi-edges. Algorithmica 86:782\u2013807. https:\/\/doi.org\/10.1007\/s00453-023-01163-7","journal-title":"Algorithmica"},{"issue":"10","key":"958_CR29","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/s10822-009-9303-2","volume":"23","author":"Y Connolly Martin","year":"2009","unstructured":"Connolly Martin Y (2009) Let\u2019s not forget tautomers. J Comput Aided Mol Des 23(10):693\u2013704. https:\/\/doi.org\/10.1007\/s10822-009-9303-2","journal-title":"J Comput Aided Mol Des"},{"key":"958_CR30","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/s10822-010-9329-5","volume":"24","author":"RA Sayle","year":"2010","unstructured":"Sayle RA (2010) So you think you understand tautomerism? J Comput Aided Mol Des 24:485\u2013496. https:\/\/doi.org\/10.1007\/s10822-010-9329-5","journal-title":"J Comput Aided Mol Des"},{"issue":"11","key":"958_CR31","doi-asserted-by":"publisher","first-page":"2864","DOI":"10.1021\/ci300415d","volume":"52","author":"L Ruddigkeit","year":"2012","unstructured":"Ruddigkeit L, van Deursen R, Blum LC et al (2012) Enumeration of 166 billion organic small molecules in the chemical universe database GDB-17. J Chem Inf Mod 52(11):2864\u20132875. https:\/\/doi.org\/10.1021\/ci300415d","journal-title":"J Chem Inf Mod"},{"issue":"8","key":"958_CR32","doi-asserted-by":"publisher","first-page":"1200","DOI":"10.1109\/TPAMI.2006.152","volume":"28","author":"D Justice","year":"2006","unstructured":"Justice D, Hero A (2006) A binary linear programming formulation of the graph edit distance. IEEE Trans Pattern Anal Mach Intell 28(8):1200\u20131214. https:\/\/doi.org\/10.1109\/TPAMI.2006.152","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"6","key":"958_CR33","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/1866158.1866179","volume":"29","author":"Y Li","year":"2010","unstructured":"Li Y, Zhang E, Kobayashi Y et al (2010) Editing operations for irregular vertices in triangle meshes. ACM Trans Graph 29(6):153. https:\/\/doi.org\/10.1145\/1866158.1866179","journal-title":"ACM Trans Graph"},{"issue":"3","key":"958_CR34","doi-asserted-by":"publisher","first-page":"e1011905","DOI":"10.1371\/journal.pcbi.1011905","volume":"20","author":"YP Kuo","year":"2024","unstructured":"Kuo YP, Carja O (2024) Evolutionary graph theory beyond pairwise interactions: Higher-order network motifs shape times to fixation in structured populations. PLoS Comput Biol 20(3):e1011905. https:\/\/doi.org\/10.1371\/journal.pcbi.1011905","journal-title":"PLoS Comput Biol"},{"key":"958_CR35","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1137\/10079973","volume":"26","author":"C D\u00fcrr","year":"2012","unstructured":"D\u00fcrr C, Gui\u00f1ez F, Matamala M (2012) Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard: a solution to the 2-atom problem in discrete tomography. SIAM J Discrete Math 26:330\u2013352. https:\/\/doi.org\/10.1137\/10079973","journal-title":"SIAM J Discrete Math"},{"issue":"3","key":"958_CR36","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/S0895480190177042","volume":"7","author":"D Hartvigsen","year":"1994","unstructured":"Hartvigsen D, Mardon R (1994) The all-pairs min cut problem and the minimum cycle basis problem on planar graphs. SIAM J Discr Math 7(3):403\u2013418. https:\/\/doi.org\/10.1137\/S0895480190177042","journal-title":"SIAM J Discr Math"},{"issue":"3","key":"958_CR37","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1109\/TCT.1972.1083456","volume":"19","author":"H Ariyoshi","year":"1972","unstructured":"Ariyoshi H (1972) Cut-set graph and systematic generation of separating sets. IEEE Trans Circuit Theory CT 19(3):233\u2013240. https:\/\/doi.org\/10.1109\/TCT.1972.1083456","journal-title":"IEEE Trans Circuit Theory CT"},{"key":"958_CR38","doi-asserted-by":"publisher","unstructured":"Jensen PA, Bellmore M (1969) An algorithm to determine the reliability of a complex system. IEEE Trans Reliability R-18(4):169\u2013174. https:\/\/doi.org\/10.1109\/TR.1969.5216346","DOI":"10.1109\/TR.1969.5216346"},{"key":"958_CR39","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1007\/BFb0120902","volume":"13","author":"JC Picard","year":"1980","unstructured":"Picard JC, Queyranne M (1980) On the structure of all minimum cuts in a network and applications. Math Programming Study 13:8\u201316. https:\/\/doi.org\/10.1007\/BFb0120902","journal-title":"Math Programm Study"},{"issue":"4","key":"958_CR40","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1145\/322217.322220","volume":"27","author":"S Tsukiyama","year":"1980","unstructured":"Tsukiyama S, Shirakawa I, Ozaki H et al (1980) An algorithm to enumerate all cutsets of a graph in linear time per cutset. J ACM 27(4):619\u2013632. https:\/\/doi.org\/10.1145\/322217.322220","journal-title":"J ACM"},{"key":"958_CR41","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.dam.2024.01.004","volume":"348","author":"A Raffaele","year":"2024","unstructured":"Raffaele A, Rizzi RR, Uno T (2024) Listing the bonds of a graph in $$\\tilde{O}(n)$$-delay. Discrete Applied Mathematics 348:105\u2013121. https:\/\/doi.org\/10.1016\/j.dam.2024.01.004","journal-title":"Discrete Appl Math"},{"key":"958_CR42","unstructured":"Duarte GL, Lokshtanov D, Pedrosa LLC et al. (2019) Computing the largest bond of a graph. In: Jansen BMP, Telle JAT (eds) 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Leibniz International Proceedings in Informatics, vol 148. Dagstuhl Publishing, Schloss Dagstuhl. 12"},{"key":"958_CR43","doi-asserted-by":"publisher","unstructured":"Vazirani VV, Yannakakis M (1992) Suboptimal cuts: Their enumeration, weight and number. In: Kuich W (ed) International Colloquium on Automata, Languages, and Programming ICALP 1992, Lect. Notes Comp. Sci., vol 623. Springer, Berlin, Heidelberg, pp 366\u2013377, https:\/\/doi.org\/10.5555\/646246.684856","DOI":"10.5555\/646246.684856"},{"key":"958_CR44","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00453-009-9284-5","volume":"56","author":"LP Yeh","year":"2010","unstructured":"Yeh LP, Wang BF, Su HH (2010) Efficient algorithms for the problems of enumerating cuts by non-decreasing weights. Algorithmica 56:297\u2013312. https:\/\/doi.org\/10.1007\/s00453-009-9284-5","journal-title":"Algorithmica"},{"key":"958_CR45","doi-asserted-by":"publisher","unstructured":"Guasque A, Balbastre P (2022) Evaluation and comparison of integer programming solvers for hard real-time scheduling. IEEE Trans Inform Systems E105.D(10):1726\u20131733. https:\/\/doi.org\/10.1587\/transinf.2022EDP7073","DOI":"10.1587\/transinf.2022EDP7073"},{"key":"958_CR46","doi-asserted-by":"publisher","unstructured":"Moraglio A, Poli R (2004) Topological interpretation of crossover. In: Deb K, Poli R, Banzhaf W, et\u00a0al (eds) Genetic and Evolutionary Computation \u2013 GECCO 2004, pp 1377\u20131388, https:\/\/doi.org\/10.1007\/978-3-540-24854","DOI":"10.1007\/978-3-540-24854"},{"key":"958_CR47","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H Whitney","year":"1932","unstructured":"Whitney H (1932) Non-separable and planar graphs. Trans Amer Math Soc 34:339\u2013362","journal-title":"Trans Amer Math Soc"},{"key":"958_CR48","doi-asserted-by":"publisher","unstructured":"Morin L, Danelljan M, Agea MI et\u00a0al (2023) MolGrapher: Graph-based visual recognition of chemical structures. In: 2023 IEEE\/CVF International Conference on Computer Vision (ICCV), pp 19495\u201319504, https:\/\/doi.org\/10.1109\/iccv51070.2023.01791, URL http:\/\/arxiv.org\/abs\/2308.12234, arXiv:2308.12234 [cs]","DOI":"10.1109\/iccv51070.2023.01791"},{"issue":"1","key":"958_CR49","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1186\/s13321-015-0068-4","volume":"7","author":"SR Heller","year":"2015","unstructured":"Heller SR, McNaught A, Pletnev I et al (2015) InChI, the IUPAC International Chemical Identifier. J Cheminformatics 7(1):23. https:\/\/doi.org\/10.1186\/s13321-015-0068-4","journal-title":"J Cheminform"},{"key":"958_CR50","first-page":"2579","volume":"9","author":"LJP van der Maaten","year":"2008","unstructured":"van der Maaten LJP, Hinton GE (2008) Visualizing data using t-SNE. J Machine Learning Res 9:2579\u20132605","journal-title":"J Mach Learn Res"},{"issue":"6","key":"958_CR51","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/0898-5529(90)90156-3","volume":"3","author":"J Gasteiger","year":"1990","unstructured":"Gasteiger J, Rudolph C, Sadowski J (1990) Automatic generation of 3D-atomic coordinates for organic molecules. Tetrahedron Comput Methodol 3(6):537\u2013547. https:\/\/doi.org\/10.1016\/0898-5529(90)90156-3","journal-title":"Tetrahedron Comput Methodol"},{"issue":"8","key":"958_CR52","doi-asserted-by":"publisher","first-page":"1747","DOI":"10.1021\/acs.jcim.7b00221","volume":"57","author":"PCD Hawkins","year":"2017","unstructured":"Hawkins PCD (2017) Conformation generation: The state of the art. J Chem Inf Model 57(8):1747\u20131756. https:\/\/doi.org\/10.1021\/acs.jcim.7b00221","journal-title":"J Chem Inf Model"},{"key":"958_CR53","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1186\/1471-2105-11-531","volume":"11","author":"A Hildebrandt","year":"2010","unstructured":"Hildebrandt A, Dehof AK, Rurainski A et al (2010) BALL \u2013 biochemical algorithms library 1.3. BMC Bioinformatics 11:531. https:\/\/doi.org\/10.1186\/1471-2105-11-531","journal-title":"BMC Bioinformatics"},{"key":"958_CR54","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1186\/s13321-019-0372-5","volume":"11","author":"N Yoshikawa","year":"2019","unstructured":"Yoshikawa N, Hutchison GR (2019) Fast, efficient fragment-based coordinate generation for Open Babel. J Cheminformatics 11:49. https:\/\/doi.org\/10.1186\/s13321-019-0372-5","journal-title":"J Cheminform"},{"issue":"12","key":"958_CR55","doi-asserted-by":"publisher","first-page":"2562","DOI":"10.1021\/acs.jcim.5b00654","volume":"55","author":"S Riniker","year":"2015","unstructured":"Riniker S, Landrum GA (2015) Better informed distance geometry: Using what we know to improve conformation generation. J Chem Inf Model 55(12):2562\u20132574. https:\/\/doi.org\/10.1021\/acs.jcim.5b00654","journal-title":"J Chem Inf Model"},{"issue":"12","key":"958_CR56","doi-asserted-by":"publisher","first-page":"5714","DOI":"10.1021\/acs.jcim.0c00174","volume":"60","author":"W Gao","year":"2020","unstructured":"Gao W, Coley CW (2020) The synthesizability of molecules proposed by generative models. J Chem Inf Model 60(12):5714\u20135723. https:\/\/doi.org\/10.1021\/acs.jcim.0c00174","journal-title":"J Chem Inf Model"},{"issue":"1","key":"958_CR57","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1186\/1758-2946-1-8","volume":"1","author":"P Ertl","year":"2009","unstructured":"Ertl P, Schuffenhauer A (2009) Estimation of synthetic accessibility score of drug-like molecules based on molecular complexity and fragment contributions. J Cheminformatics 1(1):8. https:\/\/doi.org\/10.1186\/1758-2946-1-8","journal-title":"J Cheminform"},{"issue":"2","key":"958_CR58","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1021\/acs.jcim.7b00622","volume":"58","author":"CW Coley","year":"2018","unstructured":"Coley CW, Rogers L, Green WH et al (2018) SCScore: Synthetic complexity learned from a reaction corpus. J Chem Inf Model 58(2):252\u2013261. https:\/\/doi.org\/10.1021\/acs.jcim.7b00622","journal-title":"J Chem Inf Model"},{"key":"958_CR59","doi-asserted-by":"publisher","first-page":"565644","DOI":"10.3389\/fphar.2020.565644","volume":"11","author":"D Polykovskiy","year":"2020","unstructured":"Polykovskiy D, Zhebrak A, Sanchez-Lengeling B et al (2020) Molecular sets (MOSES): A benchmarking platform for molecular generation models. Front Pharmacol 11:565644. https:\/\/doi.org\/10.3389\/fphar.2020.565644","journal-title":"Front Pharmacol"},{"issue":"15","key":"958_CR60","doi-asserted-by":"publisher","first-page":"2887","DOI":"10.1021\/jm9602928","volume":"39","author":"GW Bemis","year":"1996","unstructured":"Bemis GW, Murcko MA (1996) The properties of known drugs. 1. Molecular frameworks. J Med Chem 39(15):2887\u20132893. https:\/\/doi.org\/10.1021\/jm9602928","journal-title":"J Med Chem"},{"issue":"10","key":"958_CR61","doi-asserted-by":"publisher","first-page":"1503","DOI":"10.1002\/cmdc.200800178","volume":"3","author":"J Degen","year":"2008","unstructured":"Degen J, Wegscheid-Gerlach C, Zaliani A et al (2008) On the art of compiling and using \u2019drug-like\u2019 chemical fragment spaces. ChemMedChem 3(10):1503\u20131507. https:\/\/doi.org\/10.1002\/cmdc.200800178","journal-title":"ChemMedChem"},{"issue":"9","key":"958_CR62","doi-asserted-by":"publisher","first-page":"1736","DOI":"10.1021\/acs.jcim.8b00234","volume":"58","author":"K Preuer","year":"2018","unstructured":"Preuer K, Renz P, Unterthiner T et al (2018) Fr\u00e9chet ChemNet Distance: A metric for generative models for molecules in drug discovery. J Chem Inf Model 58(9):1736\u20131741","journal-title":"J Chem Inf Model"},{"key":"958_CR63","doi-asserted-by":"publisher","first-page":"2719","DOI":"10.1021\/jm901137j","volume":"53","author":"JB Baell","year":"2010","unstructured":"Baell JB, Holloway GA (2010) New substructure filters for removal of pan assay interference compounds (PAINS) from screening libraries and for their exclusion in bioassays. J Med Chem 53:2719\u20132740. https:\/\/doi.org\/10.1021\/jm901137j","journal-title":"J Med Chem"},{"issue":"7","key":"958_CR64","doi-asserted-by":"publisher","first-page":"1444","DOI":"10.3390\/molecules24071444","volume":"24","author":"Y Chu","year":"2019","unstructured":"Chu Y, He X (2019) MoleGear: a java-based platform for evolutionary de novo molecular design. Molecules 24(7):1444","journal-title":"Molecules"},{"key":"958_CR65","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1016\/S1074-5521(00)00122-8","volume":"7","author":"K Illgen","year":"2000","unstructured":"Illgen K, Enderle T, Broger C et al (2000) Simulated molecular evolution in a full combinatorial library. Chemistry and Biology 7:433\u2013441. https:\/\/doi.org\/10.1016\/S1074-5521(00)00122-8","journal-title":"Chem Biol"},{"key":"958_CR66","doi-asserted-by":"publisher","unstructured":"Kerstjens A, Winter HD (2022) Leadd: Lamarckian evolutionary algorithm for de novo drug design. Journal of Cheminformatics 14:1\u201320. https:\/\/doi.org\/10.1186\/S13321-022-00582-Y\/FIGURES\/17, URL https:\/\/jcheminf.biomedcentral.com\/articles\/10.1186\/s13321-022-00582-yhttp:\/\/creativecommons.org\/publicdomain\/zero\/1.0\/","DOI":"10.1186\/S13321-022-00582-Y\/FIGURES\/17"},{"key":"958_CR67","doi-asserted-by":"publisher","unstructured":"Leguy J, Cauchy T, Glavatskikh M et al (2020) Evomol: a flexible and interpretable evolutionary algorithm for unbiased de novo molecular generation. Journal of Cheminformatics 12:1\u201319. https:\/\/doi.org\/10.1186\/S13321-020-00458-Z\/FIGURES\/10, URL https:\/\/jcheminf.biomedcentral.com\/articles\/10.1186\/s13321-020-00458-z","DOI":"10.1186\/S13321-020-00458-Z\/FIGURES\/10"},{"key":"958_CR68","doi-asserted-by":"publisher","unstructured":"Meyenburg C, Dolfus U, Briem H et al (2022) Galileo: Three-dimensional searching in large combinatorial fragment spaces on the example of pharmacophores. Journal of Computer-Aided Molecular Design. https:\/\/doi.org\/10.1007\/s10822-022-00485-y","DOI":"10.1007\/s10822-022-00485-y"},{"key":"958_CR69","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13321-020-00429-4","volume":"12","author":"JO Spiegel","year":"2020","unstructured":"Spiegel JO, Durrant JD (2020) Autogrow4: An open-source genetic algorithm for de novo drug design and lead optimization. Journal of Cheminformatics 12:1\u201316. https:\/\/doi.org\/10.1186\/s13321-020-00429-4","journal-title":"J Cheminform"},{"key":"958_CR70","doi-asserted-by":"publisher","first-page":"e18","DOI":"10.7717\/peerj-pchem.18","volume":"3","author":"C Steinmann","year":"2021","unstructured":"Steinmann C, Jensen JH (2021) Using a genetic algorithm to find molecules with good docking scores. PeerJ Physical Chemistry 3:e18. https:\/\/doi.org\/10.7717\/peerj-pchem.18","journal-title":"PeerJ Phys Chem"},{"key":"958_CR71","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2404.17329","author":"P Eisenhuth","year":"2024","unstructured":"Eisenhuth P, Liessmann F, Moretti R et al (2024b) Revold: ultra-large library screening with an evolutionary algorithm in Rosetta. arXiv. https:\/\/doi.org\/10.48550\/arXiv.2404.17329","journal-title":"arXiv"},{"key":"958_CR72","doi-asserted-by":"publisher","first-page":"1","DOI":"10.21767\/2470-6973.100022","volume":"3","author":"M Butkiewicz","year":"2017","unstructured":"Butkiewicz M, Wang Y, Bryant SH et al (2017) High-throughput screening assay datasets from the pubchem database. Chem Inform 3:1\u20137. https:\/\/doi.org\/10.21767\/2470-6973.100022","journal-title":"Chem Inform"},{"key":"958_CR73","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00406-0","volume":"259","author":"LM Schmitt","year":"2001","unstructured":"Schmitt LM (2001) Theory of genetic algorithms. Theor Comp Sci 259:1\u201361. https:\/\/doi.org\/10.1016\/S0304-3975(00)00406-0","journal-title":"Theor Comp Sci"},{"key":"958_CR74","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0304-3975(03)00393-1","volume":"310","author":"LM Schmitt","year":"2004","unstructured":"Schmitt LM (2004) Theory of genetic algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling. Theor Comp Sci 310:181\u2013231. https:\/\/doi.org\/10.1016\/S0304-3975(03)00393-1","journal-title":"Theor Comp Sci"},{"key":"958_CR75","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1186\/s13321-022-00677-6","volume":"15","author":"SR Rieder","year":"2023","unstructured":"Rieder SR, Oliveira MP, Riniker S et al (2023) Development of an open-source software for isomer enumeration. J Cheminform 15:10. https:\/\/doi.org\/10.1186\/s13321-022-00677-6","journal-title":"J Cheminform"},{"key":"958_CR76","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-61470-04","author":"JL Andersen","year":"2017","unstructured":"Andersen JL, Flamm C, Merkle D et al (2017) Chemical graph transformation with stereo-information. Lect Notes Comp Sci. https:\/\/doi.org\/10.1007\/978-3-319-61470-04","journal-title":"Lect Notes Comp Sci"},{"key":"958_CR77","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0304-3975(97)00298-3","volume":"233","author":"RJ Gardner","year":"2000","unstructured":"Gardner RJ, Gritzmann P, Prangenberg D (2000) On the computational complexity of determining polyatomic structures by X-rays. Theoret Comput Sci 233:91\u2013106. https:\/\/doi.org\/10.1016\/S0304-3975(97)00298-3","journal-title":"Theoret Comput Sci"},{"key":"958_CR78","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0304-3975(99)00325-4","volume":"259","author":"M Chrobak","year":"2001","unstructured":"Chrobak M, D\u00fcrr C (2001) Reconstructing polyatomic structures from discrete x-rays: NP-completeness proof for three atoms. Theoret Comput Sci 259:81\u201398. https:\/\/doi.org\/10.1016\/S0304-3975(99)00325-4","journal-title":"Theoret Comput Sci"},{"key":"958_CR79","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.ejor.2003.10.037","volume":"162","author":"MC Costa","year":"2005","unstructured":"Costa MC, L\u00e9tocart L, Roupin F (2005) Minimal multicut and maximal integer multiflow: a survey. Eur J Oper Res 162:55\u201369. https:\/\/doi.org\/10.1016\/j.ejor.2003.10.037","journal-title":"Eur J Oper Res"},{"key":"958_CR80","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1090\/S0002-9904-1960-10494-6","volume":"66","author":"HJ Ryser","year":"1960","unstructured":"Ryser HJ (1960) Matrices of zeros and ones. Bull Amer Math Soc 66:442\u2013464. https:\/\/doi.org\/10.1090\/S0002-9904-1960-10494-6","journal-title":"Bull Amer Math Soc"},{"key":"958_CR81","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.2140\/pjm.1957.7.1073","volume":"7","author":"D Gale","year":"1957","unstructured":"Gale D (1957) A theorem on flows in networks. Pacific J Math 7:1073\u20131082. https:\/\/doi.org\/10.2140\/pjm.1957.7.1073","journal-title":"Pacific J Math"},{"key":"958_CR82","doi-asserted-by":"publisher","first-page":"371","DOI":"10.4153\/CJM-1957-044-3","volume":"9","author":"H Ryser","year":"1957","unstructured":"Ryser H (1957) Combinatorial properties of matrices of zeros and ones. Canadian J Math 9:371\u2013377. https:\/\/doi.org\/10.4153\/CJM-1957-044-3","journal-title":"Canadian J Math"},{"issue":"4","key":"958_CR83","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1080\/00029890.1996.12004747","volume":"103","author":"M Krause","year":"1996","unstructured":"Krause M (1996) A simple proof of the Gale-Ryser theorem. American Mathematical Monthly 103(4):335\u2013337. https:\/\/doi.org\/10.1080\/00029890.1996.12004747","journal-title":"Am Math Month"},{"key":"958_CR84","doi-asserted-by":"publisher","unstructured":"P\u00e9rez-Salvador BR, de-los Cobos-Silva S, Gut\u00ederrez-\u00c1ndrade MA, et al (2002) A reduced formula for the precise number of $$(0,1)$$-matrices in $${\\cal{A}}(R, S)$$. Discrete Math 256:361\u2013372. https:\/\/doi.org\/10.1016\/S0012-365X(97)00197-0","DOI":"10.1016\/S0012-365X(97)00197-0"},{"key":"958_CR85","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/S0021-9800(68)80026-2","volume":"5","author":"L Mirsky","year":"1968","unstructured":"Mirsky L (1968) Combinatorial theorems and integral matrices. J Combin Theory 5:30\u201344. https:\/\/doi.org\/10.1016\/S0021-9800(68)80026-2","journal-title":"J Combin Theory"},{"key":"958_CR86","doi-asserted-by":"publisher","first-page":"1553","DOI":"10.1016\/j.laa.2009.05.024","volume":"431","author":"JA Dias da Silva","year":"2009","unstructured":"Dias da Silva JA, Fonseca A (2009) Constructing integral matrices with given line sums. Linear Algebra Appl 431:1553\u20131563. https:\/\/doi.org\/10.1016\/j.laa.2009.05.024","journal-title":"Linear Algebra Appl"},{"key":"958_CR87","doi-asserted-by":"publisher","unstructured":"G\u00e9rard Y (2008) Reconstructing a matrix with a given list of coefficients and prescribed row and column sums is NP-hard. In: Brimkov VE, Barneva RP, Hauptman HA (eds) Combinatorial Image Analysis, IWCIA 2008. Lecture Notes Comp Sci. Springer, Berlin, Heidelberg. 4958; 363\u2013371, https:\/\/doi.org\/10.1007\/978-3-540-78275-9_32","DOI":"10.1007\/978-3-540-78275-9_32"},{"key":"958_CR88","doi-asserted-by":"publisher","unstructured":"G\u00e9rard Y (2009) About the complexity of timetables and 3-dimensional discrete tomography: A short proof of NP-hardness. In: Wiederhold P, Barneva RP (eds) Combinatorial Image Analysis. IWCIA 2009. Lecture Notes Comp Sci. Springer, Berlin, Heidelberg 5852; 289\u2013301. https:\/\/doi.org\/10.1007\/978-3-642-10210-3_23","DOI":"10.1007\/978-3-642-10210-3_23"}],"container-title":["Journal of Cheminformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13321-025-00958-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13321-025-00958-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13321-025-00958-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T14:37:07Z","timestamp":1750171027000},"score":1,"resource":{"primary":{"URL":"https:\/\/jcheminf.biomedcentral.com\/articles\/10.1186\/s13321-025-00958-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":88,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["958"],"URL":"https:\/\/doi.org\/10.1186\/s13321-025-00958-w","relation":{"has-preprint":[{"id-type":"doi","id":"10.26434\/chemrxiv-2024-41295","asserted-by":"object"}]},"ISSN":["1758-2946"],"issn-type":[{"value":"1758-2946","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]},"assertion":[{"value":"12 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 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 interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"97"}}