ハミング距離で区切られた文字列のすべての対（DNA）を取得= 1

Question

Iは次のように、DNA配列の配列を有する：

AA
TA
AC
CC

とIすべてのシーケンスペアの間のハミング距離を計算するためのより速い方法の検索（おそらく並べ替えによる）、次に素朴なアプローチ（O（N^2））

私はあなたのn >> kの場合はハミング距離= 1

Answer 1

を持っているペアのシーケンスを必要とし、その後は

あなたのオリジナルの複雑さは、kはO（nはN k）は、であるが、以下試すことができますシーケンスの長さ（ハミング距離の比較にはkステップが必要）。それを改善しようとしましょう。

1. 1それから離れているすべての文字列を作成し、あなたの入力の各文字列の場合はその中のすべての文字列とハッシュマップ（複雑性​​Oためにハッシュの（N * K））
2. を作成し、それらが含まれているかどうかを確認ハッシュマップに - それと

を（あなたは、n個の文字列ごとに）k個のバリエーションのそれぞれをO（kはハッシュする必要があるため）複雑性O（nはK K）yesの場合、あなたは、ペアを発見しましたO（n n k）をO（n k k）に置き換えました。 n >> kならば有益でなければならない。

k >> nの場合、おそらくn^2の部分は気にしないので、簡単なアルゴリズムを使用します。

nは近くのkについて、あなたは*（nは0,1,2,3（複雑性Oですべての文字を加算することにより、私は、各シーケンスのための疑似ハッシュを作成します

1. コメントで示唆されているものを試すことができますk））
2. （並べ替えなしで使用する場合は複雑度O（n * logn）、基数/バケットソートの場合はO（n））
3. 並べ替えられたシーケンスを通り、あなたのケースに応じて最大3離れていますが、ほとんどの病理学的ケースではO（n n k）になりますが、実際のデータではc O（n k f（n））に近い方f（n）は非常に小さいでしょう）