I need an algorithm to process protein chains. The volume size would probably not exceed 30x30x30 angstrom^3.

Say, I have a point cloud of 50,000 points in a 3D space.

I want to count the number of neighbors each point {(x1,y1,z1), (x2,y2,z2), (x3,y3,z3), ... ...,(xN,yN,zN)} has at radii {r1, r2, r3, ..., rM}.

Which algorithm should I use?

Additional information:

  1. Do you need to do this count online/sequentially or all at once?
    All once.

  2. What restrictions might there be on the radii?
    The radii will be 4.0, 4.5, 5.0, 5.5, 6.0, 6.5, 7.0 angstrom.

  3. Do you need to do this just once in this particular case or do you need a general algorithm?
    I will use this to process protein sequences. Not DNA/RNA, though.

  4. For a general algorithm, what's the likely range of the number of points?
    The range would be 50,000 at max (although, the maximum length of available protein is 38,000 residues).

  5. Are you expecting there to be relatively few or relatively many neighbors?
    I am expecting relatively few neighbors, in the range of 0-50.

NOTE: I prefer a hash-based algorithm as it doesn't require additional data structures like KD tree, or octree.


2 Answers 2


The usual method is dividing the space into cells, in your case 7Å cubes, assigning atoms to cells, and searching for neighbors only in 3x3x3=27 cells. This method is described in Wikipedia as cell lists, although that name is not as widely used as the method itself.

If you analyze experimental protein structures note that they may have alternative conformations (alternative locations of the same atom), and that the structure in the file represents an asymmetric unit.


K Dimensional Tree (KD-Tree) data structure might help:


  • 1
    $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Jul 7, 2023 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.