*这是一个简短的介绍,具体问题在最后一段以粗体显示。
我正在尝试生成具有给定汉明距离的所有字符串,以有效地解决生物信息学任务。
这个想法是给定一个字符串(即“ ACGTTGCATGTCGCATGATGCATGAGAGCT”),要搜索的单词的长度(即4)以及在字符串中搜索该单词时可接受的不匹配(即1),返回最频繁的单词或“变异”字。
要清楚,给定字符串的长度为4的单词可以是以下单词(在[[]'之间):
[ACGT]TGCATGTCGCATGATGCATGAGAGCT #ACGT
这个
A[CGTT]GCATGTCGCATGATGCATGAGAGCT #CGTT
或这个
ACGTTGCATGTCGCATGATGCATGAG[AGCT] #AGCT
我所做的是(而且效率很低,并且当单词需要有10个字符时它的速度很慢)会生成给定距离的所有可能的单词:
itertools.imap(''.join, itertools.product('ATCG', repeat=wordSize))
如果生成的单词(或其突变)出现在循环中,然后搜索并比较给定字符串中的每个单词:
wordFromString = givenString[i:i+wordSize]
mismatches = sum(ch1 != ch2 for ch1, ch2 in zip(wordFromString, generatedWord))
if mismatches <= d:
#count that generated word in a list for future use
#(only need the most repeated)
我想做的是,不是生成所有可能的单词,而是仅生成出现在给定字符串中且具有给定数量的不匹配项的单词的变异,换句话说,给定汉明距离和一个单词,返回所有可能的单词距离等于或小于该距离的变异字词,然后将其用于在给定的字符串中进行搜索。
我希望我很清楚。谢谢。
def mutations(word, hamming_distance, charset='ATCG'):
for indices in itertools.combinations(range(len(word)), hamming_distance):
for replacements in itertools.product(charset, repeat=hamming_distance):
mutation = list(word)
for index, replacement in zip(indices, replacements):
mutation[index] = replacement
yield "".join(mutation)
此函数生成汉明距离小于或等于给定数字的单词的所有变异。它相对有效,并且不检查无效单词。但是,有效的突变可能会出现多次。如果希望每个元素都是唯一的,请使用一组。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句