Python extract common patterns of length X among a set of sequences

user_5455842 0
Viewed 93

Let's say I have the following :
data = ['ABCD', 'ABABC', 'BCAABCD']
I'm trying to make a function, that uses Counter taking three argvs, one for the data, second for the minimum proportion of the number of sequences that must have this pattern for being taken into account, and a third one that is the maximum pattern length.

A working function should gives me the following :

>>> check(data, 0.50, 2)
Counter({'A': 3, 'AB': 3, 'B': 3, 'BC': 3, 'C': 3, 'CD': 2, 'D': 2})

>>> check(data, 0.34, 4)
Counter({'A': 3, 'AB': 3, 'ABC': 3, 'ABCD': 2, 'B': 3, 'BC': 3, 'BCD': 2, 'C': 3, 'CD': 2, 'D': 2})

I'm really lost on this thing, I just know how to get the combinations thing for two or more letter like this :

Counter(combinations(data[0], 2)) & Counter(combinations(data[1], 2)) & Counter(combinations(data[2], 2))

And I also know how to get the sum of the letters in all elements of data with :

Counter(data[0]) + Counter(data[1]) + Counter(data[2])

(Strange thing, I couldn't manage to do this sum using list comprehension as I would've liked to do because of an error saying I can't do '+' between 'str' and 'int'

If you guys can't give me full code, no problem, I only need some guidance on how to start the whole thing and to get the logic.

Have a nice day to the one who read my whole thing :)
itertools counter sequence collections python
1 Answers

You can use a recursive generator function to get all combinations of the merged substrings (with length <= the maximum) in data and find the substring intersections using collections.defaultdict:

from collections import defaultdict
data = ['ABCD', 'ABABC', 'BCAABCD']
def combos(d, l, c = []):
   if c:
      yield ''.join(c)
   if d and len(c) < l:
      yield from combos(d[1:], l, c+[d[0]])
      if not c:
          yield from combos(d[1:], l, c)

def check(d, p, l):
   _d = defaultdict(set)
   for i in d:
      for j in combos(i, l):
         _d[j].add(i)
   return {a:len(b) for a, b in _d.items() if len(b)/len(d) >= p}

print(check(data, 0.50, 2))
print(check(data, 0.34, 4))

Output:

{'A': 3, 'AB': 3, 'B': 3, 'BC': 3, 'C': 3, 'CD': 2, 'D': 2}
{'A': 3, 'AB': 3, 'ABC': 3, 'ABCD': 2, 'B': 3, 'BC': 3, 'BCD': 2, 'C': 3, 'CD': 2, 'D': 2}
user_73267380
Related