annotate altschulEriksonDinuclShuffle.py @ 2:e72172a0a429 default tip

Uploaded
author xuebing
date Sat, 31 Mar 2012 21:49:00 -0400
parents f9d894fb823c
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
1 #! /usr/bin/env python
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
2
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
3 # altschulEriksonDinuclShuffle.py
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
4 # P. Clote, Oct 2003
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
5 # NOTE: One cannot use function "count(s,word)" to count the number
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
6 # of occurrences of dinucleotide word in string s, since the built-in
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
7 # function counts only nonoverlapping words, presumably in a left to
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
8 # right fashion.
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
9
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
10
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
11 import sys,string,random
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
12
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
13
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
14
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
15 def computeCountAndLists(s):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
16 #WARNING: Use of function count(s,'UU') returns 1 on word UUU
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
17 #since it apparently counts only nonoverlapping words UU
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
18 #For this reason, we work with the indices.
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
19
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
20 #Initialize lists and mono- and dinucleotide dictionaries
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
21 List = {} #List is a dictionary of lists
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
22 List['A'] = []; List['C'] = [];
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
23 List['G'] = []; List['T'] = [];
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
24 nuclList = ["A","C","G","T"]
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
25 s = s.upper()
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
26 s = s.replace("U","T")
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
27 nuclCnt = {} #empty dictionary
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
28 dinuclCnt = {} #empty dictionary
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
29 for x in nuclList:
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
30 nuclCnt[x]=0
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
31 dinuclCnt[x]={}
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
32 for y in nuclList:
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
33 dinuclCnt[x][y]=0
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
34
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
35 #Compute count and lists
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
36 nuclCnt[s[0]] = 1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
37 nuclTotal = 1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
38 dinuclTotal = 0
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
39 for i in range(len(s)-1):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
40 x = s[i]; y = s[i+1]
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
41 List[x].append( y )
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
42 nuclCnt[y] += 1; nuclTotal += 1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
43 dinuclCnt[x][y] += 1; dinuclTotal += 1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
44 assert (nuclTotal==len(s))
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
45 assert (dinuclTotal==len(s)-1)
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
46 return nuclCnt,dinuclCnt,List
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
47
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
48
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
49 def chooseEdge(x,dinuclCnt):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
50 numInList = 0
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
51 for y in ['A','C','G','T']:
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
52 numInList += dinuclCnt[x][y]
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
53 z = random.random()
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
54 denom=dinuclCnt[x]['A']+dinuclCnt[x]['C']+dinuclCnt[x]['G']+dinuclCnt[x]['T']
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
55 numerator = dinuclCnt[x]['A']
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
56 if z < float(numerator)/float(denom):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
57 dinuclCnt[x]['A'] -= 1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
58 return 'A'
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
59 numerator += dinuclCnt[x]['C']
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
60 if z < float(numerator)/float(denom):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
61 dinuclCnt[x]['C'] -= 1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
62 return 'C'
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
63 numerator += dinuclCnt[x]['G']
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
64 if z < float(numerator)/float(denom):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
65 dinuclCnt[x]['G'] -= 1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
66 return 'G'
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
67 dinuclCnt[x]['T'] -= 1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
68 return 'T'
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
69
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
70 def connectedToLast(edgeList,nuclList,lastCh):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
71 D = {}
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
72 for x in nuclList: D[x]=0
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
73 for edge in edgeList:
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
74 a = edge[0]; b = edge[1]
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
75 if b==lastCh: D[a]=1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
76 for i in range(2):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
77 for edge in edgeList:
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
78 a = edge[0]; b = edge[1]
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
79 if D[b]==1: D[a]=1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
80 ok = 0
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
81 for x in nuclList:
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
82 if x!=lastCh and D[x]==0: return 0
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
83 return 1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
84
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
85
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
86
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
87 def eulerian(s):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
88 nuclCnt,dinuclCnt,List = computeCountAndLists(s)
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
89 #compute nucleotides appearing in s
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
90 nuclList = []
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
91 for x in ["A","C","G","T"]:
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
92 if x in s: nuclList.append(x)
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
93 #compute numInList[x] = number of dinucleotides beginning with x
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
94 numInList = {}
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
95 for x in nuclList:
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
96 numInList[x]=0
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
97 for y in nuclList:
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
98 numInList[x] += dinuclCnt[x][y]
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
99 #create dinucleotide shuffle L
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
100 firstCh = s[0] #start with first letter of s
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
101 lastCh = s[-1]
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
102 edgeList = []
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
103 for x in nuclList:
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
104 if x!= lastCh: edgeList.append( [x,chooseEdge(x,dinuclCnt)] )
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
105 ok = connectedToLast(edgeList,nuclList,lastCh)
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
106 return ok,edgeList,nuclList,lastCh
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
107
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
108
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
109 def shuffleEdgeList(L):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
110 n = len(L); barrier = n
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
111 for i in range(n-1):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
112 z = int(random.random() * barrier)
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
113 tmp = L[z]
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
114 L[z]= L[barrier-1]
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
115 L[barrier-1] = tmp
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
116 barrier -= 1
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
117 return L
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
118
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
119 def dinuclShuffle(s):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
120 ok = 0
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
121 while not ok:
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
122 ok,edgeList,nuclList,lastCh = eulerian(s)
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
123 nuclCnt,dinuclCnt,List = computeCountAndLists(s)
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
124
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
125 #remove last edges from each vertex list, shuffle, then add back
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
126 #the removed edges at end of vertex lists.
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
127 for [x,y] in edgeList: List[x].remove(y)
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
128 for x in nuclList: shuffleEdgeList(List[x])
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
129 for [x,y] in edgeList: List[x].append(y)
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
130
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
131 #construct the eulerian path
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
132 L = [s[0]]; prevCh = s[0]
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
133 for i in range(len(s)-2):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
134 ch = List[prevCh][0]
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
135 L.append( ch )
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
136 del List[prevCh][0]
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
137 prevCh = ch
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
138 L.append(s[-1])
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
139 t = string.join(L,"")
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
140 return t
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
141
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
142
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
143
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
144 if __name__ == '__main__':
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
145 if len(sys.argv)!=3:
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
146 print "Usage: python altschulEriksonDinuclShuffle.py GCATCGA 5"
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
147 sys.exit(1)
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
148 s = sys.argv[1].upper()
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
149 for i in range(int(sys.argv[2])):
f9d894fb823c Uploaded
xuebing
parents:
diff changeset
150 print dinuclShuffle(s)