A binary space partition (BSP) tree was implemented in order to exploit the spatial coherency of atoms. It allows an accelerated search for neighbours. Such a BSP tree is incorporated in the tree module as a tree class. It holds attributes and methods that are needed to build and query the BSP tree. This is done on the fly while the protein object is initialised with a pdb file. All operations are done "under the hood" and more information can be reviewed in the pydoc documentation page of the p3d module.
BSP Tree perfermance increase vs classical approximation of distance
A performance test between classical distance approximation and the usage of the BSP tree was performed on 1000 protein structures. There, the hydrogen bond partners for non-protein compounds was evaluated. Each nitrogen or oxygen in a non-protein molecule, e.g. Lipids, ATP, FAD etc was queried about its surroundings in order to find the hydrogen bond partners. The x axis shows the amount of atoms in the protein structure, the y-axis shows the amount of atoms that were investigated about their protein surroundings and the color code is the performance increase in % (BSP Tree query vs
classical). It is worth pointing out that the classical
distance approximation is not calculating the distance directly but it tests recursively each dimension if the distance is below a threshold and breaks out of the loop if the distance is already bigger within one dimension.