第 3 章 シミュレーション 62
3.7 CCPD によって求めた周辺事後確率の偏りの指標
り返し数は4であるが，各プール内のクローンの数は一定ではなく，
プール内のクローン数の平均値は 36 である．
Design III 繰り返し数もクローンが入っているプールの数も一定ではな いランダムなデザインである．ただし，繰り返し数の平均は4，プー ル内のクローンの数の平均は36 である．
図3.7，図3.8および図3.9，図3.10からBIB design (Design I)，Design
II，Design III の順で高いスクリーニング能力が得られることがわかる．
これは BIB design や packing design のような計画的なプーリングデザ インのほうがランダムなデザインよりスクリーニング能力が高いことを意 味している．Designs IIとIIIの比較からもランダムな繰り返し数を持つ デザインより「繰り返し数一定」のデザインが望ましいことがわかる．
注意: LDPC 符号の場合には各クローンの繰り返し数が一定ではないあ る種のパリティ検査行列の中に誤り訂正能力が高い符号が存在することが 知られているがグループテストの場合にも同様のことが言えるか否かはわ かっていない．
0 50 100 150 200 250 300
0 2 4 6 8 10
R1(κ,A)
order (κ) Design I Design II Design III
(1)ポジティブクローンの数: d= 1 の場合
0 50 100 150 200 250 300
0 5 10 15 20
R2(κ,A)
order (κ) Design I Design II Design III
(2)ポジティブクローンの数: d= 2 の場合
図 3.7: ポジティブクローンのスクリーニング能力 (n= 981, m = 109， 誤り確率 (P1))
表3.16: KL情報量の差(n= 1552,m= 97, λ= 2) ポジティブクローンの数 CCPD CCPD + 偏り補正
d= 1 0.000003 0.000003
d= 2 0.000007 0.000007
d= 3 0.000021 0.000007
d= 4 0.000013 0.000011
0 50 100 150 200 250 300
0 5 10 15 20 25 30
R3(κ,A)
order (κ) Design I Design II Design III
(3)ポジティブクローンの数: d= 3 の場合
0 50 100 150 200 250 300
0 5 10 15 20 25 30 35 40 R4(κ,A)
order (κ) Design I Design II Design III
(4)ポジティブクローンの数: d= 4 の場合
図 3.8: ポジティブクローンのスクリーニング能力 (n= 981, m = 109， 誤り確率 (P1))
表3.17: KL情報量の差(n= 1314,m= 73, λ= 3) ポジティブクローンの数 CCPD CCPD + 偏り補正
d= 1 0.000026 0.000011
d= 2 0.000005 0.000006
d= 3 0.000084 0.000117
d= 4 0.000023 0.000028
0 50 100 150 200 250 300
0 2 4 6 8 10
R1(κ,A)
order (κ) Design I Design II Design III
(1)ポジティブクローンの数: d= 1 の場合
0 50 100 150 200 250 300
0 5 10 15 20
R2(κ,A)
order (κ) Design I Design II Design III
(2)ポジティブクローンの数: d= 2 の場合
図 3.9: ポジティブクローンのスクリーニング能力 (n= 981, m = 109， 誤り確率 (P2))
0 50 100 150 200 250 300
0 5 10 15 20 25 30
R3(κ,A)
order (κ) Design I Design II Design III
(3)ポジティブクローンの数: d= 3 の場合
0 50 100 150 200 250 300
0 5 10 15 20 25 30 35 40 R4(κ,A)
order (κ) Design I Design II Design III
(4)ポジティブクローンの数: d= 4 の場合
図 3.10: ポジティブクローンのスクリーニング能力 (n= 981, m= 109， 誤り確率 (P2))
表3.16ではλ= 2 であり，ポジティブクローンの数が3 個以上のとき 偏り補正によって精度が上がっている．一方，λ= 3 の場合，表3.17 で はポジティブクローンの数が 2 個以上のとき偏り補正の効果が見られな い．これは，会合数 λの値が大きくなるとタナーグラフに長さ4 の閉路 が増加し，同時に長さ 6 以上の閉路もそれに伴って増加するために，よ り高次の偏り項が影響しているからではないかと思われる．λが大きいと
きには，2.5.2節の 2次の補正項だけでなくより高次の項も考慮して偏り
補正を行う必要があると思われる．
第 4 章 結論
本論文では，第2章でグループテストにもとづく2つの事後確率の近似 計算アルゴリズムBNPD，CCPDを提案した．本論文で提案したBNPD は確率伝播法にもとづいて周辺事後確率を計算するアルゴリズムである が，通常の確率伝搬法に現れる2r 個(r はプールの大きさ)の和の計算を
余事象の belief に置き換えることにより簡略化し，計算量を少なくして
いるため，実行速度が速い．CCPD アルゴリズムにも同様の高速化がな されている．また，BNPDおよびCCPDにより求めた周辺事後確率の推 定値の偏りの解析を通して，unique collineality conditionを満たすプー リングデザインを用いてグループテストを行った際のBNPDにより求め た周辺事後確率の推定値の近似の良さを理論的に示した．
第 3 章では，BNPD，CCPD，MCPD の 3 つのアルゴリズムのスク リーニング効率，実行速度などをシミュレーションにより比較した．まず，
MCPDはシミュレーションにより周辺事後確率を計算するアルゴリズム のため，反復回数を増やすと近似精度が高くなるが，反復回数に比例して 実行時間が長くなる．特に高い確率でポジティブクローンをスクリーニン グするためには，MCPDではアルゴリズムの反復数をより多くとる必要 があり，要求される確率が高くなるに従い，反復数も多くしなければなら ない．また，MCPDの収束に必要な反復数は偽ポジティブ・偽ネガティ ブの確率分布に大きく左右され，偽ポジティブ・偽ネガティブの確率が指 数的に減少する(P2)の場合には，少ない反復回数で十分なスクリーニン グ能力が得られるが，偽ポジティブ・偽ネガティブの確率が (P1)および
(P3)の場合には，近似精度を BNPDやCCPD と同じ程度にするために は，非常に大きな反復回数が必要となる．また，MCPDはポジティブク ローンの数dが多くなるに従い反復回数を大きくしなければならない．
一方，BNPD, CCPDはクローン数やポジティブクローンの数には大き
く左右されず，数回，数十回程度で収束する．その近似精度はプーリングデ ザインに大きく依存して決まり，プーリングデザインがunique collinearity condition を満たす，すなわち，packing designであるときには，周辺事 後確率の推定値の近似精度が高い．しかし，プールの数が少なく packing
designを用いることができない場合には，タナーグラフに長さが 4 の閉
路が存在し，このような閉路が多く存在するとBNPDは収束しなくなる．
また，ポジティブクローンの数が増加するに従い，BNPD が収束する比 率は小さくなる傾向がある．CCPD は長さ4 の閉路が多く存在しても収 束するが，周辺事後確率の推定値の偏りは長さ 4 の閉路がないときに比 べて大きく十分な反復の後ではMCPD の近似精度を下回る．しかし，実 行速度は BNPD, CCPD, MCPDの順に速い．
したがって，プーリングデザインにpacking design を用いることがで きる場合には長さ4の閉路が存在しないためBNPDのスクリーニング能 力は十分高く，実行速度も速い．一方，packing design を用いることがで きない場合は，CCPD を用いれば短い計算時間で一定のスクリーニング 能力が得られる．さらに高いスクリーニング能力を得るには，CCPD に より求めた周辺事後確率の推定値を初期値として，MCPD を十分な回数 実行するハイブリッドアルゴリズムを用いることができれば，MCPDを 単独で実行するより速く，しかも十分なスクリーニング能力が得られる (図4.1)．
3.6.1節のシミュレーションの結果より，packing design を用いた場合，
各クローンの繰り返し数 k が 3 と 4 の間に大きなスクリーニング能力 の差があるので，k は少なくとも 4 以上であることが望ましい．また，
3.6.2節のシミュレーションの結果より，BIB design (packing design)を 用いるとランダムにデザインを作るよりスクリーニング能力が高くなる．
さらに，3.7節のシミュレーションの結果より，BIB designを用いた場 合，2 つのプール Gと H の会合数 |G∩H| が小さければ2.5 節の偏り
開始
プ ー リ ン グ デ ザ イ ン に packing designを用いる ことができるか?
packing designを用いてプーリ ング実験を行い，BNPDを事後 確率計算アルゴリズムに用いる．
Yes
終了
CCPDを用いる．
No
より高いスクリーニ ング能力が必要か?
CCPDの出力をMCPDの 初期値として十分な反復回 数で事後確率を計算する．
Yes No
図4.1: プーリングデザインと事後確率計算アルゴリズム
補正が有効であるが，会合数が大きくなると偏り補正の効果が見られな くなることがある．これは，会合数 λの値が大きいためタナーグラフに 長さ4 の閉路が増加し，それに伴って長さ6 以上の閉路も増加するため に，より高次の偏り補正項が影響しているからではないかと思われる．し たがって，packing design を用いることができない場合に 2 つのプール の会合数λが大きくなると，BNPD，CCPDの偏り補正には 3次以上の 補正項の影響も考えなければならず，高次の補正項の導出が必要であると 思われる．
本論文では，各クローンの繰り返し数 k が一定の場合のみ扱ったが，
LDPC符号の分野では kが一定でないある種の符号の中に誤り訂正能力 が高い符号が存在することが知られており，グループテストについても繰 り返し数が一定でないプーリングデザインのスクリーニング能力の研究が 必要である．
最後に本論文を通して，偽ポジティブ・偽ネガティブの誤りに対して頑 健なBNPD，CCPD，MCPDなどの確率的な事後確率計算アルゴリズム と高い識別能力を有する組合せ論的なプーリングデザインを併用してグ ループテストのアルゴリズムを構築することが重要であることが言えるで あろう．
付録 A
定理 1 の証明
CcG(ℓ) = ∪
G′∈G(ℓ)cG
G′，CGc(ℓ) = ∪
G′∈GGc(ℓ)
G′ とし，帰納法で証明する．ま ず，t= 0 のとき
Q¯(0)cG(x) =P(Xc =x)
が成り立つ．次に t≥1 のとき，式(2.2)のR¯(t)Gc(x)はQ¯(t−1)cG (x)を用い て次のように得られる．
KR¯(t)Gc(xc)
=K ∑
xc′∈{0,1} forc′∈G\{c}
P (
SG=sGZG= ∨
c′∈G
xc′) ∏
c′∈G\{c}
Q¯(tc′−G1)(xc′)
= ∑
xc′∈{0,1} forc′∈G\{c}
P (
SG=sGZG= ∨
c′∈G
xc′
)
× ∏
c′∈G\{c}
P (
Xc′ =xc′, ∩
G′∈Gc′G(2t−2)
{SG′ =sG′})
= ∑
xc′∈{0,1} forc′∈CcG(2t−2)\{c}
P (
SG=sGZG= ∨
c′∈G
xc′
) P
( ∩
c′′∈Cc′(2tG−2)\{c}
{Xc′′ =xc′′})
× ∏
c′∈G\{c}
P
( ∩
G′∈Gc′G(2t−2)
{SG′ =sG′} ∩
c′′∈Cc′G(2t−2)
{Xc′′ =xc′′})
= ∑
xc′∈{0,1} forc′∈CcG(2t−2)\{c}
P (
SG=sGZG= ∨
c′∈G
xc′
) P
( ∩
c′′∈Cc′(2t−2)
G \{c}
{Xc′′ =xc′′})
× ∏
c′∈G\{c}
P
( ∩
G′∈Gc′G(2t−2)
{SG′ =sG′} ∩
G′∈Gc′G(2t−2)
{ZG′ = ∨
c′′∈G′
xc′′})
= ∑
xc′∈{0,1} forc′∈CcG(2t−2)\{c}
P
( ∩
c′′∈Cc′G(2t−2)\{c}
{Xc′′ =xc′′})
×P
( ∩
G′∈GGc′(2t−1)
{SG′ =sG′} ∩
G′∈G(2tGc′−1)
{ZG′ = ∨
c′′∈G′
xc′′})
= ∑
xc′∈{0,1} forc′∈CcG(2t−2)\{c}
P
( ∩
c′′∈Cc′G(2t−2)\{c}
{Xc′′ =xc′′})
×P
( ∩
G′∈GGc′(2t−1)
{SG′ =sG′} ∩
c′′∈CGc′(2t−1)
{Xc′′=xc′′})
= ∑
xc′∈{0,1} forc′∈CcG(2t−2)\{c}
P
( ∩
G′∈G(2tGc′−1)
{SG′ =sG′}, ∩
c′′∈Cc′G(2t−2)\{c}
{Xc′′ =xc′′} Xc =xc
)
=P
( ∩
G′∈G(2tGc′−1)
{SG′ =sG′}Xc =xc
) .
また，式 (2.3)は上記の結果を用いて次のように得られる．
Q(t)cG(xc)
=P(Xc=xc) ∏
G′∈(c)\{G}
R(t)G′c(Xc)
=P(Xc=x) ∏
G′∈(c)\{G}
P
( ∩
G′′∈GG′c(2t−1)
{SG′′ =sG′′}Xc =xc
)
=P(Xc=xc) ∏
G′∈(c)\{G}
∑
xc′∈{0,1} forc′∈CG′c(2t−1)\{c}
P
( ∩
c′′∈C(2t−1)G′c′ \{c}
{Xc′′ =xc′′})
×P
( ∩
G′′∈G(2tG′c−1)
{SG′′=sG′′} ∩
c′′∈CG′c′(2t−1)
{Xc′′=xc′′})
=P(Xc=xc) ∏
G′∈(c)\{G}
∑
xc′∈{0,1} forc′∈CG′c(2t−1)\{c}
P
( ∩
c′′∈C(2t−1)G′c′ \{c}
{Xc′′ =xc′′})
×P
( ∩
G′′∈G(2tG′c−1)
{SG′′=sG′′} ∩
G′′∈GG′c(2t−1)
{ZG′′= ∨
c′′∈G′′
xc′′})
=P(Xc=xc) ∑
xc′∈{0,1} forc′∈GcG(2t)\{c}
P
( ∩
c′∈GcG(2t)\{c}
{Xc′ =xc′})
×P( ∩
G′∈GcG(2t)
{SG′ =sG′} ∩
G′∈GcG(2t)
{ZG′ = ∨
c′∈G′
xc′
})
=P(Xc=xc) ∑
xc′∈{0,1} forc′∈GcG(2t)\{c}
P
( ∩
c′∈GcG(2t)\{c}
{Xc′ =xc′})
×P( ∩
G′∈GcG(2t)
{SG′ =sG′} ∩
c′∈CcG(2t)
{Xc′ =xc′})
=P(Xc=xc) ∑
xc′∈{0,1} forc′∈G(2t)cG\{c}
P( ∩
G′∈GcG(2t)
{SG′ =sG′}, ∩
c′∈C(2t)cG
{Xc′ =xc′} Xc=xc
)
=P(Xc=xc)P( ∩
G′∈GcG(2t)
{SG′ =sG′}Xc =xc )
=P( ∩
G′∈GcG(2t)
{SG′ =sG′}, Xc =xc )
.
参考文献
[1] C.I. Amos, M.L. Frazier, and W. Wang, “DNA pooling in mutation detection with reference to sequence analysis,”Am. J. Hum. Genet.
vol. 66, pp. 1689-1692, 2000.
[2] N. Arnheim, C. Strange, and H. Erlich, “Use of pooled DNA sam-ples to detect linkage disequilibrium of polymorphic restriction frag-ments and human disease: studies of HLA class II loci,”Proc. Natl Acad. Sci. USA, vol.82, pp. 6970-6974, 1985.
[3] L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,”IRE Trans. Inform.
Theory, vol. IT-20(2), pp. 284-287, 1974.
[4] D.J. Balding, and D.C. Torney, “Optimal pooling designs with error detection,”J. Combin. Theory A, vol. 74, no. 1, pp. 131-140, 1996.
[5] E. Barillot, B. Lacroix, and D. Cohen, “Theoretical analysis of li-brary screening using anN-dimensional pooling strategy,” Nucleic Acids Res., vol. 19, no. 22, pp. 6241-6247, 1991.
[6] T. Berger, J.W. Mandell, and P. Subrahmanya, “Maximally efficient two-stage screening,”Biometrics, vol. 56, no. 3, pp. 833-840, 2000.
[7] A. De Bonis, L. Gasieniec, and U. Vaccaro, “Optimal two-stage algorithms for group testing problems,”SIAM J. Comput., vol. 34, pp. 1253-1270, 2005.
[8] A. De Bonis, and U. Vaccaro, “Improved algorithms for group test-ing with inhibitors,”Inform. Proc. Lett., vol. 67, pp. 57-64, 1998.
[9] R. Brookmeyer, “Analysis of multistage pooling studies of biological specimens for estimating disease incidence and prevalence,” Biomet-rics, vol. 55, pp. 608-612, 1999.
[10] W.J. Bruno, E. Knill, D.J. Balding, D.C. Bruce, N.A. Doggett, W.W. Sawhill, R.L. Stallings, C.C. Whittaker, and D.C. Torney,
“Efficient pooling designs for library screening,”Genomics, vol. 26, no. 1, pp. 21-30, 1995.
[11] K.A. Bush, W.T. Federer, H. Pesotan, and D. Raghavarao, “New combinatorial designs and their applications to group testing,” J.
Stat. Plann. Infer., vol. 10, pp. 335-343, 1984.
[12] R. Carmi, T. Rokhlina, A.E. Kwitek-Black, K. Elbedour, D. Nishimura, E.M. Stone, and V.C. Sheffield, “Use of a DNA pooling strategy to identify a human obesity syndrome locus on chromosome 15,” Hum. Mol. Genet., vol. 4, pp. 9-13 (1995).
[13] X.M. Chang, F.K. Hwang, and J.F. Weng, “Group testing with two and three defectives,” Ann. N. Y. Acad. Sci., vol. 576, pp. 86-96, 1989.
[14] C.J. Colbourn, and J.H. Dinitz, Handbook of Combinatorial De-signs, Second Edition, Chapman & Hall / CRC, 2006.
[15] R. Dorfman, “The detection of defective members of large popula-tions,” Ann. Math. Statist., vol. 14, pp. 436-440, 1943.
[16] D.Z. Du, and F.K. Hwang, Combinatorial Group Testing and Its Applications, World Scientific Pub. Co, 2000.
[17] D.Z. Du, and F.K. Hwang, “Competitive group testing,”Disc. Appl.
Math., vol. 45, pp. 221-232, 1993.
[18] D.Z. Du, and F.K. Hwang,Pooling Design and Nonadaptive Group Testing: Important Tools for DNA Sequencing, World Scientific Pub. Co, 2006.