优化 python 用于计算子字符串出现次数的字典创建

Question

函数接收包含数千行的文件名和一个K值。该函数必须将文件的每一行分成 K 个序列，并创建一个字典，其中序列是键，值是文件中出现的次数。 问题是耗时较长（75s）

def dictionary_creator(file, k):
    dictionary = dict()
    for record in SeqIO.parse(file, "fasta"):
        for i in range(len(record.seq) - k + 1):
            kseq = str(record.seq)[i:i + k]
            if kseq in dictionary:
                dictionary[kseq] += 1
            else:
                dictionary[kseq] = 1
    return dictionary

示例：

sampleC.fa

D00535:66:CCE77ANXX:5:2306:5138:1999 1:N:0:ATTACTCG+GTACTGAC AGTCTGAGTAGCGTCGTGGTATTCCTGAAAGGNNNNNNNNNNNTNNNNNNNNNNNTGTTATGTTTACTCCTACGAATNTGATGGCGAAGTGGGCTNTTGCT D00535:66:CCE77ANXX:5:2306:6815:1999 1:N:0:ATTACTCG+GTACTGAC GATGATCTGCCGAAGCTCAGGAATTCGGTCGTNNNNNNNNNNNGNNNNNNNNNNNCTCTGGTCCAGCCTTTCCACGTNCTCCACTCGCATGCCGANGATGA D00535:66:CCE77ANXX:5:2306:17450:1999 1:N:0:ATTACTCG+GTACTGAC GGCTTCATGCTGCAGCGTGGCCTCCTCCAGGTNNNNNNNNNNNTNNNNNNNNNNNGCCTCTCTCTTCTTGTTCATCTNGATCTGGGCTGAAGTGGNNCCGC D00535:66:CCE77ANXX:5:2306:18797:2000 1:N:0:ATTACTCG+GTACTGAC AAGCTGTTAGTGAAATAAATGATCCTATAGAANNNNNNNNNNNTNNNNNNNNGNNAGCATCTGGGTAGTCTGAGTAGNGTCGTGGTATTCCTGAANGGCCC D00535:66:CCE77ANXX:5:2306:1210:2146 1:N:0:ATTACTCG+GTACTGAC GTCATGTCTTCCTTTTCAAAAAACTTCAGTTTTGTAGATTTTCGTTGAAACAGCAAGCGAAGCACCAGGTCCTCTCTTCTCATCGGAGCGTCTGCAGATCG

Python:

dictionary_creator('sampleC.fa',2)

输出：

{'AG': 26, 'GT': 31, 'TC': 42, 'CT': 38, 'TG': 32, 'GA': 24, 'TA': 13, 'GC': 25, 'CG': 18, 'GG': 20, 'AT': 22, 'TT': 27, 'CC': 20, 'AA': 23, 'GN': 5, 'NN': 79, 'NT': 6, 'TN': 9, 'AC': 7, 'CA': 19, 'NG': 7, 'NC': 3, 'AN': 3, 'NA': 1}

Answer 1

有一个微不足道的改进：您在内循环中执行 str(record.seq)。此操作需要 O(n) 时间，其中 n 是字符串的长度，而您正在执行 O(n) 次，因此算法的时间复杂度为 O(n²)。但是每次的字符串都是一样的，所以你应该在外循环中只构建一次：

    for record in SeqIO.parse(file, "fasta"):
        seq_str = str(record.seq)
        for i in range(len(seq_str) - k + 1):
            kseq = seq_str[i:i + k]
            # ...

应用此修复后，此简单算法的运行时间为 O(nk)，其中 n 是字符串的长度，k 是您要计算的子字符串的长度。如果这足够好，那就太好了，你可以在这里停止阅读。

使用 suffix automaton, which is the smallest deterministic finite automaton 接受字符串的所有后缀是可能的更有效的解决方案：

Intuitively a suffix automaton can be understood as compressed form of all substrings of a given string. An impressive fact is, that the suffix automaton contains all this information in a highly compressed form. For a string of length n it only requires O(n) memory. Moreover, it can also be build in O(n) time (if we consider the size k of the alphabet as a constant), otherwise both the memory and the time complexity will be O(n log k).

想法是为record.seq构造一个后缀自动机，然后用它来计算长度为k的每个可能子串的出现次数。

build the suffix automaton, and then O(k) time to count occurrences for each substring需要O(n)的时间。有 a^k 个可能的子字符串，其中 a 是字母表的大小（在您的示例中为 5），因此您的问题的总体运行时间将为 O(n + 5^k)。如果 n 比 5^k 大很多，那么这可能是一个显着的加速；但如果 k 非常小，几乎可以肯定不会。

优化 python 用于计算子字符串出现次数的字典创建

Optimize python dictionary creation for counting substring occurrences

python

fasta