Missouri Western & Davidson Univ.
"Solving the Pancake Problem with a Bacterial Computer"
Goal
「パンケーキ問題」という数学問題を大腸菌に解いてもらう。
参考：Pancake sorting - wikipedia(英語)
焦げパンケーキ問題(フライ返し１枚)とは
焦げ面を下にして、パンケーキを下から大きい順に並べ替えるには、最小で何手必要か？
焦げパンケーキ問題2 (フライ返し2枚）とは
フライ返しが２つ使える場合、焦げ面を下にしてパンケーキを下から大きい順に並べ替えるには、最小で何手？
デザイン
問題2(フライ返し2枚)を“大腸菌に解かせる”ということ
パンケーキを遺伝子に置き換えて考える。
１：パンケーキ遺伝子をランダムにひっくり返す（返し方は次のHinHixシステム参照）
２：たまたま「完成品」ができたら、蛍光等のシグナルが出て教えてくれる
３：完成品が出来た瞬間までの時間を計る。（パンケーキのFlipはランダムに、しかしある頻度でおこるので 、この時間から初期状態から完成品までの最短の「手数」が推測できる ）
フライ返し：Hin-Hix Recombination (Salmonella 遺伝子組換え系)
SalmonellaはHin 呼ばれるリコンビナーゼ（遺伝子の組換えをする酵素）の行う遺伝子の反転によって、鞭毛タンパク質の発現を制御している。hixLとhixRという配列で囲まれている部分が、Hinリコンビナーゼによって反転する。これをフライ返しに応用する。
実験デザイン：パンケーキ２枚の問題を大腸菌に解かせる
1.Construct 〜パンケーキの積み重ね方
パンケーキ1… pBAD プロモーター
パンケーキ2…RBS-Tet
...とする。マイナスがついたものは左向きである。
また、プロモーターの向きの区別をする為に、5’側にRBS-RFP reverse を入れる。
例：RFP無しの場合(1,2)と(-2,-1)は共にTet耐性を示し、区別が出来ない。しかしRFPがあると(1,2)のみが赤色蛋白質を発現するため見分けることが出来る。（図６参照）
2.パンケーキ完成品
パンケーキなら「大きい順に並べたもの」が完成品だが、今回の遺伝子パンケーキの場合は「Tetプレート上で成育しコロニーを形成するもの： (1,2) & (-2,-1)」を完成品とする。
3.出発construct
出発constructの選び方
パンケーキ２枚では８つのconstructが考えられる。このうちどれを解かせればいいのだろうか。
下図はシュミレーション結果である。それぞれの初期状態（図５の８通り）に対し２０回のランダムなflipを起こし、それぞれのflip回数において完成品に辿り着いた大腸菌の割合をプロットしたものである。
すると８つのconstructは、挙動が似ているものどうし３つのグループ（グラフ青、緑、紫）に分けられることがわかる。このグループの中からそれぞれ１つを選び、大腸菌に解かせることにする。
4.問題を解く
1) 出発constructを入れた大腸菌内でHin(フライ返し)を発現させる。パンケーキ遺伝子はランダムにひっくり返り続ける。
2) 求める完成品(図６)のコロニーが得られるまでの時間を計る。
3) 今得られた時間をFlipの起こる時間で割り、出発constructから完成品までの最短の手数を推測する。
→ 解答（最短の手数）が求められる！
実験
タイムアップのため良い結果は出せなかったようです。
その他詳しくはmissouri&davidsonのwikiページをご覧ください。
Reference
Missouri Western State Univ. wikiDavidson Univ. wiki