代码之家 › 专栏 › 技术社区 › Maximilian Wiens

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

hamming-distance dna-sequence permutation algorithm java

6

Maximilian Wiens · 技术社区 · 11 年前

有没有一种算法可以通过给定数量的可以变化的最大允许位置(最大不匹配,最大汉明距离)来生成字符串(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
  {?}

一种可能的方法是生成一个具有给定字符串的所有排列的集合,对它们进行迭代,并移除所有具有更大汉明距离的字符串。

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

还有其他更有效的方法/实现吗?

1 回复 | 直到 9 年前

1

8

Bernhard Barker 11 年前

只需使用普通的置换生成算法,除非你绕过距离,当你有不同的字符时会递减。

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万个候选者(假设我的代码是正确的)。

上面的代码在我的机器上只需不到一秒钟的时间就可以完成(无需打印),但不要指望任何生成器能够在合理的时间内生成更多的代码,因为可能性太多了。