Subscribe to Syndicate

Automated Bond Order Assignment as an Optimization Problem

Abstract: 
Numerous applications in Computational Biology process molecular structures and hence require not only reliable atomic cordinates, but also correct bond order information. Regrettably, this information is not always provided in molecular databases like the Cambridge Structural Database or the Protein Data Bank. Very different strategies have been applied to derive bond order information, most of them relying on the correctness of the atom coordinates. We extended a different ansatz proposed by Wang et al. that assigns heuristic molecular penalty scores solely based on connectivity information and tries to heuristically approximate its optimum. In this work, we present two efficient and exact solvers for the problem replacing the heuristic approximation scheme of the original approach: an ILP formulation and an A* approach. Both are integrated into the upcoming version of the Biochemical Algorithms Library BALL and have been successfully validated on the MMFF94 validation suite.
Journal: 
Proceedings of GCB 2009, Lecture Notes in Informatics 2009
Publication Date: 
30 Sep 2009
Citation: 
[DRL+09] Dehof, A. K., Rurainski, A., Lenhof, H.-P., and Hildebrandt, A.: Automated Bond Order Assignment as an Optimization Problem. Proceedings of the German Conference on Bioinformatics (GCB), Lecture Notes in Informatics, 2009.