Найти самую часто встречающуюся подстроку заданной длины k в строке

Взял курс по биоинформатике на coursera. Есть задачка, которую я не могу решить. Смысл в том что у нас есть две переменные:
перечень букв в одно длинное слово, в котором есть повторяющиеся сочетания букв (напр.ACGTTGCATGTCGCATGATGCATGAGAGCT и CATG GCAT) Цифра которая задает количество повторяющихся букв(в примере выше задана цифра Надо узнать какое из сочетаний самое повторяющееся. Я нашел решение и не могу понять одну строку:
Count = CountDict(Text, k)
У меня выкидывает ошибку, а ее смысл как я понимаю в создании словаря.
# Input: A string Text and an integer k # Output: A list containing all most frequent k-mers in Text def FrequentWords(Text, k): FrequentPatterns = [] Count = CountDict(Text, k) m = max(Count.values()) for i in Count: if Count[i] == m: FrequentPatterns.append(Text[i:i+k] FrequentPatternsNoDuplicates = remove_duplicates(FrequentPatterns) return FrequentPatternsNoDuplicates

Ответ

Думаю, что биоинформатика подразумевает эффективное решение, т.к. строки генома могут быть очень длинными.
А одним из эффективных решений, особенно для больших k, в данном случае будет использование суффиксного массива в связке с определением наибольшего общего префикса двух соседних суффиксов (LCP). Построение суффиксного массива несложными средствами имеет сложность O(NlogN) или O(Nlog^2(N)). Есть и более сложные в реализации алгоритмы за линейное время.
Edit: В коде закомментирована краткая реализацию на Python c плохой асимптотикой. Заменил на реализацию алгоритма Manber-Myers отсюда (должна быть асимптотика O(NlogN), но, как я понял, реализация этого не обеспечивает для произвольных входных данных)
LCP строится за линейное время - я привел эффективный и простой алгоритм Kасаи.
После построения LCP нужно из него вычленить наиболее длинные серии, все элементы которых не меньше заданной длины k (думаю, на Python это делается одной строчкой). Время линейное.
Длина наибольшей серии соответствует (точнее - на единицу меньше) количеству повторов самой частой подстроки нужной длины. Для получения самой этой подстроки нужно взять подстроку, начиная с индекса из соответствующего элемента суффиксного массива.
#медленная реализация #def get_suffix_array(s): # return sorted(range(len(s)), key=lambda i: s[i:])
from collections import defaultdict
def sort_bucket(s, bucket, order): d = defaultdict(list) for i in bucket: key = s[i + order // 2:i + order] d[key].append(i) result = [] for k, v in sorted(d.items()): if len(v) > 1: result += sort_bucket(s, v, 2 * order) else: result.append(v[0]) return result
def suffix_array_ManberMyers(s): return sort_bucket(s, range(len(s)), 1)
def lcp_kasai(s, suffarr): n = len(suffarr) k = 0 lcp = [0] * n rank = [0] * n for i in range(n): rank[suffarr[i]] = i
for i in range(n): if (k>0): k -= 1 if(rank[i]==n-1): k = 0 continue j = sa[rank[i]+1] while((i+ksa = suffix_array_ManberMyers("ACGTTGCATGTCGCATGATGCATGAGAGCT$") print(sa) lc = lcp_kasai("ACGTTGCATGTCGCATGATGCATGAGAGCT$", sa) print(lc)
вывод суффиксного массива и lcp:
[30, 0, 24, 26, 21, 14, 17, 7, 20, 13, 6, 11, 1, 28, 23, 25, 16, 19, 12, 5, 27, 9, 2, 29, 10, 22, 15, 18, 4, 8, 3] [0, 1, 2, 1, 4, 3, 3, 0, 5, 4, 1, 2, 1, 0, 3, 2, 1, 6, 5, 2, 1, 2, 0, 1, 1, 3, 2, 6, 2, 1, 0]
в lcp мы видим два куска длиной два (это означает, что две подстроки встречаются трижды) со значением >=4: 5, 4 и 6, 5, начинающиеся на 8 и 17 позициях. Эти позиции в суффиксном массиве содержат индексы в исходной строке 20 и 19, чему соответствуют подстроки CATG и GCAT