如果一个复杂的Python版本我可以告诉自己如果一个复杂的字符串

Question

我在读this post，我想知道是否有人能找到方法将重复的主题捕捉成更复杂的字符串。在

例如，在

string = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'

这里重复的主题： “AAACACGTACGTAATTCCGTGTGTCCCCTATACGTTT”

所以，输出应该是这样的：

^{pr2}$

这个例子来自一种被称为微卫星的典型生物现象，它存在于DNA中。在

更新1:已从字符串变量中删除星号。这是个错误。在

更新2：单字符主题不算在内。例如：在ACGUGAAAGUC中，不考虑“A”基序。在

Answer 1

如果可以绑定查询，则可以使用字符串的单次传递。比较的数量将是length of string * (max_length - min_length)，因此将线性缩放。在

s = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'

def find_repeats(s, max_length, min_length=2):

    for i in xrange(len(s)):
        for j in xrange(min_length, max_length+1):
            count = 1
            while s[i:i+j] == s[i+j*count:i+j*count+j]: count += 1
            if count > 1:
                yield s[i:i+j], i, count

for pattern, position, count in find_repeats(s, 6, 2):
    print "%6s at region (%d, %d), %d repeats" % (pattern, position, position + count*len(pattern), count)

输出：

^{pr2}$

请注意，这比regexp的答案捕捉到更多的重叠模式，但是如果不了解您认为的好的匹配，就很难进一步减少它，例如，TATACG比ATACGT好？在

附加：使用dict返回匹配项是个坏主意，因为模式不是唯一的。在

Answer 2

可以使用如下递归函数：

注意：result参数将被视为全局变量（因为向函数传递可变对象会影响调用方）

import re
def finder(st,past_ind=0,result=[]):
   m=re.search(r'(.+)\1+',st)
   if m:
      i,j=m.span()
      sub=st[i:j]
      ind = (sub+sub).find(sub, 1)
      sub=sub[:ind]
      if len(sub)>1:
        result.append([sub,(i+past_ind+1,j+past_ind+1)])
      past_ind+=j
      return finder(st[j:],past_ind)
   else:
      return result



s='AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'
print finder(s)

结果：

^{pr2}$

以下字符串的上一个问题的答案：

s = 'AAAC**ACGTACGTA**ATTCC**GTGTGT**CCCC**TATACGTATACG**TTT'

您可以使用来自mentioned question的答案和一些额外的配方：

首先可以使用**拆分字符串，然后创建一个新列表，其中包含使用r'(.+)\1+'regex重复的字符串：

所以结果是：

>>> new=[re.search(r'(.+)\1+',i).group(0) for i in s.split('**')]
>>> new
['AAA', 'ACGTACGT', 'TT', 'GTGTGT', 'CCCC', 'TATACGTATACG', 'TTT']

注意，关于'ACGTACGT'在结尾错过了A的内容！在

然后可以使用principal_period的函数来获取重复的子字符串：

def principal_period(s):
    i = (s+s).find(s, 1, -1)
    return None if i == -1 else s[:i]

>>> for i in new:
...    p=principal_period(i)
...    if p is not None and len(p)>1:
...        l.append(p)
...        sub.append(i)
... 

因此，l中有重复的字符串，sub中有主字符串：

>>> l
['ACGT', 'GT', 'TATACG']
>>> sub
['ACGTACGT', 'GTGTGT', 'TATACGTATACG']

然后您需要一个region，您可以使用span方法来完成：

>>> for t in sub:
...    regons.append(re.search(t,s).span())

>>> regons
[(6, 14), (24, 30), (38, 50)]

最后，您可以压缩3个列表regon，sub，l，并使用dict理解来创建预期结果：

>>> z=zip(sub,l,regons)
>>> out={i :{'repeat':i.count(j),'region':reg} for i,j,reg in z}
>>> out
{'TATACGTATACG': {'region': (38, 50), 'repeat': 2}, 'ACGTACGT': {'region': (6, 14), 'repeat': 2}, 'GTGTGT': {'region': (24, 30), 'repeat': 3}}

主要代码：

>>> s = 'AAAC**ACGTACGTA**ATTCC**GTGTGT**CCCC**TATACGTATACG**TTT'
>>> sub=[]
>>> l=[]
>>> regon=[]
>>> new=[re.search(r'(.+)\1+',i).group(0) for i in s.split('**')]
>>> for i in new:
...    p=principal_period(i)
...    if p is not None and len(p)>1:
...        l.append(p)
...        sub.append(i)
... 

>>> for t in sub:
...    regons.append(re.search(t,s).span())
... 
>>> z=zip(sub,l,regons)
>>> out={i :{'repeat':i.count(j),'region':reg} for i,j,reg in z}
>>> out
{'TATACGTATACG': {'region': (38, 50), 'repeat': 2}, 'ACGTACGT': {'region': (6, 14), 'repeat': 2}, 'GTGTGT': {'region': (24, 30), 'repeat': 3}}

Answer 3

这个简单的while循环检测所有重复的模式：

def expand():
    global hi
    hi += 1

def shrink():
    global lo
    lo += 1

s = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'

motifs = set()

lo = 0
hi = 0

f = expand

while hi <= len(s):
    sub = s[lo : hi+1]
    if s.count(sub) > 1:
        motifs.add(sub)
        if lo==hi: f = expand
        f()
    else:
        f = shrink if lo<=hi else expand
        f()

此时，motifs包含所有重复的模式。。。让我们用一些标准来筛选它们：

^{pr2}$