查找文本中出現不匹配的最常見k-mers

Question

我正試圖解決查找字符串中不匹配最頻繁的k-mers。要求列出如下：

不匹配的頻繁字問題：查找字符串中不匹配最頻繁的k-mers。

輸入：字符串文本以及整數k和d。 （您可以假定k≤12且d≤3）。

輸出：所有最常見的k-mers，在文本中最多有d個不匹配。

下面是一個例子：

樣品輸入：

ACGTTGCATGTCGCATGATGCATGAGAGCT

樣本輸出：

GATG ATGC ATGT

最簡單和最低效方式是lis ■所有文本k聚體，並計算其彼此間的hamming_difference，並挑選出的圖案，其hamming_difference小於或d相等，下面是我的代碼：

import collections 

kmer = 4 
in_genome = "ACGTTGCATGTCGCATGATGCATGAGAGCT"; 
in_mistake = 1; 
out_result = []; 
mismatch_list = [] 

def hamming_distance(s1, s2): 
    # Return the Hamming distance between equal-length sequences 
    if len(s1) != len(s2): 
     raise ValueError("Undefined for sequences of unequal length") 
    else: 
     return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2)) 

for i in xrange(len(in_genome)-kmer + 1): 
    v = in_genome[i:i + kmer] 
    out_result.append(v) 

for i in xrange(len(out_result) - 1): 
    for j in xrange(i+1, len(out_result)): 
     if hamming_distance(str(out_result[i]), str(out_result[j])) <= in_mistake: 
      mismatch_list.extend([out_result[i], out_result[j]]) 

mismatch_count = collections.Counter(mismatch_list) 
print [key for key,val in mismatch_count.iteritems() if val == max(mismatch_count.values())] 

了預期的效果。相反，我得到了' CATG」。有人知道我的代碼有問題嗎？

Answer 1

這一切似乎很大，直到你的代碼最後一行：

print [key for key,val in mismatch_count.iteritems() if val == max(mismatch_count.values())] 

由於CATG比其他任何k聚體的得分更高，你永遠只能得到一個答案。看看：

>>> print mismatch_count.most_common() 
[('CATG', 9), ('ATGA', 6), ('GCAT', 6), ('ATGC', 4), ('TGCA', 4), ('ATGT', 4), ('GATG', 4), ('GTTG', 2), ('TGAG', 2), ('TTGC', 2), ('CGCA', 2), ('TGAT', 1), ('GTCG', 1), ('AGAG', 1), ('ACGT', 1), ('TCGC', 1), ('GAGC', 1), ('GAGA', 1)] 

找出你真的想從這個結果回來什麼。

我認爲解決方法是改變你的第二個頂級「for」循環，內容如下：

for t_kmer in set(out_result): 
    for s_kmer in out_result: 
     if hamming_distance(t_kmer, s_kmer) <= in_mistake: 
      mismatch_list.append(t_kmer) 

這將產生類似的結果是什麼你期待：

>>> print mismatch_count.most_common() 
[('ATGC', 5), ('ATGT', 5), ('GATG', 5), ('CATG', 4), ('ATGA', 4), ('GTTG', 3), ('CGCA', 3), ('GCAT', 3), ('TGAG', 3), ('TTGC', 3), ('TGCA', 3), ('TGAT', 2), ('GTCG', 2), ('AGAG', 2), ('ACGT', 2), ('TCGC', 2), ('GAGA', 2), ('GAGC', 2), ('TGTC', 1), ('CGTT', 1), ('AGCT', 1)]