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を構築したいのだけどメモリがやばい
-
ディスクベースのアプローチ毀損の
-
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
-
short read sについて
-
αとβがadjacent
-
de Bruijn graphの例
-
ACCAACGTTG,AGCAACTCGT
-
3文字ごとに分解
-
最後と最初が一致したらつなぐ
-
自分には繋がないのかな…?
k-mer Mapping
-
同じk-merを1つの頂点にまとめること
-
de Bruijn graphの構築は…
Scatter/Gather
Horizontal Partition (H-Partition)
-
readの分割
-
S: 短いreadの集合
-
S1,…,St: Sの疎な分割
-
ハッシュテーブル構築
-
SiについてハッシュテーブルHiにk-merを挿入
-
挿入順にID割当(1-index)
-
Mi: Siにおけるマッピング関数
-
出力
Bucket Partition
Minimum Substring Partitioning
minimum substring
-
定義
-
s: 文字列
-
r=$$ \min_p(s) $$がsのp-substringとは
minimum substring partitioning
…
/(^o^)\アキラメタ
VLDB
2013-10-17 23:33:24 (Thu)
最終更新:2013年10月17日 23:33