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)…まとまりの良さの分布的評価
  • ツールに引数があるとき、その引数が結果にどういう影響を与えているかを調べ、引数調整もしないといけない(評価尺度がよい方がよいが、ベストのものがよいのか、引数を調整してその評価尺度がどのように推移するかで選ぶのか、など、工夫はいる)