5. Deep Sequenceデータのアセンブル・アルゴリズム。基礎と気をつけるべきこと:ぱらぱらめくる『Deep Sequencing Data Analysis』

  • どうして難しいか
    • ゲノム上に似た配列が山ほどある
    • 読まれたリードにエラーがある
    • バレージが不均一
    • PCR増幅の影響
    • データ量が莫大
  • 明るい側面
    • Paired-end(で情報量が多い)と楽
  • De novo assemblyのツール
    • Edena,CABOG,De Bruijn graph,SOAPdenovo,MetaVelvet,Strig graph,SGA
  • 使われるアルゴリズム・理論
    • いわゆるグラフ理論に基づくアセンブリ
      • グラフ上のパス探索問題にして解く
    • OLC(Overlap-layout-consensus) graph/String graphに基づくアセンブリ
      • リードをノードに、オーバーラップがあることをエッジにしてグラフを作り、そのグラフにパスを見つける
    • De Bruijn graphにして解く
      • リードを細断して、細断片をノードにもとのリードのつながりをエッジにしておき、その上で、同一細断配列のノードを合併してグラフを作り、そのグラフ上でオイラーパスを探索する(こちらがわかりやすい)
  • アセンブル結果の評価
    • いくつのcontingsにまとまったか
    • 結局、何塩基がまとまったか(どれくらい残ったか)
    • 長いcontigsから数えて全体の半分がまとまるのに必要なcontigsを取ったら、その最短contigの長さはいくつか(N50)…まとまりの良さの分布的評価
    • ツールに引数があるとき、その引数が結果にどういう影響を与えているかを調べ、引数調整もしないといけない(評価尺度がよい方がよいが、ベストのものがよいのか、引数を調整してその評価尺度がどのように推移するかで選ぶのか、など、工夫はいる)