In [1]:

    

# A simple example of a substring index; mirrors example from lecture notes

# we're going to extract 4 substrings like this:
# t:           CGTGCCTACTTACTTACAT
# substring 1: CGTGC
# substring 2:     CCTAC
# substring 3:         CTTAC
# substring 4:             CTTAC
t = 'CGTGCCTACTTACTTACAT'


    

In [2]:

    

# From t, make list of pairs, where first pair item is substring, second is its offset
def substringize(t, ln, iv):
    # ln = length of substrings to extract
    # iv = distance between substings to extract; e.g. 1 means take *every* substring
    pairs = []
    # Loop below is like a Java/C loop saying: for(i = 0; i < len(t) - ln + 1; i += iv)
    for i in range(0, len(t) - ln + 1, iv):
        pairs.append((t[i:i+ln], i))
    return pairs
    # Could also have used list comprehension:
    # return [ (t[i:i+ln], i) for i in range(0, len(t) - ln + 1, iv) ]


    

In [3]:

    

substringize('CGTGCCTACTTACTTACAT', 5, 4)


    

    
Out[3]:





[('CGTGC', 0), ('CCTAC', 4), ('CTTAC', 8), ('CTTAC', 12)]

In [4]:

    

# Like substringize, but uses a map data structure
def mapize(t, ln, iv):
    index = {}
    for i in range(0, len(t) - ln + 1, iv):
        sub = t[i:i+ln]
        if sub in index:
            index[sub].append(i) # already have an entry; append to it
        else:
            index[sub] = [i] # don't yet have entry, make new one
    return index


    

In [5]:

    

index = mapize('CGTGCCTACTTACTTACAT', 5, 4)
index


    

    
Out[5]:





{'CCTAC': [4], 'CGTGC': [0], 'CTTAC': [8, 12]}

In [6]:

    

p = 'CTTACTTA'


    

In [7]:

    

# index: give me a hint where I should look for occurrences of p in t
index[p[:5]]


    

    
Out[7]:





[8, 12]