2011-06-08

ジグソーパズルの解き方

パズル DNA鑑定

捜し物記事(こちら)の続き
また、この捜し物はN人の行方不明者、M人の身元不明者の特定問題(こちら)の続きでもある
アルゴリズムを考える前に、問題を整理しよう
全人類の歴史全体を考える
すべての個人はAncestral Recombination Graph(ARG)のノードとなっている
このARGをジグソーパズルに見立てよう
ARGのノードがパズルのピース
ピースの周囲の凸凹は、ジェノタイプがうまくメンデルの法則に合うかどうかを表している
ただし、このジグソーパズルは、市販のそれのように、「こんなにぴったりはまるんだから、このピースはこのピースと隣り合わせだ」と言えるほど特異度が高くない(そのピースとは別のピースもはまるかもしれない)
また、このジグソーパズルのピースは、結構、いい加減な作りで、ピースの周辺がちびて欠けていたり、ボンドが張り付いて出っ張っていたりする部分がある(これは、突然変異があるため「血縁関係」的にははまるけれども、「メンデルの法則」だけを頼りにして、はめ具合を決めてはいけないことに相当する
また、ピースの中には、『変幻自在ピース』と呼ばれるピースがある。『変幻自在ピース』はその形を「ある範囲で」変えることができ、「変化して取る姿」は確率的に決まる。これは、ジェノタイプが観測できていない個人に対応するピースで、「範囲」はそのピースの帰属集団が取りうるジェノタイプの種類に相当し、「確率的」に決まるのは、帰属集団にはジェノタイプの存在確率情報があるからである
突然変異の可能性を認めることで、「すべてのピース」はすべての場所にはまりうる、ただし、はまりの良さ悪さは大いに違う、というパズルとしては厄介な問題を生じる
さらにやっかいなことに、このパズルでは、非常に多くのピースが「なくなっている」。過去の人のピースはもちろんないし、「現在時」の人のピースもすべてをそろえてパズルを解いているわけではない
「行方不明者」を探している血縁関係者は、この広大なパズルの中で、ごく少数のピースに相当し、それらは隙間を空けて、並べられている
この隙間にうまくはまるジェノタイプを持った「身元不明者ピース」がないかどうかがこのパズルである
隙間は１人分のこともあれば、複数人分のこともある。複数人分の場合に、個々のピースを独立して当てはめることもあるかもしれないが、複数ピースを合わせて、うまく隙間にあうことを確認する必要もある
DNAの情報だけでこのパズルを解こうとするのが、「白地ジグソーパズル」であり、性別・年齢・その他の情報を使うのは、「絵柄ありのジグソーパズル」に相当する
「どれくらいうまくはまっていれば」「はまり」であるかについて、コンセンサスが必要だと、プレーヤたちは思っている
すべての身元不明ピースの落ち着け位置を決めずに、一部だけで、ピースがはまったように見えたら「一部完成」とするかどうかもコンセンサスが必要だ、とプレーヤたちは思っている
「うまいはまり具合」「(一部)完成」についてのコンセンサスは問題だが、
そもそも、どういう手順でこのパズルを解くことにするのかをアルゴリズムにしたい、という点が問題だ
掲載図はこちらのジグソーパズル作成ソフトで作成