PPH
参照文献：Mary Ann Liebert, Inc. - Journal of Computational Biology - 10(3-4):323
- 論理説明に用いられる用語の定義
- PPH問題(Perfect Phylogeny Haplotyping Problem)
- Unphased data(SNPのdiploid genotype data)が与えられたときに、そこから、「組換え」を仮定せずに、「相互に矛盾のないハプロタイプのセット」をすべての個人に与えることができるかどうか
- Matrices
- M:Genotype matrix (n人ｘm個(SNP):n rowsはs(speceies)に対応、m columnsはpolymorphic sitesに対応)
- M':Haplotype matrix (2n本(haplotype)ｘm個(SNP))
- Haplotype inference
- MからM'を推定する作業
- "M' is an expansion of M"
- Perfect phylogeny
- Perfect phylogenyはMに対して定義される
- Perfect phylogenyのはTree(木)型のグラフである
- Perfect phylogenyは2n枚のleaf(葉)を持つ
- 2n枚の葉はそれぞれ、n人の2n本のhaplotypeに相当する
- m個のpolymorphismはTのedgeのいずれか１つに相当する(mutationの発生に対応する)
- infinite-sitesモデルを採用しているので、個々のpolymorphismは1edgeにのみ対応する
- また、すべてのpolymorphismは相互に異なるedgeに対応する
- leafを端点に持たないedgeは必ずpolymorphismに対応する
- 任意の2leaves間の道(path)を構成するedgesに対応するpolymorophismについて、2leavesが対応するハプロタイプでは値がことなる、その逆に、pathの構成edgesに対応するpolymorphism以外においては値が一致する
- forced と inferred
- Complete-pair-matrixとは
- m polymorphismsについて推定するにあたり、2 polymorphismsの作る多型ペアに着目する
- M'(2n x m; haplotype matrix)から2カラムを取り出したsub-matrixの2カラムに{0,0},{0,1},{1,0},{1,1}の４パターンがある場合にこれをComplete-pair-matrixと呼ぶ
- Complete-pair-matrixがを構成する２多型の間には、infinite-sites モデルにおいては、組換えが必ずあることが知られており、perfect phylogenyを解として持たない
- pph-pair
- m polymorphismsについて推定するにあたり、2 polymorphismsの作る多型ペアに着目する
- Complete-pair matrixのときにはM'のsub-matrixについて検討したが、今回は、M(n x m; genotype matrix)の２カラムのsub-matrixについて、2重ヘテロの個体以外のデータから、「確定的」にcomplete-pair-matrix({0,0},{0,1},{1,0},{1,1})が生じないとき、このSNPペアをpph-pairと呼ぶ
- pph-pairでないSNPペアを含むMには、perfect phylogenyである解が得---Four gamete testと同義である
- 逆は真ではない。Mがつくるすべての2カラムのsub-matrixがpph-pairであっても、perfect phylogeny解が存在するとは限らない
- pph-pairか否かの判断はfour-gamete testと同義である
- Companions
- equate/negateの記号化
- equate,negateを記号化して取り扱う
- E(i,j1,j2)を、SNPj1-j2においてcompanionである個体iのequate/negateを記号化したものとする
- M'[i,j1]とM'[i,j2]とを0(true),1(false)で表現したときのEXCLUSIVE-ORがE(i,j1,j2)になっている
- equate/negateの関係をM'の要素EXCLUSIVE-ORで扱うことにより、３個以上のSNPセットにてすべてcompanionsの関係にあるSNPsとそれが作るハプロタイプの一意的推定についての論理展開が容易に行えるようになる
- CompanionsなSNPペアにおいて、{ホモ、ヘテロ}、{ヘテロ、ホモ}という個体の存在は、このSNPペアにおけるcompanion個体のequate/negate選択をforcedに決定する
- このようなSNPペアをforcing patternを有するcomparison columnsであると言う
- PPH問題(Perfect Phylogeny Haplotyping Problem)
- PPHによるハプロタイプフェージング
- グラフの作成
- グラフは点(vertex)の集合と、辺(edge)の集合からなる
- 今、PPHを解くにあたり、次のような点と辺の構成のグラフを作成する
- 点をMのカラム(多型)とする
- 辺は２多型間の関係とする
- 相互にcomparison関係にあるcolumns間を辺で結ぶ
- ２多型間の関係には２種類を定義し、その和をグラフの構成辺とする
- 第１の２多型間関係(第１の辺集合)：Ef
- Forcing patternを持つcomparison columns同士を結ぶ辺
- 第２の２多型間関係(第２の辺集合)：En
- forcing patternを持たないcomparison columns同士を結ぶ辺
- 第１の２多型間関係(第１の辺集合)：Ef
- Efにおいては、eaquate/negate値がすでに確定している
- Enにおいては、eaquate/negate値は不確定状態であるが、その値の取り方、ノード・辺との関係において制約がある
- Efに属する辺が作る単連結グラフ(グラフ全体のうちの１部(部分グラフ))においてフェージングする
- 一意解が求まることが知られている
- 添付図の左上の図に相当する
- グラフ全体は、１個以上のEf辺が作る単連結部分グラフ(一意解が得られた)と、それを結ぶEn辺(このような辺をEf要素が作る部分グラフのcrossと呼ぶ)とが作るmulti-graph H (多重グラフ(２ノード間を結ぶ辺が複数本、存在する))とが形成される
- すべての辺はEnに属する
- 添付図の右上の図に相当する
- Hを構成する辺から次のような基準で統合ノードと辺とを選び、グラフ T を得る
- 作成するグラフは"spanning tree"である
- spanningであるから、すべての統合ノードが含まれる
- treeであるからサイクルを含まない
- 添付図のしたの図に相当する
- 作成するグラフは"spanning tree"である
- Tについてperfect phylogenyが得られるかどうかをpph-pairチェックなどで確認する
- TはEnの辺からなるので、その辺にそれぞれ、eaquate/negateのいずれかを割り当てる
- Tにk個のEn辺が含まれていれば、2^kの場合わけが存在する
- 割り当てにあたっては、Mの段階で、forcing patternが発生するようにgenotypeを与える
- Enのまま取り扱うと、一意な解が得られるかどうかは不明であるが、eaquate/negateを強制して選ばれた解は一意性がある
- spanning treeのノードの数はm以下(mは多型数)であり、spanning treeの辺の数はノードの数より１小さいから、k<mである</li>
- このアルゴリズムでの探索は、解があるならば、それが一意解であり、それに到達することを保証している
- グラフの作成
アルゴリズムのエッセンス
Step 1:O(nm^2)
グラフの作成
すべてのSNPペアに対して、pph-pairチェックを行う
合格したらStep 2へ
Step 2:O(m^2)
不確定な辺にeaquate/negate設定をする
Step 3:O(nm)
Step 2を受けてgenotype matrixを作成する
Step 4:O(nm)
Perfect phylogeny recognition algorithmにより、できた「解」が適切であるかをチェックする
- PPHアルゴリズムの特徴(その他のハプロタイプフェージング方法との比較)
- 適用対象
- 組換えのおきていない「ブロック」を対象とする
- BialleleicなSNPのUnphased diploidデータを対象とし、個人のhaplotypeセットを推定する
- 適用対象
- Phasing方法としての特徴
- Deterministicな解が得られる(ただし、解が求められる場合)
- 解が得られるために、「すべての個体でヘテロ」であるSNPを含まないこと」を必要条件とする
