2016-01-15

アラインメントアルゴリズムをレビューする：クリニカルシークエンシングのために

論文クリニカルシークエンスアラインメント

FDAがプレシジョン・メディシンを念頭に、シークエンシングのアラインメント・アルゴリズムのレビューをしました(その紹介記事、そのレポート)
これをアラインメント・アルゴリズムの紹介記事と考えて、Short Readsのアラインメントがなんたるかがわかっている人を対象に説明することを念頭にして、少し丁寧に読んでみます
タイトル：Alignment of Short Reads: A Crucial Step for Application of Next-Generation Sequencing Data in Precision Medicine
1. Introduction
- NGSとShort Readsの活用に関する概説
2. Strategies of Current Alignment Algorithms
- 原則
  - Short readをレファレンスゲノム配列に当てたときに、一致箇所・不一致箇所がどうなるかによって、scoreをつけて、マップされるべき位置を特定しようとする
  - 不一致箇所として、In/DelとSubstitutionとが(通常)考慮される
- アラインメント・アルゴリズムは大きく２つに分類される
  - (1) Seed and Extend
  - (2) q-grams filter
- アラインメントするにあたって、メモリ活用という側面から採用されるアルゴリズムとして、いくつかのIndex法が採用される
  - Hash-table
  - FM-index(Borrows-Wheeler Transformation-based)
- 2.1. Seed-and-Extend Strategy
  - (i)Seed
    - ショートリード上の部分k-merセグメントを「スライディング・ウィンドウ」にて作る→実習で確かめる
    - そのようにしてできたk-mer seedがリファレンスゲノムにマッチするかどうかをindex法の一つによって見出す→実習で確かめる
  - (ii)Extend
    - 左右に一つずつ伸ばす
    - 伸ばしてよいかどうかの判定をする。判定するために判定基準 constraintsを決める→実習で確かめる
  - (iii)Final alignment
    - "Standard" "dynamic programs"を使って、レファレンス配列のどこにするかを最終的に決める
  - どこに時間がかかるか：(ii)
    - ショートリードからできたseedsのいずれもが、全長までextend出来ないときに、特に時間がかかる。すべてのseedsについてやり続けないといけないから。１つでも全長カバーすれば、他のseedからスタートしてもscoreは同じになるので、それについてはやる必要がない→実習で確かめる
  - "Seed filtration":時間を節約するために
    - Seed -> Seed-filtration -> Extension -> Final-alignment
  - "Impact of seed length"
    - "Shorter seeds increase sensitivity, longer seeds increase speed"
- 2.1.1. k-mer Exact Match Seed
  - Final aligmentにDynamic programming
    - Smith-Watermanか
    - Base qualityを考慮したNeedleman-Wunschか
    - ここで知るべきこと
      - "Dynamic programming"とは何か
      - 配列アラインメントというコンテクストでは"Dynamic programming"とはどういうことをするのか、SWとNWに共通することは何か
      - 両者の違いは(このコンテクストで)何か
      - メモリ負荷に留意すると、Seed-and-extensionにおける意味づけもわかる
    - 11-mer, 9-merと手法の効率との関係
- 2.1.2. k-mer Inexact Match Seed
  - 鳩ノ巣原理、長さn、m個のミスマッチ、k=n/(m+1)。必ず一つはExact matchなk-mer
  - Exact matchなk-merを探している
  - Inexact match seedを用いるアルゴリズムでのマッピングステップの加速について書いている(BWT、インデックス法、並列処理(GPU))
  - "Bowtie generates k-mer inexact match seeds with at most three(default two) mismatches in the high-quality end of a read(default: the first 28 bp in the read)" の意味が解るだろうか
    - ショートリードの片側はもう片側よりクオリティがよいので、その酔い側のある長さについて、k-mer inexactを実施するという意味
- 2.1.3. k-mer Spaced Seed
- 2.1.4. Maximum Extend Match(MEM) Seed
- 2.1.5. Adaptive Seed
- 2.2. q-gram filter
  - ショートリードを分割する
  - それをマッピングする
  - 多くのグラムがマッピングされたあたりが本物であろうと考えて、そこにリードをアラインメントする
  - Extensionしない
  - In/Delに強い→実習で確かめる
  - "predetermined positions such as SNP sites in a reference genome are not required"とは
  - hit箇所を探す実習
Index法(この記事では対象としていないが、勉強しておこう)
- Hash-table
- FM-index