<p>K Dimensional Tree (KD-Tree) data structure might help:</p>
<p><a href="https://www.biorxiv.org/content/10.1101/605907v2.full.pdf" rel="nofollow noreferrer">https://www.biorxiv.org/content/10.1101/605907v2.full.pdf</a></p>

CC BY-SA 4.0
2023-07-07T13:34:33.657Z
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](/help/how-to-answer).
Community
CC BY-SA 4.0
2023-07-07T04:39:52.797Z
2023-07-07T04:39:52.797Z
The August
<p>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 <a href="https://en.wikipedia.org/wiki/Cell_lists" rel="nofollow noreferrer">cell lists</a>, although that name is not as widely used as the method itself.</p>
<p>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 <a href="https://pdb101.rcsb.org/learn/guide-to-understanding-pdb-data/biological-assemblies#Anchor-Asym" rel="nofollow noreferrer">asymmetric unit</a>.</p>

CC BY-SA 4.0
2023-07-07T22:14:51.453Z
2023-07-07T22:14:51.453Z
marcin
<p>I need an algorithm to process protein chains. The volume size would probably not exceed 30x30x30 angstrom^3.</p>
<p>Say, I have a point cloud of 50,000 points in a 3D space.</p>
<p>I want to <strong>count</strong> the number of neighbors <strong>each</strong> point {(x<sub>1</sub>,y<sub>1</sub>,z<sub>1</sub>), (x<sub>2</sub>,y<sub>2</sub>,z<sub>2</sub>), (x<sub>3</sub>,y<sub>3</sub>,z<sub>3</sub>), ... ...,(x<sub>N</sub>,y<sub>N</sub>,z<sub>N</sub>)} has at radii {r<sub>1</sub>, r<sub>2</sub>, r<sub>3</sub>, ..., r<sub>M</sub>}.</p>
<p><strong>Which algorithm should I use?</strong></p>
<p><strong>Additional information:</strong></p>
<ol>
<li><p>Do you need to do this count online/sequentially or all at once?<br />
All once.</p>
</li>
<li><p>What restrictions might there be on the radii?<br />
The radii will be 4.0, 4.5, 5.0, 5.5, 6.0, 6.5, 7.0 angstrom.</p>
</li>
<li><p>Do you need to do this just once in this particular case or do you need a general algorithm?<br />
I will use this to process protein sequences. Not DNA/RNA, though.</p>
</li>
<li><p>For a general algorithm, what's the likely range of the number of points?<br />
The range would be 50,000 at max (although, the maximum length of available protein is 38,000 residues).</p>
</li>
<li><p>Are you expecting there to be relatively few or relatively many neighbors?<br />
I am expecting relatively few neighbors, in the range of 0-50.</p>
</li>
</ol>
<p><strong>NOTE:</strong> I prefer a hash-based algorithm as it doesn't require additional data structures like KD tree, or octree.</p>

<proteins><protein-structure><algorithms><3d-structure>
Algorithm for counting neighbors
# Algorithm for counting neighbors

(Asked by: username_0 on 2023-07-05)

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.

**Tags:** proteins, protein-structure, algorithms, 3d-structure

---

## 2 answers

### Answer by username_3 on 2023-07-07. Score: 4 | Accepted answer

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](https://en.wikipedia.org/wiki/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](https://pdb101.rcsb.org/learn/guide-to-understanding-pdb-data/biological-assemblies#Anchor-Asym).


---

### Answer by username_1 on 2023-07-07. Score: 0

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

<https://www.biorxiv.org/content/10.1101/605907v2.full.pdf>

> **Comments:**
> **username_2**: 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](/help/how-to-answer).  

---

