Expediting protein structural analysis with an efficient kernel density estimation algorithm

We describe a kernel density estimation based mechanism aimed at expediting protein structural analysis. We have been motivated by the observation that many protein structural analysis algorithms suffer high time complexity, while only the residues and atoms on the contour of a protein are essential for determining the functions of the protein and how it could interact with the other proteins. Accordingly, for some protein structural analysis problems, it is desirable to invoke a mechanism that can extract the residues and atoms on the contour of a protein in order to expedite the analysis process. The conventional approach to carry out this task is to invoke the α-hull algorithm from computer graphics, which features O(n²) time complexity, where n is the number of residues or atoms in the protein. A kernel density estimation based expediting mechanism with an average time complexity of O(nlogn) is proposed. We also report the experiment conducted to evaluate the effects of applying the proposed expediting mechanism to a real protein structural analysis problem. Experimental results reveal that a speedup of 4.8 to 10.3 times can be achieved with minimum impact on the analysis accuracy.