-1

問題は、与えられた DNA 配列で複数回出現する長さ k のすべての配列を見つけることです。長さ k の各シーケンスについて、ハッシュが計算され、マップに格納される、ローリング ハッシュ関数を使用するアプローチを見つけました。現在のシーケンスが繰り返しかどうかを確認するには、そのハッシュを計算し、ハッシュがハッシュ マップに既に存在するかどうかを確認します。はいの場合は、このシーケンスを結果に含めます。そうでない場合は、ハッシュ マップに追加します。

ここでのローリング ハッシュとは、ウィンドウを 1 つスライドさせて次のシーケンスに移動するときに、前のシーケンスの最初の文字の寄与を削除し、新しく追加された文字の寄与を追加する方法で、前のシーケンスのハッシュを使用することを意味します。つまり、新しいシーケンスの最後の文字です。

Input: AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT
and k=10
Answer: {AAAAACCCCC, CCCCCAAAAA}

このアルゴリズムは完璧に見えますが、完全なハッシュ関数を作成して衝突を回避することはできません。誰かがどのような状況でも完璧なハッシュを作成する方法を説明できれば、それは大きな助けになります.

4

4 に答える 4

5

これは実際には研究課題です。

入力 = N、入力長 = |N| といういくつかの事実に同意しましょう。

  1. kここk=10では、スライディング ウィンドウを入力の上に移動する必要があります。したがって、あなたはO(|N|)以上と一緒に暮らす必要があります。
  2. ローリング ハッシュは、局所性に依存する決定論的ハッシュの形式です。決定論的ハッシュ化の欠点は、同様の文字列に頻繁に遭遇するほどハッシュ化が難しくなるため、ハッシュ化の利点が大幅に減少することです。
  3. 入力が長いほど、ハッシュの効果が低下します

これらの事実を考えると、「ローリング ハッシュ」はすぐに失敗します。染色体の 1/10 でさえ機能するローリング ハッシュを設計することはできません。

では、どのような代替手段がありますか?

  1. ブルームフィルター. 単純なハッシュよりもはるかに堅牢です。欠点は、誤検知がある場合があることです。ただし、これは複数のフィルターを使用することで軽減できます。
  2. Cuckoo ハッシュはブルーム フィルターに似ていますが、使用するメモリが少なく、局所性に敏感な「ハッシュ」と、最悪の場合の一定のルックアップ時間があります。
  3. サフィックス trieにすべてのサフィックスを貼り付けるだけです。これが完了したら、10少なくとも 2 つの子を持つ深さのすべての文字列を出力し、そのうちの 1 つが葉になります。
  4. サフィックス ツリーを使用して、サフィックス トライを改善します。ルックアップはそれほど単純ではありませんが、メモリ消費は少なくなります。
  5. 私のお気に入りはFM-Indexです。私の意見では、最もクリーンなソリューションは Burrows Wheeler Transform を使用することです。この手法は、Bowtie や BWA などの産業用ツールでも使用されています。
于 2018-07-18T18:03:01.463 に答える
1

あなたができることは、中国の剰余定理を使用して、いくつかの大きな素数を選択することです。思い出すと、CRT とは、余素モジュラスを持つ合同系が、すべてのモジュライの積をモジュラスとする一意の解を持つことを意味します。したがって、10^6+3、10^6+33、および 10^6+37 の 3 つのモジュラスがある場合、実際には、モジュラスのサイズは多かれ少なかれ 10^18 になります。モジュラスが十分に大きい場合、衝突が発生するという考えを多かれ少なかれ無視することができます。私のインストラクターが見事に述べたように、衝突が発生するよりも、コンピュータが自然に発火する可能性が高くなります。その衝突確率を好きなだけ任意に小さくします。

于 2018-07-18T17:23:27.303 に答える