g_contacts: Fast contact search in bio-molecular ensemble data

Short-range interatomic interactions govern many bio-molecular processes. Therefore, identifying close interaction partners in ensemble data is an essential task in structural biology and computational biophysics. A contact search can be cast as a typical range search problem for which efficient algorithms have been developed. However, none of those has yet been adapted to the context of macromolecular ensembles, particularly in a molecular dynamics (MD) framework. Here a set-decomposition algorithm is implemented which detects all contacting atoms or residues in maximum O(Nlog(N))$O(Nlog\left(N\right))$ run-time, in contrast to the O(N²)$O\left(N^2\right)$ complexity of a brute-force approach.