(57)【特許請求の範囲】
【請求項１】
集計表の各度数を入力として、その入力に対応するフィッシャー正確検定の結果が有意であるか否かを判断するための条件が記憶されている条件記憶部と、
上記条件記憶部から読み込んだ条件に集計表の度数を入力することにより、その集計表の度数に対応するフィッシャー正確検定の結果を得る計算部と、
を含み、
上記計算部は、上記集計表の度数を秘密計算により秘匿化した状態で、その集計表の度数に対応するフィッシャー正確検定の結果を得るための計算を行う、
フィッシャー正確検定計算装置。
【請求項２】
請求項１のフィッシャー正確検定計算装置において、
上記条件は、根ノード及び各内部ノードに条件式が割り当てられており、各葉ノードにフィッシャー正確検定の結果が割り当てられている決定木の形で与えられ、
上記計算部は、根ノード及び各内部ノードに割り当てられた条件式に上記集計表の度数を入力することにより得られた値に応じて定まる葉ノードに割り当てられているフィッシャー正確検定の結果を出力する、
フィッシャー正確検定計算装置。
【請求項３】
請求項２のフィッシャー正確検定計算装置において、
有意である旨のフィッシャー正確検定の結果が割り当てられている葉ノードには、その葉ノードから上記根ノードに至るパス上の根ノード及び内部ノードに割り当てられている条件式に集計表の度数を入力することにより得られる値が所定の値となるように根ノード及び各内部ノードに条件式が割り当てられており、
上記計算部は、葉ノードから上記根ノードに至るパス上の根ノード及び内部ノードに割り当てられている条件式に上記集計表の度数を入力することにより得られる値が所定の値となる葉ノードがあるか上記集計表の度数を秘匿しつつ判断し、そのような葉ノードがある場合には、上記集計表についてのフィッシャー正確検定の結果は有意であるとの結果を得る、
フィッシャー正確検定計算装置。
【請求項４】
計算部が、集計表の各度数を入力として、その入力に対応するフィッシャー正確検定の結果が有意であるか否かを判断するための条件が記憶されている条件記憶部から読み込んだ条件に集計表の度数を入力することにより、その集計表の度数に対応するフィッシャー正確検定の結果を得る計算ステップと、
を含み、
上記計算部は、上記集計表の度数を秘密計算により秘匿化した状態で、その集計表の度数に対応するフィッシャー正確検定の結果を得るための計算を行う、
フィッシャー正確検定計算方法。
【請求項５】
請求項１から３の何れかのフィッシャー正確検定計算装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、フィッシャー正確検定（Fisher’s exact test）を効率良く計算する技術に関する。
【背景技術】
【０００２】
統計学的検定法の一つとして、フィッシャー正確検定が広く知られている。フィッシャー正確検定の利用例として、ゲノムワイド関連解析（GWAS: Genome-Wide Association Study）がある（例えば、非特許文献１参照。）。以下、フィッシャー正確検定について簡単に説明する。【０００３】
【表１】
0006682105.tif 000002
【０００４】
この表は、n人の被験者を形質 (X又はY)と特定のアレル(A又はG)で分類して数え上げした2x2の集計表の例である。a,b,c,dは度数（非負整数）を表す。フィッシャー正確検定は、非負整数iについて、【０００５】
【数１】
0006682105.tif 000003
としたとき、
【数２】
0006682105.tif 000004
と所定の値の閾値Tとの大小関係で、形質と特定のアレルの間に統計学的に有意な関連があるかどうか判定するものである。ゲノムワイド関連分析では、各々の一塩基多型（SNP:Single Nucleotide Polymorphism）毎に上記のような集計表を作成し、各集計表についてフィッシャー正確検定を行う場合がある。ゲノムワイド関連解析では、数百万数千万という膨大な数のSNPが対象となる。したがって、ゲノムワイド関連分析では大量にフィッシャー正確検定を行う場面があり得る。【０００６】
一方、ゲノム情報の機微性や機密性から、ゲノム情報を暗号技術によって秘匿しつつゲノムワイド関連解析を行う先行研究がある（例えば、非特許文献２参照。）。非特許文献２ではゲノム情報を秘匿しつつカイ２乗検定を行う方法が提案されている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Konrad Karczewski, “How to do a GWAS”, GENE 210: Genomics and Personalized Medicine, 2015.
【非特許文献２】Yihua Zhang, Marina Blanton, and Ghada Almashaqbeh, “Secure distributed genome analysis for GWAS and sequence comparison computation”, BMC Med. Inform. Decis. Mak., 2015.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
フィッシャー正確検定では、min(a+b,a+c)-max(0,a-d)+1種類のpiの計算が必要となり、特にゲノムワイド関連解析では大量の集計表に対してそれぞれフィッシャー正確検定を行う場合があるため、計算機環境や集計表の度数によっては膨大な処理時間を要する可能性がある。【０００９】
この発明の目的は、従来よりも効率良くフィッシャー正確検定の計算を行うフィッシャー正確検定計算装置、方法及びプログラムを提供することである。
【課題を解決するための手段】
【００１０】
この発明の一態様によるフィッシャー正確検定計算装置は、集計表の各度数を入力として、その入力に対応するフィッシャー正確検定の結果が有意であるか否かを判断するための条件が記憶されている条件記憶部と、条件記憶部から読み込んだ条件に集計表の度数を入力することにより、その集計表の度数に対応するフィッシャー正確検定の結果を得る計算部と、を備えており、計算部は、集計表の度数を秘密計算により秘匿化した状態で、その集計表の度数に対応するフィッシャー正確検定の結果を得るための計算を行う。
【発明の効果】
【００１１】
事前計算を行うことで、本計算では従来よりも効率良くフィッシャー正確検定の計算を行うことができる。
【図面の簡単な説明】
【００１２】
【図１】フィッシャー正確検定計算装置の例を説明するためのブロック図。
【図２】フィッシャー正確検定計算方法の例を説明するための流れ図。
【図３】決定木の例を示す図。
【発明を実施するための形態】
【００１３】
以下、図面を参照して、この発明の一実施形態について説明する。
【００１４】
フィッシャー正確検定計算装置は、図１に示すように、条件記憶部１と計算部２を例えば備えている。フィッシャー正確検定計算方法は、フィッシャー正確検定計算装置の計算部２が図２及び以下に説明するステップＳ２の処理を行うことにより実現される。
【００１５】
集計表の度数の総和n及び有意水準である閾値Tの値は事前に決まっているものとする。
【００１６】
＜条件記憶部１＞
条件記憶部１には、集計表の各度数を入力として、その入力に対応するフィッシャー正確検定の結果が有意であるか否かを判断するための条件が記憶されている。
【００１７】
例えば、n=a'+b'+c'+d'となる全ての非負整数の組(a',b',c',d')についてフィッシャー正確検定の結果を事前に求めておき、(a',b',c',d')とそのフィッシャー正確検定の結果を対応付けて条件記憶部１に記憶させておく。フィッシャー正確検定計算装置は、この事前計算を行うため事前計算部３を備えていてもよい。
【００１８】
条件記憶部１に記憶されている条件は、根ノード及び各内部ノードに条件式が割り当てられており、各葉ノードにフィッシャー正確検定の結果が割り当てられている決定木であってもよい。n=50であり、所定の閾値T=10-8である場合の決定木の例を図３に示す。このような決定木は、既存の機械学習方法を用いることにより作成すればよい。
例えば、n=a'+b'+c'+d'となる全ての非負整数の組(a',b',c',d')と、フィッシャー正確検定の結果を求めるための式とに基づいて、参考文献１から３に記載された方法により、このような決定木を作成することができる。
〔参考文献１〕Leo Breiman, Jerome H. Friedman, Richard A. Olshen, Charles J. Stone, " Classification and Regression Trees (Wadsworth Statistics/Probability)", Wadsworth & Brooks/Cole Advanced Books & Software,
〔参考文献２〕
John R. Quinlan, "Induction of decision trees", Machine learning, 1986, P.81-106.
〔参考文献３〕Trevor Hastie, Robert Tibshirani, Jerome Friedman, "The Elements of Statistical Learning Data Mining, Inference, and Prediction, Second Edition", Springer Series in Statistics.
【００１９】
図３において、根ノード及び各内部ノードに割り当てられている条件式は、V1=a,V3=c,V9=ad,V11=bc,V12=bd,V14=cd,V21=abc,V25=ad2,V30=bcdと各ノードに対応する閾値との大小関係を表す式である。図３において、14e+3は14*103を意味し、13e+3は13*103を意味する。図３の決定木では、あるノードに対応する条件式にフィッシャー正確検定の対象となる集計表の度数(a,b,c,d)を入力した場合に、その条件式が成立する場合にはそのノードの左の子ノードに遷移し、その条件式が成立しない場合にはそのノードの右の子ノードに遷移するものとする。図３の決定木において、葉ノードの「FALSE」はp>Tでありフィッシャー正確検定の結果が有意でないことを意味し、葉ノードの「TRUE」はp≦Tでありフィッシャー正確検定の結果が有意であることを意味する。
【００２０】
＜計算部２＞
計算部２は、条件記憶部１から読み込んだ条件に、フィッシャー正確検定の対象となる集計表の度数を入力することにより、その集計表の度数に対応するフィッシャー正確検定の結果を得る（ステップＳ２）。
【００２１】
例えば、条件記憶部１に(a',b',c',d')とそのフィッシャー正確検定の結果を対応付けて記憶されている場合には、計算部２は、条件記憶部１を参照して、入力された集計表の度数(a,b,c,d)に対応するフィッシャー正確検定の結果を得る。より詳細には、計算部２は、条件記憶部１を参照して、入力された集計表の度数(a,b,c,d)と同じ度数(a',b',c',d')に対応するフィッシャー正確検定の結果を得て、入力された集計表の度数(a,b,c,d)に対応するフィッシャー正確検定の結果とする。又はフィッシャー正確検定の結果が有意である集計表の度数のみ条件記憶部1に記憶し、入力された集計表の度数(a,b,c,d)と同じ度数(a',b',c',d')が条件記憶部1にあれば、フィッシャー正確検定の結果が有意であると判定しても良い。同様に、フィッシャー正確検定の結果が有意でない集計表の度数を記憶しても良い。
【００２２】
また、条件記憶部１に、根ノード及び各内部ノードに条件式が割り当てられており、各葉ノードにフィッシャー正確検定の結果が割り当てられている決定木が記憶されている場合には、計算部２は、根ノード及び各内部ノードに割り当てられた条件式に上記集計表の度数を入力することにより得られた値に応じて定まる葉ノードに割り当てられているフィッシャー正確検定の結果を出力してもよい。
【００２３】
例えば、条件記憶部１に条件として図３の決定木のデータが記憶されており、この図３の決定木を用いて、入力された集計表の度数(a,b,c,d)に対応するフィッシャー正確検定の結果を得るためには、次のような処理を行えばよい。
【００２４】
計算部２は、まず最上位の根ノードの「V25>=14e+3」の条件式、すなわちad2≧14000を満たすかどうか計算し、満たす場合にはであれば根ノードの左の子ノードの条件式に進み、満たさない場合には根ノードの右の子ノードの条件式に進む。以降、同様の処理を葉ノードに到達するまで繰り返し行う。そして、到達した葉ノードに対応するフィッシャー正確検定の結果を出力する。
【００２５】
図3の決定木の例では、高々7回の大小比較によってフィッシャー正確検定の結果が得られることが分かる。一方、
【００２６】
【数３】
0006682105.tif 000005
を計算する場合、最悪でおよそn/2=25個のpiを求める必要がある。piはさらに9個の階乗値の乗除からなるが、これは以下のように対数を取り、事前計算を行うことで効率良く求めることができる。
【００２７】
【数４】
0006682105.tif 000006
より、
【数５】
0006682105.tif 000007
【００２８】
であるから、k=0,1,2,…,nについてΣj=1k log jを事前計算しておき、log paを事前計算値を用いて求めれば、事前計算値の加減算のみで計算できる。そして、log piからpiを求める。なお、Σj=10 log j=0とする。
【００２９】
上記の演算によれば、piを求めるために9回の照合処理、8回の加減算、およびlog piからpiを求める必要がある。したがって少なくとも25×9=225回の照合処理が必要となり、これは高々7回の大小比較と比べて225/7≒32.1倍の計算回数となる。さらに照合処理は大小比較と同等以上の処理時間とみなせば、決定木を用いた方が処理時間も短く済むことが期待できる。
【００３０】
なお、計算部２は、入力されたフィッシャー正確検定の対象となる集計表の度数(a,b,c,d)を秘密計算により秘匿化した状態で、その集計表の度数(a,b,c,d)に対応するフィッシャー正確検定の結果を得るための計算を行ってもよい。
【００３１】
このような計算は、入出力を秘匿しつつ大小比較ができる暗号技術を組み合わせて実現することができる。以下、入出力を秘匿しつつ大小比較する（以下、入出力秘匿大小比較と略する。）について説明する。大小比較を行う二つの数値x,yを入力とし、x,yの少なくとも一方は暗号化され実際の数値が分からないものとする。いまxのみが暗号化されているものとし、これをE(x)と表記する。そして出力となる大小比較結果を
【００３２】
【数６】
0006682105.tif 000008
【００３３】
とする。すなわち、入出力秘匿大小比較とは、E(x),yを入力とし、E(x)を復号することなく、大小結果の暗号文E(z)を求めることを意味する。もし、zが最終的に求めたい結果であれば、E(z)を適宜復号する。このような入出力秘匿大小比較として、例えば参考文献４及び５の方法を挙げることができる。
【００３４】
〔参考文献４〕Ivan Damgard, Matthias Fitzi, Eike Kiltz, Jesper B. Nielsen, Tomas Toft, "Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation", In Proc. 3rd Theory of Cryptography Conference, TCC 2006, volume 3876 of Lecture Notes in Computer Science, pages 285-304, Berlin, 2006, Springer-Verlag
〔参考文献５〕Takashi Nishide, Kazuo Ohta, "Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol", Public Key Cryptography - PKC 2007, 10th International Conference on Practice and Theory in Public-Key Cryptography, 2007, P.343-360
【００３５】
以下、入出力秘匿大小比較を用いて、図３の決定木から、フィッシャー正確検定の結果を求める方法について説明する。
【００３６】
入力を集計表の度数(a,b,c,d)の暗号文(E(a),E(b),E(c),E(d))と、図３の決定木のデータとする。入出力秘匿大小比較を用いない場合には、上記のように、まず最上位の根ノードの「V25>=14e+3」の条件式、すなわちad2≧14000を満たすかどうか計算し、満たす場合には根ノードの左の子ノードの条件式に進み、満たさない場合には根ノードの右の子ノードの条件式に進む。以降、同様の処理を葉ノードに到達するまで繰り返し行う。そして、到達した葉ノードに対応するフィッシャー正確検定の結果を出力する。
【００３７】
これを入出力秘匿大小比較を用いて実現する場合、先ず条件式ad2≧14000について、入力E(a),E(d)からそれらを復号することなくE(ad2)を計算する。当該方法は例えば参考文献４，５で説明されているため、具体的な方法は省略する。次に入出力秘匿大小比較を用いて、E(ad2)及び条件式の14000から、E([ad2≧14000])を計算する。
【００３８】
ここで、[ad2≧14000]は、ad2≧14000であれば１、そうでなければ０とする。次に左下の条件式「V30<94」または右下の条件式「V9>=485」に進むが、[ad2≧14000]の値が秘匿されているため、どちらに進むべきか分からない。そこで、根ノードから、TRUEが割り当てられている葉ノードに到達する全てのパスのそれぞれについてパス上のノードの条件式を満たすかを計算し、TRUEが割り当てられている葉ノードに到達したかどうかを最終出力、すなわちフィッシャー正確検定結果として出力する。
【００３９】
例えば最も左にあるTRUEが割り当てられている葉ノードに到達するパスは，条件式「V25≧14e+3」、「V30<94」、「V12<38」、「V14<134」、「V12<36」、「V3<1.5」について、はじめの４つはYes、残り２つはNoとなればよい。すなわち、はじめの４つはYes、残り２つはNoとなれば1の暗号文を返し、そうでなければ０の暗号文を返すように条件を設定しておく。例えば、簡単のため全てYesとなれば１の暗号文を返すよう、条件式「V12<36」、「V3<1.5」をそれぞれ「V12≧36」、「V3≧1.5」に置き換える。このように置き換えた決定木のデータを条件として条件記憶部１に予め記憶しておく。
【００４０】
いま、条件式「V25≧14e+3」、「V30<94」、「V12<38」、「V14<134」、「V12≧36」、「V3≧1.5」について、入出力秘匿大小比較を用いて結果の暗号文（それぞれE(z1),E(z2),E(z3),E(z4),E(z5),E(z6)とする）を求める。全てYesとなるときに限り１の暗号文を返すために、E(z1),E(z2),E(z3),E(z4),E(z5),E(z6)からE(z1z2z3z4z5z6)を求める。すなわち、計算部２は暗号文の中身を秘匿したまま乗算する。この方法も例えば参考文献４，５で説明されているため、具体的な方法は省略する。以下、同様の処理をTRUEが割り当てられている葉ノードに到達する全てのパスに対して行い、得られた暗号文（E(z1z2z3z4z5z6)をはじめTRUEに到達する16種類の暗号文）すべてに対して、さらに暗号文の中身を秘匿したまま乗算する。
【００４１】
当該結果は、フィッシャー正確検定結果がTRUEであれば１の暗号文であり、そうでなければ０の暗号文となるため、当該結果を復号し、フィッシャー正確検定結果を得ることができる。すなわち、入力された集計表の度数(a,b,c,d)の暗号文(E(a),E(b),E(c),E(d))を用いて、このような計算を行い、E(z1z2z3z4z5z6)の復号結果が１であるパスが存在すれば、その入力された集計表についてのフィッシャー正確検定の結果は有意であると判断することができる。
【００４２】
さらには、どの葉ノードに到達したかも秘匿するため、TRUEが割り当てられている葉ノードに到達する全てのパスに対して得られた暗号文E(z1jz2jz3jz4jz5jz6j) (j=1,2,…)について、例えば平文の論理和 ∪z1jz2jz3jz4jz5jz6jを秘密計算によって求める。すなわち暗号文E(z1jz2jz3jz4jz5jz6j) (j=1,2,…)について一つでも復号結果が1であれば、∪z1jz2jz3jz4jz5jz6j=1となることを利用する。論理和の秘密計算は例えば参考文献1に記載の方法で求めればよい。
【００４３】
すなわち、以下のように結果を得てもよい。フィッシャー正確検定で、有意か否かの結果が葉ノードに割り当てられている。上記根ノードから、葉ノードにいたるパスの各ノードには、条件式が割り当てられている。根ノードから始め、集計表の度数を各ノードの条件式に入力し、分岐することで、一つの葉ノードまでたどる事ができる。そのことにより、葉ノードに割り当てられている、フィッシャーの正確検定で有意か否かの結果を得ることができる。計算部2は、集計表の度数を秘匿しつつ、各ノードの条件式を評価し、一つの葉ノードに至るパスを得ることができ、集計表の度数を秘匿しながらフィッシャーの正確検定の結果を得る。
【００４４】
このようにして、事前に集計表の度数パターンとフィッシャー正確検定の結果(例えば、TRUE又はFALSEの二値とする)の対応を求め、フィッシャー正確検定の結果がTRUE（又はFALSE）となる条件を作成しておくことで、本計算（事前の計算部分を除いた計算）では、piの計算をすることなく、集計表の度数を条件に入力して計算するだけでフィッシャー正確検定の結果が得られるようになる。piの計算をする必要がないため、効率良くフィッシャー正確検定の計算を行うことができる。
【００４５】
また、事前計算結果を公開等することで、これまでフィッシャー正確検定の実行が困難な計算能力の高くない計算機でも、事前計算結果を参照することで、フィッシャー正確検定を実行できるようになる可能性がある。具体的には、計算リソースの使用量の削減や処理時間の削減の効果が期待できる。
【００４６】
さらに、上記の秘匿化により、例えばゲノム情報やそれに付随する各種データを秘匿しつつフィッシャー正確検定を実行することができる。これは、例えば、複数の研究機関が所持するゲノムデータを秘匿したまま相互に開示することなく、統合されたデータのフィッシャー正確検定の実行結果を得ることができ、極めてセキュリティレベルの高いゲノム解析の実行環境の提供、ひいては医療の更なる発展へとつながることが期待できる。
【００４７】
［プログラム及び記録媒体］
フィッシャー正確検定計算装置及び方法において説明した処理は、記載の順にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４８】
また、フィッシャー正確検定計算装置における各処理をコンピュータによって実現する場合、フィッシャー正確検定計算装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各処理がコンピュータ上で実現される。
【００４９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５０】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００５１】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【産業上の利用可能性】
【００５２】
本発明のフィッシャー正確検定計算装置及び方法は、フィッシャー正確検定を利用した解析、例えば、ゲノムワイド関連解析、ゲノム分析、臨床研究、社会調査、学術研究、実験結果の分析、マーケティング調査、統計計算、医療情報分析、顧客情報分析、売り上げ分析において、集計表の情報を秘匿したまま秘密計算によりフィッシャー正確検定を行うことに適用することが可能である。ゲノムワイド関連解析の場合、例えば、n人の被験者を、特定の形質を有するかどうかと、特定のアレル(例えばA又はG)を有するかどうかで分類して数え上げした2x2の集計表の度数が、フィッシャー正確検定計算装置及び方法の入力となる。
【図１】
0006682105.tif 000009
【図２】
0006682105.tif 000010
【図３】
0006682105.tif 000011