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

#python #python_3x #алгоритм #биоинформатика

Взял курс по биоинформатике на 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


    

Ответы

Ответ 1

Думаю, что биоинформатика подразумевает эффективное решение, т.к. строки генома могут
быть очень длинными. 

А одним из эффективных решений, особенно для больших 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+k=4: 5, 4  и  6, 5, начинающиеся на 8 и 17 позициях. Эти позиции
в суффиксном массиве содержат индексы в исходной строке 20 и 19, чему соответствуют
подстроки CATG и GCAT


Ответ 2

Простой алгоритм в лоб: подсчитать количество вхождений для каждой [перекрывающейся]
подстроки длиной k, а затем вывести подстроку с наибольшим количеством повторений:

#!/usr/bin/env python
"""Find most common substring of length k."""
from collections import Counter

text = "ACGTTGCATGTCGCATGATGCATGAGAGCT"
k = 4

# count occurrences of all k-mers: words of length k in the text
words = Counter(text[i:i+k] for i in range(len(text) - k + 1))  # O(n*k)
print(words.most_common(1)[0][0])  #-> GCAT




k =  text =  


Ответ 3

text = 'ACGTTGCATGTCGCATGATGCATGAGAGCT'
key_len = 4

from collections import defaultdict, Counter
accumulator = Counter(text[i: i + key_len] for i in range(len(text) - key_len + 1))

print(accumulator)  # {'A': 7, 'C': 6, 'G': 9, 'T': 7,

max_items = defaultdict(list)

for k, v in accumulator.items():
    max_items[v].append(k)

print(max_items)  # ... , 2: ['TGCA', 'ATGA'], 3: ['GCAT', 'CATG']})

# Находим ключ с максимальным значением
max_key = max(max_items)
print(max_key, max_items[max_key])  # 3 ['GCAT', 'CATG']


Ответ 4

Попробуйте нечто вроде:

def CountDict(Text, k):
    # Создаём полный список всех подстрок длиной k
    if k > len(Text): return None
    if k == len(Text): return {Text:1}

    list_substr = list()   # Список подстрок длиной k
    for j in range(len(Text) - k + 1):
        list_substr.append( Text[j:j+k])

    # Список превращаем в словарь, с подсчётом частот
    RetMap = dict()
    for j in range(len(list_substr)):
        key_val = list_substr[j]
        RetMap[key_val] = RetMap.get(key_val, 0) + 1

    return RetMap

dnk_map = CountDict('ACGTTGCATGTCGCATGATGCATGAGAGCT', 4)
print(dnk_map)