python - "How can I tell if a string repeats itself in Python?"的更复杂版本

Question

我正在阅读 this post我想知道是否有人能找到将重复的图案捕捉到更复杂的字符串中的方法。

例如，找出所有重复的主题

string = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'

这里是重复的主题:'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'

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

output = {'ACGT': {'repeat': 2,
                   'region': (5,13)},
          'GT': {'repeat': 3,
                 'region': (19,24)},
          'TATACG': {'repeat': 2,
                     'region': (29,40)}}

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

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

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

Answer 1

你可以使用递归函数如下:

注意:结果参数将被视为全局变量(因为将可变对象传递给函数会影响调用者)

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)

结果:

[['ACGT', (5, 13)], ['GT', (19, 25)], ['TATACG', (29, 41)]]

对以下字符串的上一个问题的回答:

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

您可以使用 mentioned question 中的两个答案和一些额外的食谱:

首先，您可以使用 ** 拆分字符串，然后使用 r'(.+)\1+' 正则表达式创建一个包含重复字符串的新列表:

所以结果将是:

>>> 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 并使用字典理解来创建预期结果:

>>> 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}}