优化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 + GTACTGACAGTCTGAGTAGCGTCGTGGTATTCCTGAAAGGNNNNNNNNNNNTNNNNNNNNNNNTGTTATGTTTACTCCTACGAATNTGATGGCGAAGTGGGCTNTTGCTD00535：66：CCE77ANXX：5：2306：6815：1999 1：N：0：ATTACTCG + GTACTGACGATGATCTGCCGAAGCTCAGGAATTCGGTCGTNNNNNNNNNNNGNNNNNNNNNNNCTCTGGTCCAGCCTTTCCACGTNCTCCACTCGCATGCCGANGATGAD00535：66：CCE77ANXX：5：2306：17450：1999 1：N：0：ATTACTCG + GTACTGACGGCTTCATGCTGCAGCGTGGCCTCCTCCAGGTNNNNNNNNNNNTNTNNNNNNNNNGNGCCTCTCTCTTCTTGTTCATCTNGATCTGGGCTGAAGTGGNNCCGCD00535：66：CCE77ANXX：5：2306：18797：2000 1：N：0：ATTACTCG + GTACTGACAAGCTGTTAGTGAAATAAATGATCCTATAGAANNNNNNNNNNNTNNNNNNNNGNGAGCATCTGGGTAGTCTGAGTAGNGTCGTGGTATTCCTGAANGGCCCD00535：66：CCE77ANXX：5：2306：1210：2146 1：N：0：ATTACTCG + GTACTGACGTCATGTCTTCCTTTTCAAAAAACTTCAGTTTTGTAGATTTTCGTTGAAACAGCAAGCGAAGCACCAGGTCCTCTCTTTTCATCATCGGAGCGTCTGCAGATCG]

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，这是接受字符串所有后缀的最小的deterministic finite automaton，可能是更有效的解决方案：

直觉上，后缀自动机可以理解为给定字符串的所有子字符串的压缩形式。一个令人印象深刻的事实是，后缀自动机以高度压缩的形式包含所有这些信息。对于长度为n的字符串，它仅需要O（n）内存。而且，它也可以以O（n）时间构建（如果我们将字母的大小k视为常数），否则内存和时间复杂度均为O（n log k）。

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

[需要O（n）时间到build the suffix automaton，然后需要O（k）时间到count occurrences for each substring。可能有a ^ k个子字符串，其中a是字母的大小（在您的示例中为5），因此问题的总运行时间为O（n + 5 ^ k）。如果n比5 ^ k大很多，那么这可能是一个很大的加速。但几乎可以肯定，如果k很小的话就不会。