在python中以最少的时间复杂度在长序列上循环

Question

我有两个DNA序列（长序列），我想重复它们。 我尝试了传统的for循环，但它需要线性时间，所以它有很大的复杂性，所以我想找到一种方法在这两个序列上循环，并比较没有线性时间的字符，有什么方法可以做到这一点吗？ 更新 我想比较两个序列中的每个字符 更新2: 这是我试过的代码

for i in range(0,len(seqA)):
    if seqA[i]==seqB[i]:
        print("similar")
    else :
        print("not similar")

这是一个DNA序列样本，我想比较一下

seqA = "AT-AC-TCT-GG--TTTCT--CT----TCA---G-A-T--C-G--C--AT-A----AATC-T-T--T-CG-CCTT-T-T---A---C--TA-A--A---G-ATTTCCGT-GGAG-AGG-A-AC---AACTCT-G-AG-T--CT---TA--AC-CCA---ATT-----T--T-TTG-AG--CCTTGCCTT-GGCAA-GGCT--A---"
seqB = "ATCGCTTCTCGGCCTTT-TGGCTAAGATCAAGTGTAGTATCTGTTCTTATCAGTTTAAT-ATCTGATACGTCC-TCTATCCGAGGACAATATATTAAATGGATTT---TTGGAGCAGGGAGA-TGGAA---TAGGAGCTTGCTCCGT-CCACTCCACGCA-TCGACCTGGTATTGCAGTACC-T-CC--AGG-AACGG-TGCACCC"

Answer 1

如果您需要：一个序列，告诉您每个位置在该点上是否相等（假设相等长）：

result = "".join(
    1 if a == seqB[i] else 0
    for (i, a) in enumerate(seqA)
)

不确定result有多有用。如果两个序列相似，但其中一个删除了一个字母，该怎么办？通过这种测量，序列将非常不同

Levenshtein编辑距离可以更好地捕捉相似性的直觉，但计算成本要高得多

https://en.wikipedia.org/wiki/Levenshtein_distance

你可以把序列分成100个字母的块，然后在每对块上执行Levenshtein

这个图书馆对我来说工作得很好，研究的是古代文献，而不是DNA（我在几个小时内完成了数十亿对数据块）： https://github.com/ztane/python-Levenshtein