0

I am new to Python and I am looking for an example of a naive, simple single linkage clustering python algorithm that is based on creating a proximity matrix and removing nodes from that. I know that there are packages such as numpy but I would rather avoid them.
I have searched online but couldn't find any code simple enough to be able to understand in order to replicate it myself afterwards.

Begin with the disjoint clustering having level L(0) = 0 and sequence number m = 0.

Find the most similar pair of clusters in the current clustering, say pair (r), (s), according to d[(r),(s)] = min d[(i),(j)] where the minimum is over all pairs of clusters in the current clustering.

Increment the sequence number: m = m + 1. Merge clusters (r) and (s) into a single cluster to form the next clustering m. Set the level of this clustering to L(m) = d[(r),(s)]

Update the proximity matrix, D, by deleting the rows and columns corresponding to clusters (r) and (s) and adding a row and column corresponding to the newly formed cluster. The proximity between the new cluster, denoted (r,s) and old cluster (k) is defined as d[(k), (r,s)] = min d[(k),(r)], d[(k),(s)].

If all objects are in one cluster, stop. Else, go to step 2.

These are the steps as described in wikipedia. I have created the distance matrix but not sure how to proceed form there.

This is what I have so far:

comparing

def comparison(protein1, protein2): 

  l = [i for i in range(len(protein1)) if protein1[i] != protein2[i]] 

  return len(l)

creating the matrix

def matrix (r1,r2):

  r = [] 
  for p1 in proteins: 
    r2 = [] 
    for p2 in proteins: 
      r2 += [comparison(p1, p2)] 
    r += [r2] 
  return r

These are the sequences I am trying to compare:

seqlist = { "Human": "MGDVEKGKKIFIMKCSQCHTVEKGGKHKTGPNLHG", "Chimpanzee": "MGDVEKGKKIFIMKCSQCHTVEKGGKHKTGPNLHG", "Western tarsier":"MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGXNLHG", "Mouse": "MGDAEAGKKIFVQKCAQCHTVEKGGKHKTGPNLWG", "Rabbit": "MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHG", "Dog": "MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHG", "Pig": "MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHG", "Snapping turtle":"MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLNG", "Alligator": "MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHG", "Honeybee": "AGDPEKGKKIFVQKCAQCHTIESGGKHKVGPNLYG", }

4
  • This question appears to be off-topic because it is a request for example code
    – jonrsharpe
    Commented Mar 13, 2014 at 22:54
  • Sorry, I have done the first part my self, creating the matrix, but dunno how to rpoceed from there. Is there a better way to rephrase it? Commented Mar 13, 2014 at 23:00
  • 1
    @kapoios_kanateris Since you've already written part of the solution to this problem, you should post it on this page. Then we can figure out what still needs to be done. Commented Mar 13, 2014 at 23:17
  • Just added everything I have done so far. Commented Mar 13, 2014 at 23:35

1 Answer 1

2

You should look at the package scipy which has several hierarchical clustering algorithms implemented (see scipy.cluster.hierarchy). Look for the function pdist in the scipy.spatial module.

You should be able to get lots of nice usage examples from there.

See http://docs.scipy.org/doc/scipy/reference/cluster.hierarchy.html

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.