Algorithms For Dummies

 Challenging Difficult Problems

generator = ["A"]*6

+["C"]*4+["G"]*2+["T"]*2

text = ""

seed(4)

for i in range(1000):

    shuffle(generator)

    text 

+= generator[0]

print(text)

frequencies = Counter(list(text))

print(frequencies)

CAACCCCGACACGCCTCCATAGCCACAACAAGCAAAAAAGGC ...

Counter({'A': 405, 'C': 292, 'T': 158, 'G': 145})

After making the data inputs ready to compress, the code prepares a heap data 

structure (see the “Performing specialized searches using a binary heap” section 

of  Chapter  7  for  details)  to  arrange  the  results  efficiently  along  the  steps  the 

algorithm  takes.  The  elements  in  the  heap  contain  the  frequency  number  of 

nucleotides, the nucleotide characters, and its encoding. With a log-linear time 

complexity, O(n*log(n)), a heap is the right structure to use to order the results 

and allow the algorithm to draw the two smallest elements quickly.

heap = ([[freq, [char, ""]] for char, freq in

         frequencies.items()])

heapify(heap)

print(heap)

[[145, ['G', '']], [158, ['T', '']], [405, ['A', '']],  

[292, ['C', '']]]

When you run the algorithm, it picks the nucleotides with fewer frequencies from 

the heap (the greedy choice). It aggregates these nucleotides into a new element, 

replacing  the  previous  two.  The  process  continues  until  the  last  aggregation 

reduces the number of elements in the heap to one.

iteration = 0

while len(heap) > 1:

    iteration 

+= 1

    lo = heappop(heap)

    hi = heappop(heap)

    print ('Step %i 1st:%s 2nd:%s' % (iteration, lo,hi))

    for pair in lo[1:]:

        pair[1] = '0' 

+ pair[1]

    for pair in hi[1:]:

---

CHAPTER 15