"How can I tell if a string repeats itself in Python?" 的更复杂版本
A more complex version of "How can I tell if a string repeats itself in Python?"
我正在阅读 ，我想知道是否有人可以找到将重复的图案捕捉到更复杂的字符串中的方法。
例如，找到
中所有重复的图案
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' 主题不被考虑。
您可以使用递归函数，如下所示：
注意：结果参数将被视为全局变量（因为将可变对象传递给函数会影响调用者）
import re
def finder(st,past_ind=0,result=[]):
m=re.search(r'(.+)+',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'
您可以使用 的答案和一些额外的食谱：
首先，您可以使用 ** 拆分字符串，然后使用 r'(.+)+' 正则表达式创建一个包含重复字符串的新列表：
所以结果将是：
>>> new=[re.search(r'(.+)+',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'(.+)+',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}}
这个简单的 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 包含所有重复的模式...让我们用一些标准过滤它们：
minlen = 3
for m in filter(lambda m: len(m)>=minlen and s.count(2*m)>=1, motifs):
print(m)
'''
ATACGT
ACGT
TATACG
CGTA
'''
您可以利用以下事实：在正则表达式中，前瞻不会推进主迭代器。因此，您可以在前瞻中嵌套捕获组以查找重复并具有指定最小长度的（可能重叠的）模式：
>>> import re
>>> s = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'
>>> re.findall(r'(?=(.{2,})+)', s)
['AC', 'ACGT', 'CGTA', 'GT', 'TG', 'GT', 'CC', 'TATACG', 'ATACGT', 'TA']
>>> re.findall(r'(?=(.{2,}?)+)', s)
['AC', 'ACGT', 'CGTA', 'GT', 'TG', 'GT', 'CC', 'TA', 'ATACGT', 'TA']
请注意使用贪婪量词和非贪婪量词的结果略有不同。贪婪量词从原始字符串中的每个索引开始搜索最长的重复子字符串（如果存在的话）。非贪婪量词搜索最短的相同量词。限制是字符串中每个起始索引最多只能获得一个模式。如果您有解决此问题的任何想法，请告诉我！潜在地，我们可以使用贪婪量词正则表达式来设置一个递归解决方案，从每个索引开始找到 每个 重复模式，但让我们暂时避免 "premature computation"。
现在，如果我们采用正则表达式 (?=(.{2,})+) 并对其进行修改，我们还可以捕获包含重复图案的整个子字符串。通过这样做，我们可以使用匹配的 span 来计算重复次数：
(?=((.{2,})+))
在上面的正则表达式中，我们在先行中的捕获组中有一个捕获组。现在我们拥有解决问题所需的一切：
def repeated_motifs(s):
import re
from collections import defaultdict
rmdict = defaultdict(list)
for match in re.finditer(r'(?=((.{2,})+))', s):
motif = match.group(2)
span1, span2 = match.span(1), match.span(2)
startindex = span1[0]
repetitions = (span1[1] - startindex) // (span2[1] - startindex)
others = rmdict[motif]
if not others or startindex > others[-1]['region'][1]:
others.append({'repeat': repetitions, 'region': span1})
return rmdict
s = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'
d = repeated_motifs(s)
print(d)
# list of the repeating motifs we have found sorted by first region
print(sorted(list(d.keys()), key=lambda k: d[k][0]['region']))
因为未指定主题在字符串的多个 "regions" 中重复自身的情况下所需的行为，我假设 OP 想要一个 string->list 的字典，其中每个列表包含自己的一套词典。
如果可以绑定查询，则可以使用字符串的单次传递。比较次数将为 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)
输出：
AC at region (2, 6), 2 repeats
ACGT at region (4, 12), 2 repeats
CGTA at region (5, 13), 2 repeats
GT at region (18, 24), 3 repeats
TG at region (19, 23), 2 repeats
GT at region (20, 24), 2 repeats
CC at region (24, 28), 2 repeats
TA at region (28, 32), 2 repeats
TATACG at region (28, 40), 2 repeats
ATACGT at region (29, 41), 2 repeats
TA at region (34, 38), 2 repeats
请注意，这比正则表达式答案捕获了更多的重叠模式，但是如果不了解更多关于您认为 良好 匹配的内容，就很难进一步减少它，因为例如为什么 TATACG 比 ATACGT 好？
额外：使用字典来 return 匹配是一个坏主意，因为模式不会是唯一的。
我正在阅读
例如，找到
中所有重复的图案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' 主题不被考虑。
您可以使用递归函数，如下所示：
注意：结果参数将被视为全局变量（因为将可变对象传递给函数会影响调用者）
import re
def finder(st,past_ind=0,result=[]):
m=re.search(r'(.+)+',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'
您可以使用
首先，您可以使用 ** 拆分字符串，然后使用 r'(.+)+' 正则表达式创建一个包含重复字符串的新列表：
所以结果将是：
>>> new=[re.search(r'(.+)+',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'(.+)+',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}}
这个简单的 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 包含所有重复的模式...让我们用一些标准过滤它们：
minlen = 3
for m in filter(lambda m: len(m)>=minlen and s.count(2*m)>=1, motifs):
print(m)
'''
ATACGT
ACGT
TATACG
CGTA
'''
您可以利用以下事实：在正则表达式中，前瞻不会推进主迭代器。因此，您可以在前瞻中嵌套捕获组以查找重复并具有指定最小长度的（可能重叠的）模式：
>>> import re
>>> s = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'
>>> re.findall(r'(?=(.{2,})+)', s)
['AC', 'ACGT', 'CGTA', 'GT', 'TG', 'GT', 'CC', 'TATACG', 'ATACGT', 'TA']
>>> re.findall(r'(?=(.{2,}?)+)', s)
['AC', 'ACGT', 'CGTA', 'GT', 'TG', 'GT', 'CC', 'TA', 'ATACGT', 'TA']
请注意使用贪婪量词和非贪婪量词的结果略有不同。贪婪量词从原始字符串中的每个索引开始搜索最长的重复子字符串（如果存在的话）。非贪婪量词搜索最短的相同量词。限制是字符串中每个起始索引最多只能获得一个模式。如果您有解决此问题的任何想法，请告诉我！潜在地，我们可以使用贪婪量词正则表达式来设置一个递归解决方案，从每个索引开始找到 每个 重复模式，但让我们暂时避免 "premature computation"。
现在，如果我们采用正则表达式 (?=(.{2,})+) 并对其进行修改，我们还可以捕获包含重复图案的整个子字符串。通过这样做，我们可以使用匹配的 span 来计算重复次数：
(?=((.{2,})+))
在上面的正则表达式中，我们在先行中的捕获组中有一个捕获组。现在我们拥有解决问题所需的一切：
def repeated_motifs(s):
import re
from collections import defaultdict
rmdict = defaultdict(list)
for match in re.finditer(r'(?=((.{2,})+))', s):
motif = match.group(2)
span1, span2 = match.span(1), match.span(2)
startindex = span1[0]
repetitions = (span1[1] - startindex) // (span2[1] - startindex)
others = rmdict[motif]
if not others or startindex > others[-1]['region'][1]:
others.append({'repeat': repetitions, 'region': span1})
return rmdict
s = 'AAACACGTACGTAATTCCGTGTGTCCCCTATACGTATACGTTT'
d = repeated_motifs(s)
print(d)
# list of the repeating motifs we have found sorted by first region
print(sorted(list(d.keys()), key=lambda k: d[k][0]['region']))
因为未指定主题在字符串的多个 "regions" 中重复自身的情况下所需的行为，我假设 OP 想要一个 string->list 的字典，其中每个列表包含自己的一套词典。
如果可以绑定查询，则可以使用字符串的单次传递。比较次数将为 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)
输出：
AC at region (2, 6), 2 repeats
ACGT at region (4, 12), 2 repeats
CGTA at region (5, 13), 2 repeats
GT at region (18, 24), 3 repeats
TG at region (19, 23), 2 repeats
GT at region (20, 24), 2 repeats
CC at region (24, 28), 2 repeats
TA at region (28, 32), 2 repeats
TATACG at region (28, 40), 2 repeats
ATACGT at region (29, 41), 2 repeats
TA at region (34, 38), 2 repeats
请注意，这比正则表达式答案捕获了更多的重叠模式，但是如果不了解更多关于您认为 良好 匹配的内容，就很难进一步减少它，因为例如为什么 TATACG 比 ATACGT 好？
额外：使用字典来 return 匹配是一个坏主意，因为模式不会是唯一的。