Самый быстрый способ подсчета экземпляров подстрок в строке Python3.6 - PullRequest
Новая
       7

Самый быстрый способ подсчета экземпляров подстрок в строке Python3.6

0 голосов
/ 24 января 2019

Я работал над программой, которая требует подсчета подстрок (до 4000 подстрок из 2-6 символов, расположенных в списке) внутри основной строки (~ 400 000 символов). Я понимаю, что это похоже на вопрос, заданный на Подсчет подстрок в строке , однако это решение не работает для меня. Поскольку мои подстроки представляют собой последовательности ДНК, многие из моих подстрок являются повторяющимися экземплярами одного символа (например, «AA»); следовательно, «AAA» будет интерпретироваться как один экземпляр «AA», а не как два случая, если я разделю строку на «AA». Мое текущее решение использует вложенные циклы, но я надеюсь, что есть более быстрый путь, так как этот код занимает 5+ минут для одной основной строки. Заранее спасибо! 

def getKmers(self, kmer):
    self.kmer_dict = {}
    kmer_tuples = list(product(['A', 'C', 'G', 'T'], repeat = kmer))
    kmer_list = []
    for x in range(len(kmer_tuples)):
        new_kmer = ''
        for y in range(kmer):
            new_kmer += kmer_tuples[x][y]
        kmer_list.append(new_kmer)
    for x in range(len(kmer_list)):
        self.kmer_dict[kmer_list[x]] = 0
    for x in range(len(self.sequence)-kmer):
        for substr in kmer_list:
            if self.sequence[x:x+kmer] == substr:
                self.kmer_dict[substr] += 1
                break
    return self.kmer_dict

Ответы [ 2 ]

0 голосов
/ 24 января 2019

Для подсчета перекрывающихся подстрок ДНК вы можете использовать Biopython: 

>>> from Bio.Seq import Seq
>>> Seq('AAA').count_overlap('AA')
2

Отказ от ответственности: я написал этот метод, см. Commit 97709cc.

Однако, если вы ищете действительно высокую производительность, Python, вероятно, не является правильным выбором языка (хотя может помочь расширение, подобное Cython).

0 голосов
/ 24 января 2019

Конечно, Python полностью способен выполнять поиск строк. Но вместо того, чтобы заново изобретать все необходимые вам колеса, по одному винту за раз, вам лучше использовать более специализированный инструмент внутри Python для решения вашей проблемы - похоже, проект BioPython наиболее активно поддерживается и завершается. чтобы справиться с такой проблемой.

Короткий пост с примером, напоминающим вашу проблему: https://dodona.ugent.be/nl/exercises/1377336647/

Ссылка на документацию по проекту BioPython: https://biopython.org/wiki/Documentation

(если бы проблема заключалась в том, что строки просто перекрывались, то сторонний модуль "regex" был бы хорошим способом - https://pypi.org/project/regex/ - поскольку встроенный движок регулярных выражений в модуле re Python не может иметь дело с перекрывающейся последовательностью либо)

...