通过Java中给定的最大汉明距离(不匹配的数量)获取所有字符串组合

是否有算法通过给定数量的可以变化的最大允许位置(最大不匹配,最大汉明距离)生成字符串(DNA序列)的所有可能的字符串组合？

字母表是{A,C,T,G}.

字符串AGCC和最大错配数2的示例：

Hamming distance is 0 {AGCC} Hamming distance is 1 {CGCC, TGCC, GGCC, AACC, ACCC, ATCC, AGAC, AGTC, ..., AGCG} Hamming distance is 2 {?}

一种可能的方法是生成一个包含给定String的所有排列的集合,迭代它们并删除具有更大汉明距离的所有字符串.

通过给定的20个字符的字符串和最大汉明距离5,这种方法非常耗费资源.

那还有另一个更有效的approcahes / implementation吗？

最佳答案

只需使用常规排列生成算法,除了你绕过距离,当你有一个不同的角色时减少它.

static void permute(char[] arr, int pos, int distance, char[] candidates) { if (pos == arr.length) { System.out.println(new String(arr)); return; } // distance > 0 means we can change the current character, // so go through the candidates if (distance > 0) { char temp = arr[pos]; for (int i = 0; i < candidates.length; i++) { arr[pos] = candidates[i]; int distanceOffset = 0; // different character, thus decrement distance if (temp != arr[pos]) distanceOffset = -1; permute(arr, pos+1, distance + distanceOffset, candidates); } arr[pos] = temp; } // otherwise just stick to the same character else permute(arr, pos+1, distance, candidates); }

致电：

permute("AGCC".toCharArray(), 0, 1, "ACTG".toCharArray());

表现说明：

对于字符串长度为20,距离为5和5个字符的字母表,已经有超过1700万个候选者(假设我的代码是正确的).

上面的代码只需不到一秒的时间就可以在我的机器上完成(不需要打印),但是不要指望任何发生器能够在合理的时间内产生比这更多的东西,因为有太多的可能性.

点击查看更多相关文章