title: Clustering structural 3D data
body: <p>Let's say I have a number of objects (similar to proteins, but not exactly), each of which is represented by a vector of n 3D coordinates. Each of these objects is oriented somewhere in space. Their similarity can be calculated by aligning them using the <a href="http://en.wikipedia.org/wiki/Kabsch_algorithm" rel="nofollow noreferrer">Kabsch Algorithm</a> and calculating the root-mean-square deviation of the aligned coordinates.</p>
  
  <p>My question is, what would be the recommended way of clustering a large set of these structures in such a fashion as to extract the most populated cluster (i.e. the one to which most structures belong). Also, is there a way of doing this in python. By way of example, here's a trivialized set of unclustered structures (each is represented by the coordinates of the four vertices):</p>
  
  <p><img src="https://i.stack.imgur.com/WEK0s.png" alt="enter image description here"></p>
  
  <p>And then the desired clustering (using two clusters):</p>
  
  <p><img src="https://i.stack.imgur.com/QiAK1.png" alt="enter image description here"></p>
  
  <p>I've tried aligning all of the structures to a reference structure (i.e. the first structure) and then performing k-means on the distances between the reference and aligned coordinate using <code>Pycluster.kcluster</code>, but this seems a little bit clumsy and doesn't work so well. The structures in each cluster don't end up being very similar to each other. Ideally this clustering wouldn't be done on the difference vectors, but rather on the actual structures themselves, but the structures have dimensions (n,3) rather than the (n,) required for k-means clustering.</p>
  
  <p>The other option I tried is <code>scipy.clustering.hierarchical</code>. This seems to work pretty well, but I'm having trouble deciding which cluster is the most populated since one can always find a more populated cluster by moving up to the next branch of the tree.</p>
  
  <p>Any thoughts or suggestions or ideas about different (already implemented in python) clustering algorithms would be greatly appreciated.</p>