一分子シーケンサPacBioを用いた
低メチル化領域検出
東大院・新領域・情報生命 森下研究室
鈴木 裕太
2014/07/26
Plan of this talk
●
PacBio による DNA 修飾計測の原理
–
分割問題として解く
●
分割アルゴリズムの一般的な定式化
●
重み最大区間検出(MSS)問題とその変種
–
(constrained) kmaximal segment sum
–
DNA トポロジカルドメインの検出
PacBio による DNA 修飾計測の原理
●
●
シーケンサとしての PacBio の特性
–
長いリード (~20 kbp)
–
増幅を経ないサンプルの一分子計測
ヌクレオチド取込みの時系列はDNA修飾を反映 D'
Inter Pulse Duration (IPD)
Copyrighted Material
IPD ratio = D' / D
D
Flusberg et al. (2010)
基本となるアイディア
●
最もシンプルなモデル (失敗)
is_methylated (position) := (average IPD ratio of that position) > threshold
●
–
信頼できる平均値を得るために大量のデータが必要
–
ゲノムサイズの小さなバクテリア・ウイルスに限られる
知識を取り入れたモデル
is_methylated (region) := (average IPD ratio of that region) > threshold
–
領域ごとのメチル化状態を考える
–
(resolution を下げて精度を追求)
–
CpG sites だけを考慮
分割問題として解く
●
全CpG sitesの列を、(高/低)メチル化領域へ分割
1.各CpG sites に対し、(高/低)メチル化領域へ分類した
ときのスコアを付与
スコアは、IPD ratio と coverage で決める
2.制約の下で、スコアの和が最大になる分割を探す
制約を付けなければ、自明な解(各位置を独立にスコアが大きい方へ分類す
る)が得られてしまう。ここでは、以下の制約を考える。
得られた各領域は 少なくとも 50 CpG sites を含む
(最小長さに関する制約)
アルゴリズムの設計
●
●
●
●
入力
–
{ski} : 位置 i をクラス k へ分類した場合のスコア (1≦i≦N, 1≦k≦K)
–
lk : クラス k へ分類される区間の最小サイズ (1≦k≦K)
–
{ci} : サイズの制約を満たし、スコアの和を最大化する位置ごとの分類
出力
動的計画法を用いるため、部分問題の解 Sk(i) を「1～ i までの分類で、全ての制
約を満たし、位置 i がクラス k へ分類されているものの最大スコア」と定義する
Sk(i) は以下の再帰式で順次求まる
Sk(i) = max of { Sk(i-1) + ski ,
max_k' {Sk'(i-lk)} + Σskj } (i-lk+1≦ j≦i)
Csuros (2004) のアルゴリズムと本質的に同一
得られた分類の精度
Treated Hypomethylation as positive, checked prediction for each CpG site.
(data from medaka fish, used bisulfite data as ground truth.)
x: Sensitivity(Recall) = #TP / (#TP + #FN) y: Precision = #TP / (#TP + #FP)
Regional prediction
Positionwise prediction
Copyrighted Material
他の手法との関連
●
HMM
–
●
●
区間の長さは transition prob. を通して制御
される (幾何分布を暗に仮定)
HSMM (Hidden SemiMarkov Model)
–
区間の長さの分布を指定できる。
–
多くのアルゴリズムが O(n^2) で走る
区間分割に基づく手法はHSMMと重なる部分も多い
が、確率モデルの枠組みから離れた問題にも適用で
きる(スコアが常に対数尤度のような解釈を許す訳で
はない：スケジューリング問題など)
アルゴリズムの設計(再掲)
●
●
●
●
入力
–
{ski} : 位置 i をクラス k へ分類した場合のスコア (1≦i≦N, 1≦k≦K)
–
lk : クラス k へ分類される区間の最小サイズ (1≦k≦K)
–
{ci} : サイズの制約を満たし、スコアの和を最大化する位置ごとの分類
出力
動的計画法を用いるため、部分問題の解 Sk(i) を「1～ i までの分類で、全ての制
約を満たし、位置 i がクラス k へ分類されているものの最大スコア」と定義する
Sk(i) は以下の再帰式で順次求まる
Sk(i) = max of { Sk(i-1) + ski ,
max_k' {Sk'(i-lk)} + Σskj } (i-lk+1≦ j≦i)
Csűrös /tʃyːroːʃ/ (2004) のアルゴリズムと本質的に同一
アルゴリズムの設計(拡張1)
一様でない長さ
●
●
●
●
入力
–
{ski} : 位置 i をクラス k へ分類した場合のスコア (1≦i≦N, 1≦k≦K)
–
{λki } : 位置 i をクラス k へ分類した場合の”長さ” (1≦i≦N, 1≦k≦K)
–
lk : クラス k へ分類される区間の最小サイズ (1≦k≦K)
動的計画法を用いるため、部分問題の解 Sk(i) を「1～ i までの分類で、全ての制
約を満たし、位置 i がクラス k へ分類されているものの最大スコア」と定義する
Lk(i) : i で終わるクラス k の最小の区間の開始位置 ← {λki } から計算
Sk(i) は以下の再帰式で順次求まる
Sk(i) = max of { Sk(i-1) + ski ,
max(k', l){Sk'(l)} + Σskj } (Lk(i-1)< l ≦ Lk(i+1), l+1≦ j≦i)
アルゴリズムの設計(拡張2)
単調な制約
●
入力
–
{ski} : 位置 i をクラス k へ分類した場合のスコア (1≦i≦N, 1≦k≦K)
–
accept(i, j, k): クラス k の区間 [i .. j] が制約を満たすか判定する関数
accept(i, j, k) => forall i' ≦ i, j ≦ j', accept(i', j', k) (単調性)
●
●
●
動的計画法を用いるため、部分問題の解 Sk(i) を「1～ i までの分類で、全ての制
約を満たし、位置 i がクラス k へ分類されているものの最大スコア」と定義する
Lk(i) : i で終わるクラス k の最小の区間の開始位置 ← accept() から計算
Sk(i) は以下の再帰式で順次求まる
Sk(i) = max of { Sk(i-1) + ski ,
max(k', l){Sk'(l)} + Σskj } (Lk(i-1)< l ≦ Lk(i+1), l+1≦ j≦i)
ここまでのまとめ
●
PacBio を用いた(高/低)メチル化領域の検出
を分割問題として定式化して良い精度を得た
–
●
リード長を生かして、トランスポゾン上やアレル
間のメチル化解析へ応用できる？
Csűrös のアルゴリズムを拡張し、一様でない
長さや、単調な制約に対しての線形アルゴリズ
ムを得た
–
–
エピジェネティクスへの応用
アルゴリズムは線形で単純
(← Program derivation 等で導出できる...?)
Plan of this talk
●
PacBio による DNA 修飾計測の原理
–
分割問題として解く
●
分割アルゴリズムの一般的な定式化
●
重み最大区間検出(MSS)問題とその変種
–
(constrained) kmaximal segment sum
–
DNA トポロジカルドメインの検出
色々な Maximal Segment Sum 問題
オリジナルのMaximal Segment Sum
入力： 実数の列
出力： 和が最大となる一つの区間
Maximal Sum Segment (MSS)は、次の
ような仕様で記述される問題へ発展
入力： 実数（の組）の列
出力： 何らかの基準で最良となる 区間（の組）
例えば、
- 平均値を最大化する区間を求める
- 区間の長さに制約(上限 and/or 下限)
- 重ならない k 個の区間を求める
- 重なっても良い k 個の区間を求める
= 1～k 番目に最良の区間を求めるこ
とに相当
DNA トポロジカルドメイン検出
トポロジカル ドメイン(TD) = 物理的に近接している連続した領域
(「ドメイン内の相互作用 >> ドメイン間の相互作用」という関係により定義)
Hi-C 法で得られたデータ(近接ペアの情報)からHMMなどで予測されるが...
- 多数の細胞集団に由来する情報を、単一の分割へ集約できるのか？
- ドメインの [左半分] と [右半分] の長さは独立ではない
- ドメインの長さが幾何分布に従う根拠は無い
そこで「1～ k 番目に良い(TDらしい)領域」を探し出したらどうだろうか？
→ MSS 問題の変種として高速に実行可能 (と思われる) まとめ
●
●
PacBio によるメチル化計測
–
最小長さの制約を付けて分割
–
さらに Csűrös の方法の拡張を考えた
–
どんな自然な応用があるか？
DNAトポロジカルドメインの検出
–
細胞集団のheterogeneityを考慮した定式化
© Copyright 2024 ExpyDoc
