Automated bond order assignment as an optimization problem.
BACKGROUND
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.


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.


BACKGROUND
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/.
Center for Bioinformatics, Saarland University, Saarbrücken, Germany. anna.dehof@bioinf.uni-sb.de
Anna Katharina
AK
Dehof
Alexander
A
Rurainski
Quang Bao Anh
QB
Bui
Sebastian
S
Böcker
Hans-Peter
HP
Lenhof
Andreas
A
Hildebrandt
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D006860:Hydrogen Bonding; D008024:Ligands; D016014:Linear Models; D008968:Molecular Conformation; D009696:Nucleic Acids / Q000737:chemistry; D011506:Proteins / Q000737:chemistry
D008024:Ligands; D009696:Nucleic Acids; D011506:Proteins