Skip to content

Instantly share code, notes, and snippets.

@nrshrivatsan
Created July 8, 2015 03:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nrshrivatsan/b7f8aae887c22eef1d24 to your computer and use it in GitHub Desktop.
Save nrshrivatsan/b7f8aae887c22eef1d24 to your computer and use it in GitHub Desktop.
Burrow Wheeler Transform in Python - a simple implementations
def rot(x):
k = x[0:len(x)-1]
k = x[len(x)-1]+(k)
return k
x = "UnitedStatesOfAmerica"
k = x
rotations = []
rotations.append(k)
for i in range(len(x)):
if i is 0:
continue
else:
k = rot(k)
rotations.append(k)
#Sorting rotations
rotations = sorted(rotations)
bwtransform = ''
#Creating BW Transform
for i in range(len(rotations)):
bwtransform+=rotations[i][len(x)-1]
#Printing BW Transform
print 'Burrow Wheeler Transform of '+k+'\n\t'
print bwtransform
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment