*这是一个简短的介绍,具体问题在最后一段以粗体显示.
我正在尝试生成具有给定汉明距离的所有字符串,以有效地解决生物信息学分配.
这个想法是,给定一个字符串(即'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)
我想要做的是,而不是生成所有可能的单词,只生成给定字符串中出现的具有给定数量的不匹配的单词的突变,换句话说,给定汉明距离和单词,返回所有可能的具有该(或更小)距离的变异单词,然后使用它们在给定的字符串中进行搜索.
我希望我很清楚.谢谢.