-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathwinnowed_minimizers.py
executable file
·97 lines (69 loc) · 2.71 KB
/
winnowed_minimizers.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#!/usr/bin/env python3
from collections import deque
# winnowed_minimizers--
# Yields a sequence of (v,ix) pairs; v is a minimizer value, ix is it's
# location in perm.
#
# note: we expect values in perm to be unique
def winnowed_minimizers(perm,windowSize,circular=False):
if (circular):
for mini in winnowed_minimizers_circular(perm,windowSize): yield mini
else:
for mini in winnowed_minimizers_linear(perm,windowSize): yield mini
def winnowed_minimizers_linear(perm,windowSize):
# note: we expect values in perm to be unique
# note: we treat perm as a linear sequence
# note: if len(perm) < windowSize, no minimizers will be reported
history = deque() # ordered oldest (front) to most recent (back)
# this will contain (value,position) pairs
minimizers = set()
for ix in range(len(perm)):
windowIx = ix - (windowSize-1)
v = perm[ix]
# (at the back) remove anything worse than the current value
while (len(history) > 0) and (history[-1][0] > v):
history.pop()
# push the current value and its position to back of the queue
history.append((v,ix))
# (at the front) remove any minima that are no longer in the current
# window
while (len(history) > 0) and (history[0][1] < windowIx):
history.popleft()
# copy the minimizer from window, but only if we are seeing it for
# the first time
if (windowIx >= 0) and (len(history) > 0):
vHistory = history[0]
if (vHistory not in minimizers):
yield vHistory
minimizers.add(vHistory)
def winnowed_minimizers_circular(perm,windowSize):
# note: we expect values in perm to be unique
# note: we treat perm as a circular sequence
history = deque() # ordered oldest (front) to most recent (back)
# this will contain (value,position) pairs
minimizers = set()
for ix in range(len(perm)+windowSize-1):
windowIx = ix - (windowSize-1)
wrapround = (ix >= len(perm))
v = perm[ix] if (not wrapround) else perm[ix-len(perm)]
# (at the back) remove anything worse than the current value
while (len(history) > 0) and (history[-1][0] > v):
history.pop()
# push the current value and its position to back of the queue
history.append((v,ix))
# (at the front) remove any minima that are no longer in the current
# window
while (len(history) > 0) and (history[0][1] < windowIx):
history.popleft()
# copy the minimizer from window, but only if we are seeing it for
# the first time
if (windowIx >= 0) and (len(history) > 0):
vHistory = history[0]
seenBefore = (vHistory in minimizers)
if (not seenBefore) and (vHistory[1] >= len(perm)):
vHistory2 = (vHistory[0],vHistory[1]-len(perm))
if (vHistory2 in minimizers):
seenBefore = True
if (not seenBefore):
yield vHistory
minimizers.add(vHistory)