KIT | KIT-Bibliothek | Impressum

Better partitions of protein graphs for subsystem quantum chemistry

Looz, Moritz von; Wolter, Mario; Jacob, Christoph R; Meyerhenke, Henning

Abstract: Determining the interaction strength between proteins and small molecules is key to analyzing their biological function. Quantummechanical calculations such as Density Functional Theory (DFT) give accurate and theoretically well-founded results. With common implementations the running time of DFT calculations increases quadratically with molecule size. Thus, numerous subsystem-based approaches have been developed to accelerate quantum-chemical calculations. These approaches partition the protein into different fragments, which are treated separately. Interactions between different fragments are approximated and introduce inaccuracies in the calculated interaction energies. To minimize these inaccuracies, we represent the amino acids and their interactions as a weighted graph in order to apply graph partitioning. None of the existing graph partitioning work can be directly used, though, due to the unique constraints in partitioning such protein graphs. We therefore present and evaluate several algorithms, partially building upon established concepts, but adapted to handle the new constraints. For the special case of partitioning a protein along the main chain, we also present an efficient dynamic programming algorithm that yields provably optimal results. In the general scenario our algorithms usually improve the previous approach significantly and take at most a few seconds.


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2016
Sprache Englisch
Identifikator DOI(KIT): 10.5445/IR/1000052814
ISSN: 2190-4782
URN: urn:nbn:de:swb:90-528140
KITopen ID: 1000052814
Verlag Karlsruhe
Umfang 20 S.
Serie Karlsruhe Reports in Informatics ; 2016,5
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page