BA1E.py

def patternToNumber(pattern):
	if len(pattern) == 0:
		return 0
	return 4 * patternToNumber(pattern[0:-1]) + symbolToNumber(pattern[-1:])

def symbolToNumber(symbol):
	if symbol == "A":
		return 0
	if symbol == "C":
		return 1
	if symbol == "G":
		return 2
	if symbol == "T":
		return 3

def numberToPattern(x, k):
	if k == 1:
		return numberToSymbol(x)
	return numberToPattern(x // 4, k-1) + numberToSymbol(x % 4)

def numberToSymbol(x):
	if x == 0:
		return "A"
	if x == 1:
		return "C"
	if x == 2:
		return "G"
	if x == 3:
		return "T"

def computingFrequencies(text, k):
	a = [0] * 4**k
	for i in range(len(text)-k+1):
		pattern = text[i:i+k]
		j = patternToNumber(pattern)
		a[j] = a[j] + 1
	return a

def betterClumpFinding(genome, k, t, l):
	frequentPatterns = []
	clump = [0] * 4**k
	text = genome[0:L]
	a = computingFrequencies(text, k)
	for i in range(0, 4**k):
		if a[i] >= t:
			clump[i] = 1
	for i in range(1, len(genome)-l):
		firstPattern = genome[i-1:i-1+k]
		x = patternToNumber(firstPattern)
		a[x] = a[x] - 1
		lastPattern = genome[i+L-k:i+L]
		x = patternToNumber(lastPattern)
		a[x] = a[x] + 1
		if a[x] >= t:
			clump[x] = 1
	for i in range(len(clump)):
		if clump[i] == 1:
			frequentPatterns.append(numberToPattern(i,k))
	return frequentPatterns

g = "GAGCCAGAGCTGTTCTGATCATTTCACCACTGTTCGTTTTTAAATGCACAAGAATGGAAAGTTCCTCAACTCCTCAGACCTCGCAACCACTAATCCCGTGTGCCCGACTAGGTACTGCATTATGAGCGATGGGCAGAGACATGACTTGATGGTACAACCATATTCACCATGGTCAGTAGACAAGTGAGAAACTTAGTTACAGCCGTCATCGCGCTACCTTGTCGGACTGGCTTACTGGGGGTCCATCGACACTCCTACGAGCCCAAGCTATAGTAGTCGGCCCGGCCAATTGATTCAGCCGCTTGAGAGTGGAGGTCTGGCTGCCCCTGCGAGAGGCTTGCACATCGGATAGCGCCATCCCACCGGTTAGATCGGACGAACAAAGAGAGGAGCGCCCGCTTGTCCTTTTGATAGGAGGAACCCGATTACTACTACGTAACATATATTGTGACCAGCCCTCCGTGAACCAGCGTCTGGTCATGTGATCTTAAGGTATACTAGTACAAGATGTCCCGTTTGAGTCGTCCCCAACGACCTCGCTTGAGGGCTCTCCAGGGATTGCATCAGACCCAACAGAGGAGGTACGCCCGACAATGAGGAGTCAAGGTGCGGTGCTTGCGAACTAGAGGCCTTGGTCGCACCTCATACAATTTACGGCCCCGCTCCTTGGCAATCCTACATAGGAGCCAGCGGATATCCAATACAAAGCTAAGGAACAATACTATGGACCATCCTTGATAGTGTACTCTAATTATTCTTAGTTAGAAATAATGTTGCGCTGCTTAGGAGCGGCCTGGTTGAGTGAGGCCAGTTCTTCGCGGTAGAACACGCATTGAATTGAGTGAGGGTCAGGGATAGTTCGGCTTTGATGCGTAAGTAGTGAGTGAGGCTGAGTGAGGGCTTGACCGTGTGGATGAGTGAGGAGGTTGAGTGAGGTGAGTGAGTGAGGGAGGATAGACAAGATCTTACGGATGAGTGAGGGGATAAGTGAGTGAGGGAGGTGAGTGAGGCCGAAACGGGGTTTACTGAGTGAGGGATGAGTGAGGAGAGTAAGAAGTGAGTGAGGATGAGTGAGGTGAGTGAGGAGTGAGGAGGAGGGGTGAGTGAGGGAGGCGTCTCAATGAAGGTCCTGAGTGAGTGAGGATAGTTGATGAGTGAGGGTTTTGCGACCCTGATATGAGTGAGGCTTCTGGAGTGTCCTCCCTTCGACGACCATATGTAGAACACACCGCGAACAGAGTACGATGTCTACCCACAGCCCCGGCCGCGAATCCGCATTCATGAGTTGAGTGAGGTGAGTGTGAGTGAGGCCATTAACAACGCGACAAATAGCAAAACAAAACAACGCGCGCTCACAACATTGAGTGAGGAACAACGCGTTGAAATGCGGGTAGATTCTGCTTAAACAACGCGTGCGGGTGACGGTATTAAAATGCGAACAACGCGTTACTGAACAACGCGGCGTGAACAAAACAACGCGGAACAACGCGACAACAACAAAACAACAACGCGCAACGCGTGGTAACAACGCGGGTCCGCGACAACAACGCGCCCGACCCCAACAACGCGAACAACGCGTGCAATGCAACAACGCGCAAACAACGCGTGAATTAACAACGCGTTTGCCTTCGAATGCGCTGTTCCAGCAAAACAACGCGTAACAACGCGCACAATGCGGGTTGCACTTCGCTTGTATACATGGAGCTCATCGATAAATGCGGGAACAACTTCGCTTCGCTTAAGAAATGCGGGTCACTTCGCTTGAGATGAACAACGCGGCACTTCGCTTACTTCGCTTAACGCGATACTACTTCGCTTTCGCTTGCGACAACTTCGCTTTACTTCGCTTCGCTTGTCCTGTTTGTCCTGAATAACAACGCGTTAACTTCGCTTAACGCGTAGTCGTGAATGCACTTCGCTACTTCGCTTGGAACTTCGCTTTCGCTTTAACTTCGCTTATCAGTAGTACAGGGGATAAACAGGGGATAGGGTCAGGGGATAAGGGGATAGACTTCGCTTCTACTTCGCTTCGCAGGGGACTTCGCTTGACCCGGACTTCACTTCGCTTGATAAGCAGGGGATAAGGGGATATATCAGACTTCGCTTGGGGACTTCGCTTGCCGGGCCGGGGACTTCGCACTTCGCTTACCCGGTACCCCCGGCCGGGCCGGGGAACTTCGCTTTCGCTTCGGGCCCGGGCCGGTAGGATACACCCCGGGACTTCGCTTCCCGGTCCACACTTCGCTTGGACTTCGCTTTCACTTCGCTTATACGCACACAAGGACCCGGGCCGGGGGCCGGACCGAAGCAAACCCCAGGGGATAGCCGGGCCGGAATGTACACTATGTACACTTCCATCGACCGCCGGCCATGTACATGTTCCATCGACATGTCCATCGACACATCCATCGACCACTCCCGGTCGCGCCGGGCCATGTACACTGCCGGGCCGTCCATCGACCCGGCTTCCGGGCCGGGATGTACACTCTCCATCGACCGGGCCGGCGATCCATCGACGATGATAATGTACATCCATCGACGGCCTCCATCGACCGACCACTGAATCTGCCCGGCCGGTCCATCGACCGACCACTGCTAACCGGGCCGGCCCCGATGTACACTGTATGTACACTCCTTATTCCATCGACTCCATCGACCCAGGTCCATCGACTTGCTGCTTCCCATGTATGTACACTGTCCATCGACACTCTTACGATGTACACTCCGCTTCCATCGACACCATCGACATCGACCACTATTGGAATGTCCATCGACGTACACTATCCATCGACTATCCATCGACGTATGTACACTTGCAAGATTCCATCGACCCTTAAACAATCCTTCCATCGACATTTCCATCGACATCGACACCCTTAAACTCCATCGTCCATCGACCCCTTAAACCTTCTCTCCCGCTTTGTACCAAATGTCCTCCATCGACTTCCTCCTTAAACACCGTTATTTGCTCCACCCAACTTCTTCCTTATCCTTAAACCCTTAAACCCTAGGTGCTAGGCCTACGCGTAGGCGTCTCCTTAAACCCTTATCCTTAAACTACTCCTTAAACATCCTTAAACTCTCCTTAAACATCTCTTCCTTATCCTTAAACATTTCTTCCGACGTTAGCAAATTTCCTTAAACTTCCGACGACAGGCCGTAAGCACTTCCGACGTCACCATGCCCTTCCGACGGACCATCGTCCTTAAACACGACGCTCCTTAGCGGATGGCAAGCCCTTCCTTAAACTCCGATCCTTAAACCTCTCTTCCGACGCTTCCGACGTAATCCTTAAACCGCACTACTTCCGACGTACTCCTTTCCTTAAACCCTTTCCTTAAACATCGTTTCCACCTTCCGACGGCTTGTAATTTATCTTCCTTAAACGCTCCTTAAACACAACCGCACTTCCGACTCCTTAAACGCGGAAGGCGCTAAGACTTCCGACGCTCAGAATTCTTCCCTTCCGACGTAACTCTTCCGACGGAGATCTGTCTTCCGACGCTTCCGACGGCGATTGGATCTTCCCTTCCGACGTTCCGACGTGCGAATGGGTCGACACTTCCCTTCCGACGAAGTAAGTGGAGCGCTCAAGTGGAGCTGGAGCAAGTGGAGCCGGGAGAGAATTACTGGATTCGAAAAGTGGAGCCAAAGTGAAGTGGAGCGGCTAAAGTGGAGCACGAAGTGGAAGTGGAGCTGCCCAGCAAGTGGAGCAGTGGAGCTAAGTTAGTGGGACAGCCATGTATAATAACTTAACGCCTAAGTGGAGCATAAGTGGAGCGAGCCTCAGATCAACCTAAGTGGAGCGTAAGTGGAGCTCCGAGGAAATATAAAAGTGGAGAAGTGGAGCCAAGTGGAGCCGTGGTGTACTGCAAGTGGAGCGAGCTCGATAACGCGAGACCTCAACGCAAGTGGAGCACGAAGGCTTGATCGAAAGTGGAGCCCAAAGTGGAGCAAAGTGGAGCTCATCCCTAAAGTGGAGCCCCGCCGACTGTTTCTTCAGCCGAAGTGGAGCCAAGTGGAGCTCAAAGTGGAGCAAAGTGGAGCTAGGGGGGTAAATTGCAAGTGGAGCTCCATGTTTGAAATAGATGCGTTAGGTCTCTTGAGATGCTGTAGAAATGGCTACACTGTGCCTAAGTATAAGTGGAGCGGTGCTAAAGTGGAGCACGGGAGAGGTACTCATTTACACGAAGTTAGGCCTGTTATGACAGATTCGTCCGATGCCTAGGCACCACTGACCAAGGTTAGAAGCCAAGCGATGACTGAATGACAGAGTATAATCTCGTCATGTACCGGGTACCCGTTAGTTAGCTGCTGGCCGGCCTGTGAATAATCAGGCTGCCCGTTATCTATTCCGGAATATCTAGTTACCGCCTGACATCCAATGGCCAAGAAGTAGGTATCTAATAGGGATTATTCCTGGCGAAATTCCCATGAGGTATCCGATAGGTCCCTACGGTGAACGTCCCAGATAGCCTTGCGTGCCAGCGCGCCAGCGCCGTCATGCCAGCGCCCAGCGCAGCGCTATTCAGTGCCAGCGCGGCCTTCTGATACCATCTGCCAGCGCCCAGTGCCAGCGCTCATTGCCAGCGCCCTGCCAGCGCTGCCAGCGCGGAGTTATTCATCACTGCCTGCCAGCGCGTACCCTGACAACTGCCAGCGCGCATGAATGCCAGCGCCTCTGCCAGTGCCAGCGCGCCAGCGCTATGCCAGCGCGAGAGCCGCACCTCCGGAGTCATAAGTGCCAGCGCGCTAGTTTGCCAGCGCGCAGCCGGAGTGGCCGTCGGTACTTGCCAGCGCGATAATTTACTGTCCTCTTCTGCCAGCGCCTGCCAGCGCGCAAGATGAGCCCTTTAAGTGCCAGCGCTAATGTTCTGCCTACAAGCGTACAACCTGCCAGCTGCCAGCGCCGCCAGGTGCGGAACCATGCCATGCCAGCGCGTATACCTTCGTCGGTGCCAGCGCAGCGCGCACTTTCCCGGCAAAAAATGTAGGGTAAGTCAAAAGGGAGTGTACTGGAGACTATATGTGTGCCAGCGCTGTTCCGAAGCAATGGCGGTGATGGAACCTTTGATGATGAGCATGATTACCAATCCCACATGCGGTGAGGAAGCGCCCGTTGGATACGAGCTTGTCTCCGTTCTAATCCCGGGTATATGGATCCCCTAGATCCAGTAGGCGTGCGTGCAATCTAGTCAACGTCGTTGTCGGGTCCTCCGCGCCGCACTTTCGATTAACGCTCCGCGACTGCGACAGTTCGTCGTTCGTTTTTGCCGCGGCCACGCTTGTCCGGCTCTAAGAATACGTTACACTGTCTAAGTTTCTGCATTTATAAGTTCTGTGTAAGTGGGCCCTCGAATTGAGGTGGCTGGTCTCTGTGTAATAAACCTTATTGTCTGTGTAACCAAACCTGGGTTTCTTACACCAGCTCTGTCTGTGTAACGTGGTTCTGTGTAATAGGTAGGATCCTCTGTGTAAATCTGTGTAACTTGTAGCTCTGTGTAAATTGTCCATCTTCTGTGTAATGTGTTCTGTGTAACTTGTCTGTGTAAGCTGGCATCTGTGTAAGGAGATAAGTAGTCCAAAACCCCCCCCGCCCGTTTTCTGTGTAAGTCTGTGTAAACGGAAGTCTTCATATACGTCCCAACAGTCTGTGTAATCTGTGTAAGTCTGTGTAACTGTGTCTGTGTAAGTGGTCTGTGTATCTGTGTAATCCGAGTCTGTGTAACTGTGTATCTGTGTAAGCTTGTGAAGTCCACTCCGGTATGCTAGGTGTCTGTGTAAGTTGTTTATTCAGTACGCCTCCTCTGTGTAAGTGTAATGAACCAGGGCGCAGCAATTCTGTGTAAAACTCTGTGTAATACCGGACACTTAGGGTGGAAAGACCTTGGAAATCATGACCACAGGACAAGGCGTTTGGGAGATCTCGTATATTTTTTACGATGTTTACCCACTTCGGGATACGCTGTTCACCTCTGCAAGCTCGGGCTCACCCCTTAATGCTCGGGCTCTTTCCTACATTCGGGTGTGATCGTTGCTCGGGCTGCCGCTGGCATCGCCACAACTTTCGCTCGCTCGGGCTGCGAACCCCAACCATTAGTATTCCCGCTCGGGCTACGATGAAACGAGACCTAAACGCAAATCAGCAATAGCCGACCCTGCTATTCGGGAGGTCACATCTGTTCTAATATCTGCGAGGATGTGCTCGGGCTGGATGCGGGTGTGCAGCTCGGGCGCTCGGGCTGGCTTTCCTACACTGCGAGGAGTTTGGGCGCTCGGGCTGCTTCATCCGCTCGGGCTCGACTGCGAGGCTCGGGCGCTCGGGCTCTGCTCGGGCTGCTCGTCCGGCTCGGGCTCGGGCTTATCGCTCGCTCGGGCTCTCGGGCTGGATAAAACAGTACGCGAGAAGGAGCACTGCGAGGCTGCGAGGAGAGGACCTTCTATCTCTGGCTCGGGCTCGCTCGGGCTTTCTGCGAGCTCGGGCTTCGGGCTCATCTGCGAGCTCGGGCTGGCTACTGCGAGCTCGGGCTATCTCAGCTCGGGCTTCGGGCTGCGAGGAAGGACGGATGCTGCGAGGAGGAAAAAACACTGAATGATCCCTGCGAGGAATTCTGCGAGGAGCATCAGACTGCGAGGAGAGCCGGCCTCAGATTATTAGGAAGATGCGGGGTGCTGCCTGCGAGGAAAGTTATGTGTGGCAGCGAGACCGGTAGAGGAGGCTGCGAGGAATTGACGATACTGCGAGGACCTGAATTGCACTGCGAGGAGAGGAAGTCTGCGAGGAGCATAGGTTCTAATTGATGTGTAGCGTTAATCACTGTCGGTGAATCTGTCAACTCTATACGCGACGTATGTGCACTAAAAACCAGAGATCGATTGAAAGATGGCTCGTTGCCACCCAGGTAAATTGCTAACGGTACCAAATCGCCACAGATGGTTTGACTCCCATCTCCCACGCCATCGGTAATAGAGTGGCGTCTTAAATACTCTGACTAGCGTCCCACCCGAATGGGATCGGCGAGGAGGCGTTAGTTAGACTACCCACCGGTAAGCCTCAGGAACCGTTACTGACGTTAATGGTTTCTCCTCCACTTAACCATAAAGTGCCCAGACAATCAGATCGGCACCACAACCACGAATGCTATACGACTGTCTGCACCCTAAGTGTAAGTCCTACAGACACCCTTTTCATCCTCATGTGAGATCACCGATATAAGTGGTCTGGATAGCAAATATGGGCGAATGCTCCTGAAGTTGCTGTCCCTTTTCGTCTTGGTGATGCGCGTCCGCGGGAGAAACGTATAAGATCTTCTCATGCGTTAAATCCTTTCGGGCACCCGAAATGTATGCATTCCGAGTCGTAGGCCTGCCGGCTCCCATCTTATTTAGAGGGGAAAAGAACCCATGTCCCATTGTGAAACTCTATAATTAATGCGCTCGGATCAGCATTAACTCGTTAGCTCGTATGCCTCTGCTATCACGACTATAATGCTCAATACCTAGCTGGACATTGTACATATCGTCGTTGTAAAGAAGCGATCACACTCTTGAATGAATACGTGGCTATAGCGCAACAGACTCAAGTCGCCTTCTTATTGGTACGCTGGGAGACCCCGACGATTCAGCCTAAACAATCATACTTAGCTCTTTTCTTATTCGGCCAGGTTGGGTTAACACTATAGAGACGTGTTTTGCTGCAAGATAGCCTAGCTATCGAGATTAAAAGCCTTTAAACTCTTCCTCCTATCGTCCGATGCCGTAATTACACTCCCCTGTGGCGACGGATAGCTCCGGCTACGTACCGGCAGAGGATTTAAACAGTGACCTATGGTACATAGGGAAGGCAGTGTGCCAAAAGACGCGGATGCATCCGTAGCAGACGCGGGTTACCCTTACTGGCATTTGATTAGGTTCGAATGAGCTGTCAAGCCGTCGTGTTAAGATAAGCGGCACGGCTACCATGTGTGTGTAACAAGTTCATTTAATACGGCGATAGCCGTTCAGAATTACTGGAGCGCTTTACACACAAACAACCCATAAGACCCCATTATTAGCAAAGCTCGGTCCAAAGCCCAACAGAGTTAGCGGTAGGTGTCACGAACTGCACGAATTCGCGTCTGGACCCTGACTTTCTTTTAAATAATAGTTCTCAGTAGGCTCAGATAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGTAAGATCCGT"
k = 9
L = 564
t = 20

a = betterClumpFinding(g, k, t, L)

p = ""
for i in a:
	p += i + " "

print(p)