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", }