Perfect Phylogeny HaplotypingとGraph Realization problem

Diploidのジェノタイプデータから、ハプロタイプを推定する方法はいくつか(も)知られているが、そのようにして推定されたハプロタイプが、「ARG(Ancestral Recombination Graph)を描けるか＝祖先ハプロタイプからのCoalescenceとRecombinationとからできてきたものであるとして系統樹に描けるか」というとそうではない。では、「完全系統樹＝Perfect Phylogeny」を描けるようなハプロタイプを推定してやれば、よい、ということから、ジェノタイプデータからのハプロタイプ推定を「完全系統樹作成問題」に置き換えたのが「Perfect Phylogeny Haplotyping Probmlem」である。

系統樹が描けるかという問題は、グラフが描けるかという数学の問題として扱えるので、この問題は、「Graph realization problem」にも置き換えられる。

今日のこのノートには、Graph reallization problemをNear linear-timeで解くフリーソフトウェアと、その出力ファイルをグラフに描くソフトウェアのダウンロードについて記すこととする。

Graph realization problemのソフトウェア

GREAL Graph realization から、WINDOWS用　GREAL.zipをダウンロードし、自己解凍でインストールする。実行すると、RESULT_nearto_format.txt というファイルができる。なお、GREALはグラフを描くことに失敗することもある。

このファイルを図にするには、同じくフリーのソフトウェア　Graphviz Graphviz から、graphviz-2.2.1.exe　をダウンロードし、やはり、自己解凍でインストールする。このgraphvizにさきほどGREALが作成した　neartoフォーマットのファイルを読ませると、添付のようなグラフになる。

neartoフォーマットとは、こんな感じ(添付画像の元データ)

graph realization { n0 [shape=ellipse];n1 [shape=ellipse];n2 [shape=ellipse];n3 [shape=ellipse];n4 [shape=ellipse];n5 [shape=ellipse];n6 [shape=ellipse];n7 [shape=ellipse];n8 [shape=ellipse];n9 [shape=ellipse];n10 [shape=ellipse];n11 [shape=ellipse];n12 [shape=ellipse];n13 [shape=ellipse];n14 [shape=ellipse];n15 [shape=ellipse];n16 [shape=ellipse];n17 [shape=ellipse];n18 [shape=ellipse];n1--n0 [label="2",len=1.5] ;n2--n0 [label="0",len=1.5] ;n3--n0 [label="1",len=1.5] ;n4--n1 [label="3",len=1.5] ;n5--n1 [label="4",len=1.5] ;n6--n1 [label="5",len=1.5] ;n7--n1 [label="16",len=1.5] ;n8--n6 [label="6",len=1.5] ;n9--n6 [label="9",len=1.5] ;n11--n6 [label="15",len=1.5] ;n12--n6 [label="17",len=1.5] ;n13--n8 [label="7",len=1.5] ;n14--n8 [label="8",len=1.5] ;n10--n9 [label="10",len=1.5] ;n17--n13 [label="11",len=1.5] ;n18--n13 [label="12",len=1.5] ;n15--n14 [label="13",len=1.5] ;n16--n14 [label="14",len=1.5] }

※　このノートの元文献はno titleで。