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

Fastest way to count instances of substrings in string Python3.6

我一直在开发一个程序,该程序需要计算主字符串(~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

当然Python完全能够执行这些字符串搜索。但是与其重新发明你需要的所有轮子,一次一个螺丝,你最好在 Python 中使用更专业的工具来处理你的问题 - 它看起来像 BioPython 项目是处理此类问题的最积极维护和最完整的项目。

简短 post 并举例说明您的问题: https://dodona.ugent.be/nl/exercises/1377336647/

Link 至 BioPython 项目文档:https://biopython.org/wiki/Documentation

(如果问题只是字符串重叠,那么第 3 方 "regex" 模块将是一种解决方法 - https://pypi.org/project/regex/ - 作为 Python 中的内置正则表达式引擎的 re 模块也不能处理重叠序列)

要计算重叠的 DNA 子串,您可以使用 Biopython:

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

免责声明:我写了这个方法,见提交97709cc

但是,如果您正在寻找真正的高性能,Python 可能不是正确的语言选择(尽管像 Cython 这样的扩展可能会有所帮助)。