PHPz2017-04-18 10:01:45
アイデアを書いてください
リーリーデータは実際には非常にユニークであるため、ここで合理化できます。
すべての文字列の長さは 20 文字であり、ATCG 4 文字で構成されているためです。その後、比較のために整数に変換できます。
バイナリ表現は次のとおりです
文字列の長さは固定されており、各文字は 2 ビットで表現できるため、各文字列は 40 ビット整数として表現できます。 32+8 の形式で表現することも、64 ビット シェーピングを直接使用することもできます。これを行うには、C 言語を使用することをお勧めします。
比較について話しましょう。
每一个candidate在bg_db中与之差异小于等于4的所有记录 を見つける必要があるため、2 つの整数に対して ^ ビットごとの XOR 演算を実行する限り、結果 二进制中1不超过8个,且这不超过8个1最多只能分为4个组 は要件 (00^11 =11) を満たす可能性があります。 ,10^01=11)。
結果の 40 ビットを 20 のグループに分割します。つまり、3 つの値 4 b01 b10 を持つ最大 b11 グループがあり、残りはすべてb00 。
これで、比較アルゴリズムを簡単に書くことができます。
バイトごとに 3 つの非ゼロ値のグループ (4 つのグループ) を取得して、全体的な比較結果を簡単に取得できます。
各バイトには 256 個の可能な値 しかなく、 しかないため、結果は最初に保存してから取得できます。 3^4=81 種類の修飾された値
これは、結果にゼロ以外のグループがいくつあるかを取得する関数です。
阿神2017-04-18 10:01:45
まず第一に、この種の大規模なデータ処理は、合計時間を計算するための乗算に使用されるまでに、数万のアイテムを実行し、10 秒以上継続する必要があります。 1 つの項目のみがカウントされる場合、この時間はクリティカルな IO や CPU オーバーヘッドではなく、初期化プロセスのほぼすべてのオーバーヘッドです
以下のテキスト
ACTG の 4 つの可能性は 2 ビットに相当します。1 つの遺伝子の位置を表すのに 1 つの文字を使用するのはあまりにも無駄です。1 つの文字は 8 ビットであり、4 つの遺伝子の位置を保持できます。
アルゴリズムを使用せず、20 個の遺伝子をバイナリ形式に書き込むだけでも、時間を 5 倍節約できます
また、20 回ループした後の CPU 命令の数は 20*n であり、n は少なくとも 3 であると推定されます。ただし、バイナリの場合、比較のための XOR 演算は直接 CPU 命令であり、その命令の数は手順は 1
巴扎黑2017-04-18 10:01:45
アルゴリズムについてはあまり詳しくありませんが、経験から言えば、複雑なアルゴリズムは時間がかかり、この単純で粗雑なアルゴリズムほど高速ではありません
データを処理するためにマルチスレッドとクラスタリングを検討できます
ちなみにハミング距離も計算できるようです
伊谢尔伦2017-04-18 10:01:45
また、アルゴリズムは使用されず、C で書かれた総当りのソリューションです
私のマシン (CPU: Core 2 Duo E7500、RAM: 4G、OS: Fedora 19) でのテスト結果
リーリー対象の 24 コア CPU に切り替えると、パフォーマンスが 20 倍向上し、48 台のマシンを追加して 5000W の操作を行うと 15 秒かかり、時間は
10000000 * 1000000000 になります。 / 500 / 1000000 * 15 / 20 / 48 / 3600 / 24 = 3.616898 日
パラメータをコンパイルして実行
リーリーマルチスレッドに変更すると、速度が速くなります。私のマシンでは、2 スレッドに変更して、単純に 500条candidates まで速度を上げることができました。スレッド数が 9040257微秒 に増加すると、パフォーマンスが向上します。それほど大きなことではありませんが、新しい CPU にはハイパースレッディング テクノロジが搭載されており、速度の向上が期待されます。 。 。 4
リーリー
リーリー
巴扎黑2017-04-18 10:01:45
申し訳ありませんが、今日他の人が返信しているのを見ました。
質問をよく見てみると、ただの一致だと思っていたことに気づきました。
そこで私はACオートマトンの使用を提案しました。
しかし、質問の目的はシーケンスの違いを見つけることです。
これは、2 つの間の編集距離を見つけるためです。
wiki: 距離の編集
wiki: Ravenstein 距離
私が OJ を磨いていたときは、DP (動的プログラミング) を使用して、ある文字列を別の文字列に変換するための最小編集数を見つけました。
リーリー例:
リーリーstr2 は str1 に変換されます
b を挿入 1 回カウント
d を削除 1 回カウント
f を変更 1 回カウント
被験者の ATCG 遺伝子配列については、変更された配列を見つけるだけでよいですか?
しかし、この
ATCGATCG
TCGATCGA
のように計算するにはどうすればよいでしょうか?
変更のみが見つかった場合は、str1[i] と str2[i] を直接比較してください。
リーリー@rockford からインスピレーションを受けました。
生データを前処理できます。
候補の文字列
GGGAGCAGGCAAGGACTCTG
A5 T2 C4 G9
A5 T2 C4 G9 処理後の追加データ
bg_db の文字列
CTGCTGACGGGTGACACCCA
A4 T3 C7 G6
A4 T3 C7 G6 処理後の追加データ
A5 -> A4 は -1 として記録されます
T2 -> T3 は +1 として記録されます
C4 -> C7 は +3 として記録されます
G9 -> として記録されます-3
明らかに、A は変更された場合にのみ TCG になります。
同様に、少なくとも相違点の数を知るには、すべて + またはすべて -
を数えるだけで済みます。
4 より大きいものは比較する必要はありません。
最初に前処理された追加データを比較し、次に単一の比較アルゴリズムを通じて比較を実行します。
(土曜は残業、退勤後に執筆)
天蓬老师2017-04-18 10:01:45
必要なのは、これらのタスクをワーカーに送信することです。このような計算は単一のプロセスで同期的に実行されません。
実際、これは [a, b] と [c, d] を比較するのと同じであり、あなたのタスクは
[a, c]
[a, d]
[b, c]
[b, d]
同期シリアルの場合、必要な時間は 4 * 単一時間
4 つの CPU または 4 つのマシンを並列に使用している場合、時間はほぼ 単一時間
したがって、ゲノムなどの計算は基本的に、大きなマシン上のマルチコア並列タスクを使用して行われます。基本的に、参照原則は Google MapReduce 論文の原則です
。
黄舟2017-04-18 10:01:45
私はアルゴリズムは得意ではありませんが、あなたのような大量のデータを扱う場合、あなたのような CPU を大量に使用するデータタスクの場合は、コンピューターと比較することはできません。他の人がアルゴリズムを使用していると言ったことに同意します。つまり、map-reduce モデルを使用して計算します。
マップはマッピングです。まず、各候補を 1 つずつ bg_db にマッピングして、次のようなデータ構造を形成します。(candidates,bg_db)
をキューに入れて別のサーバーに渡します。各サーバーは複数のプロセスを使用して計算します。これが唯一の方法ですが、データ量が大きすぎます。タスクを割り当てて並列計算する方法を見つけてください。 、
PHP中文网2017-04-18 10:01:45
辞書ツリーを使用してすべての文字列を保存してみることができます。これにより、クエリ時にディクショナリ ツリーをトラバースする方法を使用できるようになります。
ツリーを走査するとき、現在のノードのシーケンスを維持できます。このシーケンスには、現在走査されているノードと対応するノード間の不一致の数が保存されます。
次のノードを移動するときは、現在のシーケンス内のすべてのノードを下に進み、新しいノード シーケンスを形成するようにしてください。
利点は、多くの文字列の現在のビットをまとめて比較できるため、時間を節約できることです。各位置の選択肢は多くなく、不一致も大きくないため、現在のノード列を過度に拡張する必要はありません。 (推測です…あまり詳しく検証してませんが…)
上記のコードは大まかなアイデアです。 C++ で記述した方がはるかに高速になります。
プロセス全体は、分散コンピューティング用のクラスターを使用して実行できます。
PHP中文网2017-04-18 10:01:45
視覚的には、質問者には計算するための複数のマシンがありません。
各文字列 (A:0、T:1、C:2、G:) のアルファベット順の合計を計算するという簡単なアイデアがあります。 3)、最初に 2 つの文字列の順序合計の差を計算します。最大値は 12 を超えることはできません。4 つの A は 4 つの G になります。差が 12 未満の場合は、
を処理します。追加の設定を使用すると、理論的にははるかに高速になる可能性があります。
文字列の編集距離 (ある文字列を別の文字列に追加、削除、および変更するための最小編集回数) を計算する別のアルゴリズムがあります。それは今のところ思い出せません。ご自身で確認してください。