私は、ゲノムの文字列を所有し、効率的に同じ部分

Question

補足データリンク検索方法：限りhttps://pan.baidu.com/s/1sllFLAdが

各文字列の長さは、23です：

• 候補：https://pan.baidu.com/s/1nvGWbrV
• Bg_dbをデータは大きすぎるので、私は1theの5分の1を渡すだけで、コードを貼り付けることができる速く、兄がそれを読んでいただき、ありがとう！

  ここで正式な質問です：

  私は今、2つの文字列の配列を持って、暫定的にCandidatesとBg_dbと呼ばれるが、それらのすべては、長さ20の短い文字列で、各文字列は次の4つの中の文字が含まれています：A、T 、C、G（！右のゲノム配列です！）：

  Candidates = [ 
      'GGGAGCAGGCAAGGACTCTG', 
      'GCTCGGGCTTGTCCACAGGA', 
      '...', 
      # Be you see, these fragments of human genes in fact 
  ] 
  
  Bg_db = [ 
      'CTGCTGACGGGTGACACCCA', 
      'AGGAACTGGTGCTTGATGGC', 
      '...', 
      # This more, there are about one billion 
  ] 
  

  私の仕事は、例えば、レコード内のすべての以下Bg_db 4違い、見つけるために、各候補の候補にある：

  をあなたはすぐに見つけた場合

  私の問題は、次のとおりです。すべてのレコードの以下の4の違いとBg_db内のすべての候補者、もし一例として、そして暴力的トラバーサル、パイソンの使用：

  def align (candidate, record_from_bg_db): 
      Mismatches = 0 
      For i in range (20): 
          If candidate [i]! = Record_from_bg_db [i]: 
              Mismatches + = 1 
              If mismatches> = 4: 
                  Return False 
      Return True 
  
  Candidate = 'GGGAGCAGGCAAGGACTCTG' 
  Record_from_bg_db = 'CTGCTGACGGGTGACACCCA' 
  
  Align(candidate, record_from_bg_db) # 1.24 microseconds or so 
  
  # total time: 
  
  10000000 * 1000000000 * 1.24/1000/1000/60/60/24/365 
  # = 393 
  # 1 million candidates, 1 billion bg_db records 
  # Takes about 393 years 
  # Completely unbearable ah 
  

  私の考えは、Bg_dbは非常に順序付けられた文字列（各文字の長さはわずか4かもしれません）であり、候補者がアドバイスを求めるBg_dbをすばやく比較できるアルゴリズムはありません。

Answer 1

上記の説明は正式にハミング距離と呼ばれています。あなたはここで多くを読むことができます：

https://en.wikipedia.org/wiki/Hamming_distance

を上記のリンクで声明を開く言い換えするには、次の情報理論では

、 同じ長さの2つの文字列の間のハミング距離が位置の数であります対応する シンボルが異なる。別の方法としては、ある文字列を他の文字列に変更するために必要な置換の最小数 を測定します。 に1つの文字列を変換した可能性のあるエラーの最小数は です。

これを改善する簡単な方法は、> 4の不一致を観察するときに文字列比較を終了することですが、多数の不一致を含む文字列比較が多い場合にのみ実行時間が短縮されます。

また、Burrow-Wheeler変換（BWT）を実装するアルゴリズムなど、より新しいアルゴリズムを使用することもできます。ここに完全なリストを参照してください。

https://en.wikipedia.org/wiki/List_of_sequence_alignment_software#Short-read_sequence_alignment

をBWTソフトウェアツールを使用して、私の提案は、単一ターゲットに配列データセットのいずれかを連結することであろうシーケンス、その後、クエリそれは、他のセットを使用して短い配列。なぜなら、BWTアルゴリズムは、ターゲットが、ヒトゲノムからの染色体のようないくつかの大きな配列からなるときに、よく機能するからである。アラインメントを取得すると、ターゲットシーケンスに結合した位置、つまり正確な倍数20の位置合わせにまたがるアラインメントを除外することができます。

BWTベースのツールは通常、過去のDNA配列アライメントアルゴリズムと、あなたが提示した使用例、すなわち短い配列のギャップのないアライメントは、これらのプログラムが最適化するように設計されたものです。

これは宿題でない限り、あなたが最も必要とするソフトウェアツールの種類を調べることをお勧めします。独自の配列アラインメントアルゴリズムを開発することは（個人的な経験から）困難であり、既存のツールを適切に評価するのに費やされる時間は、ソフトウェアの開発に費やされた時間が価値あるものかどうかを判断するのに役立ちます。