计算字符串 Python3.6 中子字符串实例的最快方法

Question

我一直在开发一个程序，该程序需要计算主字符串（~400,000 个字符）内的子字符串（列表中最多 4000 个 2-6 个字符的子字符串）。我知道这类似于在Counting substrings in a string 中提出的问题，但是，此解决方案对我不起作用。由于我的子字符串是 DNA 序列，我的许多子字符串都是单个字符（例如“AA”）的重复实例；因此，如果我用 'AA' 分割字符串，'AAA' 将被解释为 '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

Answer 1

要计算 DNA 的重叠子串，您可以使用 Biopython：>>> from Bio.Seq import Seq>>> Seq('AAA').count_overlap('AA')2免责声明：我写了这个方法，见 commit 97709cc。但是，如果您正在寻找真正的高性能，Python 可能不是正确的语言选择（尽管像 Cython 这样的扩展可能会有所帮助）。

Answer 2

当然，Python 完全能够执行这些字符串搜索。但是，与其重新发明您需要的所有轮子，一次一个螺丝，不如使用 Python 中更专业的工具来处理您的问题 - 看起来 BioPython 项目是最积极维护和最完整的来处理这类问题。带有类似于您的问题的示例的简短帖子：https : //dodona.ugent.be/nl/exercises/1377336647/链接到 BioPython 项目文档：https ://biopython.org/wiki/Documentation（如果问题只是字符串重叠，那么第 3 方“正则表达式”模块将是一种方法 - https://pypi.org/project/regex/ - 因为 Pythonre模块中的内置正则表达式引擎不能处理重叠序列或者）