#!/usr/bin/pythonimport csv;reader = csv.reader(open("data.txt", "rb"), delimiter='\t', quoting=csv.QUOTE_NONE);data=[]def checktype(s) : for func in ( float, str): try: n = func(s) return n except: pass return sfor row in reader: if(len(row)): data=data+[[row[0],[checktype(x) for x in row[1:]] ]];del data[0];# DELETE THIS ######## FOR TESTING ONLY #################################del data[8:]for i in range(len(data)) : print data[i][0];def printdist() : for i in range(len(distmat)) : outt=""; for j in range(len(distmat)) : outt = outt + ' %5.3f' % distmat[i][j] print outt;### END of DELETE ################################################################3# ToDo more data checking here## like delete genes with no data at all if there are any. #Now data is assumed sane. Each gene has an index in range(len(data)), i.#data[i][0] is gene name and data[i][1] are it's values.#store these indexes ina list of clusters later.#This function gives distance between 2 genes.def dist(a,b): if (len(a)!=len(b)) : raise ValueError( "a="+repr(a)+" b="+repr(b)+" do not have equal lengths"); for i in range(len(a)) : if(a[i]=='' or b[i]==''): a[i]=0.0; b[i]=0.0; return sum([(y-x)**2 for x,y in zip(a, b)])**0.5#Make a cluster using every gene's index. We will just store indexes here.clusters=[ [i] for i in range(len(data)) ];# These function gives distance between 2 clusters.# take a cluster of clusters and return a plain list.def decluster(A) : if (type(A)!=type([])) : return A; flag=0; for x in A : if (type(x)==type([])) : flag=1; if flag==0: return A; B=[] for x in A : if (type(x)==type([])) : B=B+decluster(x); else: B=B+[x]; return B;def cl_dist(i,j): x=decluster(clusters[i]); y=decluster(clusters[j]); return sum([dist(data[p][1],data[q][1]) for p in x for q in y])/(len(x)+len(y));#create cluster distance matrixdistmat=[];for i in range(len(clusters)): distmat.append([100.0]*len(clusters));for i in range(len(clusters)) : for j in range(i+1): distmat[i][j]=cl_dist(i,j); distmat[j][i]=distmat[i][j];# reduce the cluster using the algo till you have just one giant cluster.#printdist();while(len(clusters) >1) :# print clusters; mindist=100.0 min_i=0; min_j=0; for i in range(len(distmat)) : for j in range(i): if(distmat[i][j]<mindist) : mindist=distmat[i][j]; min_i=i; min_j=j; printdist(); print min_i,min_j; clusters[min_j]=[clusters[min_i],clusters[min_j]]; del clusters[min_i]; for j in range(len(distmat)) : del distmat[j][min_i]; del distmat[min_i]; #now correct the min_i entries. for i in range(len(distmat)) : distmat[min_j][i]=cl_dist(min_j,i); distmat[i][min_j]=distmat[min_j][i];### Done! Print the output!print clusters;#fancyprint for debugging and actually seeing the clustering in tree format. This was a huge waste of time but is neat. :)def fancyprint(list,padding=' '): print padding[:-1] + '+-'; #+repr(list); padding = padding + ' '; count = 0; for x in list: count = count+ 1; print padding + '|' if(type(x)==type([]) and len(x)==1 and type(x[0])!=type([]) ): x=x[0]; if(type(x)!=type([])): print padding + '+-' + str(x)+':'+ data[x][i]; else: if(count == len(list)): fancyprint(x, padding + ' '); else: fancyprint(x, padding + '|');fancyprint(clusters);