查找python函数以查找字符串中最长的顺序重复子字符串

Question

我正在对DNA序列进行编码，我感兴趣的是一个寻找序列重复的函数（这可能表示引物可能“滑倒”或做坏事的地方）

我感兴趣的一个例子如下：

longest_repeat('ATTTTCCATGATGATG')

这将输出重复长度和坐标，在本例中为9长和7:15。函数应该在末尾拾取ATGATG，因为它比TTTT重复和TGA重复更长，所以它只报告ATGATG。就领带而言，我想知道它是否能报告所有的领带，或者至少其中一条

如果设置一个阈值，只报告超过特定长度的连续重复，也会很好

我在python方面有一些经验，但这个特定的问题一直困扰着我，因为如果我编写的代码效率低下，并且输入一个50个字符长的字符串，可能会花费很长时间。我感谢所有的帮助

Answer 1

以下是一个解决方案：

def longest_repeat(seq, threshold):
    results = []
    longest = threshold
    
    # starting position
    for i in range(len(seq)):
        
        # pattern period
        for p in range(1, (len(seq)-i)//2+1):
            # skip unecessary combinations
            if results != [] and results[-1][0] == i and results[-1][3] % p == 0: continue
            
            # max possible number of repetitions
            repetitions = len(seq)//p
            
            # position within the pattern's period
            for k in range(p):
                # get the max repetitions the k-th character in the period can support
                m = 1
                while i+k+m*p < len(seq) and seq[i+k] == seq[i+k+m*p]:
                    m += 1
                repetitions = min(m, repetitions)
                
                # check if we're already below the best result so far 
                if repetitions*p < longest:    break
            
            # save the result if it's good
            if repetitions > 1 and repetitions*p >= longest:
                # overwrite lesser results
                if repetitions*p > longest: results = []
                
                # store the current one (with ample information)
                results += [(i, seq[i:i+p], repetitions, repetitions*p)]
                longest = max(longest, repetitions*p)
    
    return results

逻辑是，您运行序列中的每个起始位置（i），检查每个合理的模式周期（p），并为该组合检查它们是否产生至少与迄今为止最好的子字符串一样好的子字符串（或者阈值，如果尚未找到结果）

结果是(starting index, period string, repetitions, total length)形式的元组列表。以身作则

threshold = 5
seq = 'ATTTCCATGATGATG'

t = time.time()
results = longest_repeat(seq, threshold)
print("execution time :", time.time()-t)

for t in results:
    print(t)

我们得到

exec : 0.00010848045349121094
(6, 'ATG', 3, 9)

从那里，获得完全匹配的字符串是很简单的（只需执行period_string * repetitions）

对于700个字符的随机输入，执行时间约为6.8秒，而使用@IoaTzimas的答案时执行时间约为20.2秒