Memory Efficient Minimum Substring Partitioning - todo314 @ ウィキ

Memory Efficient Minimum Substring Partitioning

• Yang Li, Pegah Kamousi, Fangqiu Han, Shengqi Yang, Xifeng Yan, Subhash Suri
• In VLDB
• 2013

アブスト

• 並列DNAシーケンス技術が進歩している
  • Illumina, SOLiD
  • Human Whole Genome Sequencingの値段: $3,750
• 数G個の断片をとってきて遺伝子全体の再構築
  • short read: A,C,G,Tからなる短いシーケンス
• 既存手法
  • ランダムサンプリングして、重複があるreadを拾ってくる
• readの長さ
  • 数十 ~ 数百
• De novo assembly
  • 適当にreadを拾ってきてくっつける処理
  • 色々手法がある、おおまかには
    • overlap-layout-concensus アプローチ
    • 小さければ…
    • de Bruijn graph アプローチ
    • k-mers に分割（長さkの部分文字列）
    • イイ感じにくっつけていく
    • 頂点: k-mers
    • k-mersを管理するのにはハッシュテーブル
    • メモリやばすぎ
• de Bruijn graphを構築したいのだけどメモリがやばい
  • 数百GB使う
• ディスクベースのアプローチ毀損の
  • 1
  • S: 短いreadの集合
  • S1,S2,…,Stに分割
  • Hi: Siのハッシュテーブル
  • Hiをソートしてディスクに書き出す
  • 2
  • 最後のいくつかの記号で分割
• ディスクベースの分割手法 Minimum Substring Partition(MSP) を考案
  • 10GB以内に収める
  • 減速なし
  • readを疎なのに分割してメモリに乗せるのは小数に？後でマージしてグラフ構築
  • 圧縮する
    • Θ(kn)->Θ(n)
    • n: データのサイズ
    • k: k-merの長さ
    • 文字列がランダムなモデルで
• 実験
  • めっちゃでかくてもde Bruijn graphが構築できた

事前知識

• short read
  • Σ上の文字列
• k-mer
  • 長さkの文字列
• short read sについて
  • s[i,j]: si,…,sjからなる文字列
• αとβがadjacent
  • αの最後k-1文字と、βの最初k-1文字が一致

• de Bruijn graphの例
  • ACCAACGTTG,AGCAACTCGT
  • 3文字ごとに分解
  • 最後と最初が一致したらつなぐ
  • 自分には繋がないのかな…？

k-mer Mapping

• 同じk-merを1つの頂点にまとめること
• de Bruijn graphの構築は…
  • k-mer mapping
  • 辺列の生成

Scatter/Gather

Horizontal Partition (H-Partition)

1. readの分割
   • S: 短いreadの集合
   • S1,…,St: Sの疎な分割
2. ハッシュテーブル構築
   • SiについてハッシュテーブルHiにk-merを挿入
   • 挿入順にID割当(1-index)
   • Mi: Siにおけるマッピング関数
3. 出力
   • Pi: Siについての出力
   • s_i,jとID
   • Piをマージして全体のマッピング関数Mを生成

• サイズ: Θ(kn)
  • n: readのサイズ

Bucket Partition

• 似たようなことをする

Minimum Substring Partitioning

minimum substring

• 定義
  • s: 文字列
  • r=$$ \min_p(s) $$がsのp-substringとは
    • rがsの長さpの部分文字列で辞書順最小

minimum substring partitioning

…

／(^o^)＼ｱｷﾗﾒﾀ

VLDB

2013-10-17 23:33:24 (Thu)