{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T20:52:05Z","timestamp":1726433525069},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Numerous applications in Computational Biology process molecular structures and hence strongly rely not only on correct atomic coordinates but also on correct bond order information. For proteins and nucleic acids, bond orders can be easily deduced but this does not hold for other types of molecules like ligands. For ligands, bond order information is not always provided in molecular databases and thus a variety of approaches tackling this problem have been developed. In this work, we extend an ansatz proposed by Wang et al. that assigns connectivity-based penalty scores and tries to heuristically approximate its optimum. In this work, we present three efficient and exact solvers for the problem replacing the heuristic approximation scheme of the original approach: an A*, an ILP and an fixed-parameter approach (FPT) approach.<\/jats:p>\n               <jats:p>Results: We implemented and evaluated the original implementation, our A*, ILP and FPT formulation on the MMFF94 validation suite and the KEGG Drug database. We show the benefit of computing exact solutions of the penalty minimization problem and the additional gain when computing all optimal (or even suboptimal) solutions. We close with a detailed comparison of our methods.<\/jats:p>\n               <jats:p>Availability: The A* and ILP solution are integrated into the open-source C++ LGPL library BALL and the molecular visualization and modelling tool BALLView and can be downloaded from our homepage www.ball-project.org. The FPT implementation can be downloaded from http:\/\/bio.informatik.uni-jena.de\/software\/.<\/jats:p>\n               <jats:p>Contact: \u00a0anna.dehof@bioinf.uni-sb.de<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq718","type":"journal-article","created":{"date-parts":[[2011,1,19]],"date-time":"2011-01-19T01:29:49Z","timestamp":1295400589000},"page":"619-625","source":"Crossref","is-referenced-by-count":12,"title":["Automated bond order assignment as an optimization problem"],"prefix":"10.1093","volume":"27","author":[{"given":"Anna Katharina","family":"Dehof","sequence":"first","affiliation":[{"name":"1 Center for Bioinformatics, Saarland University, 66041 Saarbr\u00fccken and 2Chair for Bioinformatics, Friedrich-Schiller-University Jena, 07743 Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Rurainski","sequence":"additional","affiliation":[{"name":"1 Center for Bioinformatics, Saarland University, 66041 Saarbr\u00fccken and 2Chair for Bioinformatics, Friedrich-Schiller-University Jena, 07743 Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quang Bao Anh","family":"Bui","sequence":"additional","affiliation":[{"name":"1 Center for Bioinformatics, Saarland University, 66041 Saarbr\u00fccken and 2Chair for Bioinformatics, Friedrich-Schiller-University Jena, 07743 Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"B\u00f6cker","sequence":"additional","affiliation":[{"name":"1 Center for Bioinformatics, Saarland University, 66041 Saarbr\u00fccken and 2Chair for Bioinformatics, Friedrich-Schiller-University Jena, 07743 Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans-Peter","family":"Lenhof","sequence":"additional","affiliation":[{"name":"1 Center for Bioinformatics, Saarland University, 66041 Saarbr\u00fccken and 2Chair for Bioinformatics, Friedrich-Schiller-University Jena, 07743 Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Hildebrandt","sequence":"additional","affiliation":[{"name":"1 Center for Bioinformatics, Saarland University, 66041 Saarbr\u00fccken and 2Chair for Bioinformatics, Friedrich-Schiller-University Jena, 07743 Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2011,1,17]]},"reference":[{"key":"2023012511564754700_B1","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1107\/S0108768102003890","article-title":"The Cambridge Structural Database: a quarter of a million crystal structures and rising","volume":"58","author":"Allen","year":"2002","journal-title":"Acta Crystallogr. B"},{"key":"2023012511564754700_B2","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1089\/106652702760277336","article-title":"A combinatorial approach to protein docking with flexible side chains","volume":"9","author":"Althaus","year":"2002","journal-title":"J. Comput. Biol."},{"key":"2023012511564754700_B3","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of finding embedding in a k-tree","volume":"8","author":"Arnborg","year":"1987","journal-title":"SIAM J. Algebra. Discr."},{"key":"2023012511564754700_B4","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1021\/ci00009a001","article-title":"Automatic assignment of chemical connectivity to organic molecules in the cambridge structural database","volume":"32","author":"Baber","year":"1992","journal-title":"J. Chem. Inform. Comput. Sci."},{"key":"2023012511564754700_B5","doi-asserted-by":"crossref","first-page":"980","DOI":"10.1038\/nsb1203-980","article-title":"Announcing the worldwide protein data bank","volume":"10","author":"Berman","year":"2003","journal-title":"Nat. Struct. Biol."},{"key":"2023012511564754700_B6","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/978-3-642-02882-3_30","article-title":"Computing bond types in molecule graphs","volume-title":"Proceedings of Computing and Combinatorics Conference (COCOON 2009)","author":"B\u00f6cker","year":"2009"},{"key":"2023012511564754700_B7","doi-asserted-by":"crossref","DOI":"10.1007\/11841036_60","article-title":"On exact algorithms for treewidth","volume-title":"Technical Report UU-CS-2006-032","author":"Bodlaender","year":"2006"},{"key":"2023012511564754700_B8","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1021\/ci049645z","article-title":"Correct bond order assignment in a molecular framework using integer linear programming with application to molecules where only non-hydrogen atom coordinates are available","volume":"45","author":"Froeyen","year":"2005","journal-title":"J. Chem. Inf. Model"},{"key":"2023012511564754700_B9","first-page":"201","article-title":"A complete anytime algorithm for treewidth","volume-title":"UAI '04: Proceedings of the 20th conference on Uncertainty in Artificial Intelligence.","author":"Gogate","year":"2004"},{"key":"2023012511564754700_B10","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1093\/nar\/30.1.402","article-title":"LIGAND: database of chemical compounds and reactions in biological pathways","volume":"30","author":"Goto","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023012511564754700_B11","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1021\/ci050400b","article-title":"The blue obelisk-interoperability in chemical informatics","volume":"46","author":"Guha","year":"2006","journal-title":"J. Chem. Inf. Model"},{"key":"2023012511564754700_B12","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1002\/(SICI)1096-987X(199604)17:5\/6<490::AID-JCC1>3.0.CO;2-P","article-title":"MMFF VI. MMFF94s option for energy minimization studies","volume":"17","author":"Halgren","year":"1996","journal-title":"J. Comp. Chem."},{"key":"2023012511564754700_B13","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybernetics SSC4"},{"key":"2023012511564754700_B14","doi-asserted-by":"crossref","first-page":"774","DOI":"10.1021\/ci9603487","article-title":"BALI: automatic assignment of bond and atom types for protein ligands in the brookhaven protein databank","volume":"37","author":"Hendlich","year":"1997","journal-title":"J. Chem. Inform. Comput. Sci."},{"key":"2023012511564754700_B15","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1186\/1471-2105-11-531","article-title":"BALL - Biochemical Algorithms Library 1.3","volume":"11","author":"Hildebrandt","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023012511564754700_B16","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1021\/ci049714+","article-title":"ZINC\u2013a free database of commercially available compounds for virtual screening","volume":"45","author":"Irwin","year":"2005","journal-title":"J. Chem. Inf. Model"},{"key":"2023012511564754700_B17","doi-asserted-by":"crossref","first-page":"1623","DOI":"10.1002\/jcc.10128","article-title":"Fast, efficient generation of high-quality atomic charges. AM1-BCC model: II. parameterization and validation","volume":"23","author":"Jakalian","year":"2002","journal-title":"J. Comput. Chem."},{"key":"2023012511564754700_B18","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1093\/bioinformatics\/16.9.815","article-title":"BALL\u2013rapid software prototyping in computational molecular biology","volume":"16","author":"Kohlbacher","year":"2000","journal-title":"Bioinformatics"},{"key":"2023012511564754700_B19","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1021\/ci049915d","article-title":"On the perception of molecules from 3D atomic coordinates","volume":"45","author":"Labute","year":"2005","journal-title":"J. Chem. Inf. Model"},{"key":"2023012511564754700_B20","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0003-2670(92)85034-4","article-title":"Automatic assignment of bond orders based on the analysis of the internal coordinates of molecular structures","volume":"265","author":"Lang","year":"1992","journal-title":"Anal. Chim. Acta"},{"key":"2023012511564754700_B21","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1002\/(SICI)1097-0134(19981101)33:2<227::AID-PROT7>3.0.CO;2-F","article-title":"Exploring the conformational space of protein side chains using dead-end elimination and the A*algorithm","volume":"33","author":"Leach","year":"1998","journal-title":"Proteins"},{"key":"2023012511564754700_B22","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1093\/bioinformatics\/bti818","article-title":"BALLView: a tool for research and education in molecular modeling","volume":"22","author":"Moll","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012511564754700_B23","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1002\/prot.10232","article-title":"A new test set for validating predictions of protein-ligand interaction","volume":"49","author":"Nissink","year":"2002","journal-title":"Proteins"},{"volume-title":"Combinatorial Optimization: Algorithms and Complexity.","year":"1998","author":"Papadimitriou","key":"2023012511564754700_B24"},{"key":"2023012511564754700_B25","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF00355047","article-title":"PRODRG, a program for generating molecular topologies and unique molecular descriptors from coordinates of small molecules","volume":"10","author":"van Aalten","year":"1996","journal-title":"J. Comput. Aided Mol. Des."},{"key":"2023012511564754700_B26","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/j.jmgm.2005.12.005","article-title":"Automatic atom type and bond type perception in molecular mechanical calculations","volume":"25","author":"Wang","year":"2006","journal-title":"J. Mol. Graph. Model"},{"key":"2023012511564754700_B27","first-page":"247","article-title":"A tree-decomposition approach to protein structure prediction","author":"Xu","year":"2005","journal-title":"Proc. IEEE Comput. Syst. Bioinform. Conf."},{"key":"2023012511564754700_B28","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1089\/cmb.2007.0158","article-title":"Minimizing and learning energy functions for side-chain prediction","volume":"15","author":"Yanover","year":"2008","journal-title":"J. Comput. Biol."},{"key":"2023012511564754700_B29","doi-asserted-by":"crossref","first-page":"1379","DOI":"10.1021\/ci700028w","article-title":"Automatic perception of organic molecules based on essential structural information","volume":"47","author":"Zhao","year":"2007","journal-title":"J. Chem. Inf. Model"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/5\/619\/48865862\/bioinformatics_27_5_619.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/27\/5\/619\/48865862\/bioinformatics_27_5_619.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T12:37:18Z","timestamp":1674650238000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/27\/5\/619\/1745557"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,17]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq718","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"type":"electronic","value":"1367-4811"},{"type":"print","value":"1367-4803"}],"subject":[],"published-other":{"date-parts":[[2011,3,1]]},"published":{"date-parts":[[2011,1,17]]}}}