Как найти частую подпоследовательность пар оснований заданной длины

Question

Найти наиболее частую подпоследовательность пар оснований заданной длины. При условии, что задана строка и длина

Пример:

>>> most_freq_seq("AAGTTAGTCA", 3)
"AGT"

Может кто-нибудь объяснить, что означает «подпоследовательность базовой пары»?

Answer 1

Вы можете использовать класс Counter из коллекции в сочетании с zip для получения подпоследовательностей:

from collections import Counter
def most_freq_seq(seq,count):
    counts = Counter("".join(s) for s in zip(*(seq[i:] for i in range(count))))
    return counts.most_common(1)[0]

output:

r,c = most_freq_seq("AAGTTAGTCA", 3)

print(r,c)
# 'AGT' 2

Я знаю, что последовательности ДНК очень длинные, но я верю в это даст результаты в разумные сроки.

Для последовательности из 10 миллионов записей я получаю результат примерно за 3 секунды, используя случайные данные:

import random
import time

sequence = "".join(random.choice("ACGT") for _ in range(10_000_000))
size     = 7

start = time.time()
seq,count = most_freq_seq(sequence,size)
print(seq,count,time.time()-start)

# CCCAATT 704 3.12

Answer 2

В этом коде при нулевом повторении будет отображаться 1-й номер последовательности. его можно изменить, отредактировав вторую строку кода в most_seq = "no repeattiotion" или в что-то

def most_freq_seq(sequence,seq_len):
    most_seq = sequence[0:seq_len]
    number = 1
    for i in range(0,len(sequence)-seq_len):
        val = sequence.count(sequence[i:i+seq_len])
        if val > number :
            number = val
            most_seq = sequence[i:i+seq_len]
    print(most_seq)

most_freq_seq("AAGTTAGTCA",3)

Answer 3

Вводимый вами фрагмент ДНК. Каждая буква соответствует одной из четырех «пар оснований»: https://en.wikipedia.org/wiki/Base_pair

Следовательно, «подпоследовательность пар оснований» представляет собой просто подстроку, то есть строку меньшего размера, которая появляется во входной строке. В приведенном вами примере «AGT» - это подстрока, которая появляется дважды (что чаще, чем любая другая подстрока длиной 3 символа, что делает ее наиболее частой):

AAGTTAGTCA
 AGT AGT

Ваша задача реализовать функцию most_freq_seq, которая будет производить наиболее частую подстроку заданной длины из заданной строки. Тот факт, что это строка ДНК и что символы являются «базовыми парами», на самом деле не влияет на реализацию.

Удачи!