7

リストtransに格納されたn（〜1000000）文字列（DNAシーケンス）のセットがあります。リスト内のすべてのシーケンスの最小ハミング距離を見つける必要があります。私は単純なブルート フォース アルゴリズムを実装しましたが、これは 1 日以上実行されており、まだ解決策が示されていません。私のコードは

dmin=len(trans[0])
for i in xrange(len(trans)):
    for j in xrange(i+1,len(trans)):
            dist=hamdist(trans[i][:-1], trans[j][:-1])
            if dist < dmin:
                    dmin = dist

これを行うためのより効率的な方法はありますか? ここで hamdist は、ハミング距離を見つけるために私が書いた関数です。それは

def hamdist(str1, str2):
    diffs = 0
    if len(str1) != len(str2):
        return max(len(str1),len(str2))
    for ch1, ch2 in zip(str1, str2):
        if ch1 != ch2:
          diffs += 1
    return diffs
4

4 に答える 4

4

いくつかのアイデア:

1) sklearn.metrics.hamming_lossは、文字列を配列に変換する必要がある場合でも、おそらく実装よりもはるかに効率的です。

2) すべての文字列は一意ですか? その場合、重複を削除します。

たとえば、sklearn.metrics.pairwise.pairwise_distancesを試すこともできます。

In [1]: from sklearn.metrics.pairwise import pairwise_distances

In [2]: from sklearn.metrics import hamming_loss

In [3]: a = np.array([[3,4,5], [3,4,4],[3,1,1]])

In [4]: import numpy as np

In [5]: a = np.array([[3,4,5], [3,4,4],[3,1,1]])

In [6]: pairwise_distances(metric=hamming_loss)

In [7]: pairwise_distances(a, metric=hamming_loss)
Out[7]: 
array([[ 0.        ,  0.33333333,  0.66666667],
       [ 0.33333333,  0.        ,  0.66666667],
       [ 0.66666667,  0.66666667,  0.        ]])

上三角形のみを計算するフラグは表示されませんが、これはループよりも高速である必要があります。

于 2014-07-08T06:03:44.637 に答える
3

この回答で述べたように、二次実行時間よりも良くなる一般的な方法はありません。データの構造を活用する必要があります。たとえば、最大許容ハミング距離のしきい値 t が文字列の長さ n に比べて小さい場合 (例: t=100、n=1000000)、次の操作を実行できます: k 列をランダムに選択します (例: k=1000)。文字列をこれらの列に制限し、それらをバケットにハッシュします。次に、ハミング距離が最小の 2 つの文字列が選択されていない列でのみ一致しないという仮定の下で、各バケット内でのみペアワイズ比較を行う必要があります。例の場合、これは約 90% の確率で当てはまり、プロセスを繰り返すことでエラー確率を任意に低くすることができます。

于 2014-07-08T07:34:55.777 に答える
-1

すべての文字列のハミング距離を見つけて配列に格納します。何かのようなもの

    distance=[]
    for i in trans:
      distance.append(hamdist(i))

次に、それらの分を次のように計算します

    minimum =min(distance)
于 2014-07-08T05:50:46.680 に答える