时间戳

首页 > 解决方案 > 寻找python函数以查找字符串中最长的顺序重复子字符串

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

问题描述

我正在对 DNA 序列进行一些编码，并且我对查找连续重复的功能感兴趣（这可能代表引物可能“滑倒”AKA 做坏事的地方）。

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

longest_repeat('ATTTTCCATGATGATG')

这将输出重复长度和坐标，在本例中为 9 长和 7:15。该函数应该在末尾拾取 ATGATGATG，并且由于它比 TTTT 重复和 TGATGA 重复更长，因此它只会报告 ATGATGATG。在关系的情况下，我想它是否可以报告所有关系，或者至少其中一个。

如果它们超过特定长度，设置一个阈值以仅报告这些连续重复也很好。

我在 python 方面有一些经验，但是这个特定的问题让我很难过，因为如果我对它进行低效编码并放入一个 50 个字符长的字符串，它可能需要很长时间。我感谢所有的帮助！

标签： pythonbioinformaticsdna-sequence

解决方案

以下将非常有效地工作。它返回最长的序列、它的长度、它的起始索引和它的结束索引。如果有多个最大长度的序列，结果将是它们的列表。函数最长（s，阈值）中的第二个参数是所需的阈值最小长度：

import numpy as np

def b(n): #it returns the factors of an integer. It will be used in next function
    r = np.arange(1, int(n ** 0.5) + 1)
    x = r[np.mod(n, r) == 0]
    return set(np.concatenate((x, n / x), axis=None))
   
def isseq(s): #it tests if a string is a sequence. Using the result from previous function it compares all smaller parts of the devided string to check if they are equal
    l=[int(p) for p in sorted(list(b(len(s))))[:-1]]
    for i in l:
        if len(set(s[k*i:i*(k+1)] for k in range(len(s)//i)))==1:
            return True
    return False

def longest(s, threshold): #the main function that returns the lenghtier sequense or a list of them if they are multiple, using a threshold as minimum length
    m=[]
    for i in range(len(s), threshold-1, -1):
        for k in range(len(s)-i+1):
            if isseq(s[k:k+i]):
                m.append([s[k:k+i], i, k, k+i-1])
        if len(m)>0:
            return m
    return False

例子：

>>>s='ATTTTCCATGATGATGGST'
>>> longest(s, 1)
[['ATGATGATG', 9, 7, 15]]

>>> s='ATTTTCCATGATGATGGSTLWELWELWEGFRJGHIJH'
>>> longest(s, 1)
[['ATGATGATG', 9, 7, 15], ['LWELWELWE', 9, 19, 27]]


>>>s='ATTTTCCATGATGATGGSTWGTKWKWKWKWKWKWKWKWKWKWKWFRGWLWERLWERLWERLWERLWERLWERLWERLWERLWERLWERLWERLWERLWERLWERLWERLWERFGTFRGFTRUFGFGRFGRGBHJ'
>>> longest(longs, 1)
[['LWERLWERLWERLWERLWERLWERLWERLWERLWERLWERLWERLWERLWERLWERLWERLWER', 64, 48, 111]]

推荐阅读