bwt.py

bwt.py

import sys
import pdb

def bwt(s):
    """ Return the burrougs wheele transform and suffix array for string s
        based on Fig2 in Li & Durbin 2009 """
    table_rotation=[]
    # Table of rotations of string
    for i in range(len(s)):
        foo=s[i:]
        bar=s[:i]
        table_rotation.append(foo + bar)
        #pdb.set_trace()

    
    sorted_table= sorted(table_rotation)
    suffix_array= [ table_rotation.index(i) for i in sorted_table]
    bwt= [ sorted_table[i][len(sorted_table[i])-1] for i in range(len(sorted_table)) ]
    return (bwt, suffix_array)

    


def main():
    (transform, sa) = bwt('googol$')
    print transform
    print sa
if __name__ == "__main__":
    main()