分子コンピュータの理論と構築 リーダー： 萩谷昌己（計算機科学・東京大学大学院理学系研究科） メンバー： リサーチ・アソシエート： 横森貴（計算機科学・早稲田大学教育学部） 小林聡（計算機科学・電気通信大学電気通信学部） 榊原康文（計算機科学・東京電機大学理工学部） 陶山明（生物物理学・東京大学大学院総合文化研究科） 坂本健作（生物化学・東京大学大学院理学系研究科） 伏見譲 （生物物理学・埼玉大学工学部） 山村雅幸 （システム工学・東京工業大学総合理工学研究科） 有田正規 （ゲノム情報学・経済産業省産業技術総合研究所） リサーチ・アソシエート： 西川明男（計算機科学・東京大学→大阪電気通信大学） John Rose（生物物理学・東京大学） 期間：1996年10月～2001年3月

「分子計算」の目標 生体分子の計算能力の解析 生体分子の計算能力の工学的応用 ⇒ コンピュータに限定されるわけではない。 計算論的な観点から生体分子とその反応を解析する。 生命の神秘の一つの側面 生体分子の計算能力の工学的応用 ⇒ コンピュータに限定されるわけではない。 組み合わせ的最適化 ← 超並列性 バイオテクノロジー (computationally inspired biotechnology) ナノテクノロジー・ナノマシーン ← 微小性 最終的には医薬への応用 ← 細胞による計算 分子による計算のための新しい情報技術 新しい計算パラダイム 新しいシミュレーション技術

関連分野 分子エレクトロニクス 量子計算 ゲノム情報 (genome informatics) 人工生命 人工分子進化 分子素子を用いた電子回路（既存の計算パラダイム） 分子回路の構成技術（ナノテクノロジー）としての分子計算 量子計算 量子重ね合わせによる超並列計算 分子量子計算（量子計算と分子計算の融合） 量子デバイスの構成技術（ナノテクノロジー）としての分子計算 ゲノム情報 (genome informatics) 計算機技術のゲノム解析への応用 ヒトゲノム・プロジェクトの一環 分子計算とは逆の方向 しかし、ゲノム情報は分子計算の重要な応用分野と考えられる。 人工生命 人工分子進化

プロジェクトの主な成果 分子計算の理論 分子計算の解析と設計支援 自律的DNA計算の分子実装 分子メモリ 3SR法に基づく分子進化リアクター シグナル伝達経路のモデリングと細胞計算への応用 DNAナノテクノロジー

研究成果の分類 分子計算のための計算モデル 分子計算の実装技術・設計技術 分子計算の応用 新しい計算モデルの提案 計算可能性・計算量などの解析 分子計算の実装技術・設計技術 新しい実験技術 シミュレーション技術・符号化技術 分子計算の応用 バイオテクノロジー ナノテクノロジー 個々の研究成果はいくつかの分野にまたがっている。

固相法を利用した オートメーション化された DNA計算 陶山 明（東京大学）

Adleman-Liptonパラダイム Adleman (Science 1994) Lipton, et al. 分子による超並列計算 ハミルトン経路問題をDNAを用いて解く。 Lipton, et al. SAT問題をDNAを用いて解く。 分子による超並列計算 主として組み合わせ的最適化 DNAの自己会合によるランダムな生成 解の候補 ＝ DNA分子 生物学実験技術を駆使した解の選択 規模の拡大 ⇒ 収量を増やしエラーを減らす努力 ロボット・化学IC

Adlemanによるハミルトン経路問題の解法 解の候補をすべて含むプールの生成 解の選択と抽出 NP完全問題 3 4 2 1 5 6 O0 O6 PCR PAGE AF-SEP O1 O2 O3 O4 O5 HP HPP CGATAAGCTCGAATTTCGAT GTATATCCGAGCTATTCGAG CTTAAAGCTAGGCTAGGTAC ……………….. O2-3 O3-4 O3

陶山の Dynamic Programming DNA Computer “counting” （Ogihara and Ray） n変数 3-SATに対して O(20.4n)分子 “dynamic programming” （陶山） 生成と選択の繰り返し 部分的解の候補の生成 部分的解の選択 必要な分子数のオーダーは下がらないが、　　　係数は激減する。 固相法 磁気ビーズを用いたアフィニティ・セパレーション 自動化に有利 ⇒ ロボット

基本演算の実装 get (T, +s), get (T, -s) amplify (T, T1, T2, …Tn) annealing immobilization cold wash hot wash get (T, +s) get (T, -s) amplify (T, T1, T2, …Tn) PCR and divide T T1, T2, …Tn append (T, s, e) e annealing and ligation s immobilization cold wash hot wash Taq DNA ligase

計算規模の拡大について 陶山の見積もり しかし、100変数は決して多くはない。 100変数の3-SATに対して 2x10-3 g の DNA Adleman-Lipton では 2x1012 g の DNA ３月末まで: 10変数40節の3-SAT 究極の目標: 100変数400節の3-SAT しかし、100変数は決して多くはない。 電子コンピュータを凌駕するためには、 アルゴリズムと実験技術の両面において、 多くのブレークスルーが必要である。 例えば、ロボット...

Robot for DNA Computing Based on MAGTRATIONTM

Programming in DNA Computer [Instrument] [Reset Counter] 0 [Home Position] 0 [MJ-Open Lid] ･･･ [Get1(0)] [Get2(1)] [Append(2)] [Exit] protocol-level (1-1-4) [MJ-Open Lid] Do 2 _SEND "LID OPEN" Do 10 _SEND "LID?" Wait_msec 500 _CMP_GSTR "OPEN" IF_Goto EQ 0 ;open Wait_msec 1000 Loop ; Time out End ;open script-level Pascal/C-level

DNAコンピューティングによるゲノム解析 (DNAC)への 変換反応 DNAチップによる 処理結果の表示 処理結果の DNA/RNA分子の出力 DNA/RNA分子がもつ ゲノム情報 DNA進符号化された DNA/RNA分子反応による 計算処理 ゲノムDNA、cDNA/mRNAなどの情報をDNAコンピュータで解析する場合、それらの情報はまず最初に分子反応により正規直交化された塩基配列の並びであるDNA進符号に変換される。 DNA進符号で表現された入力情報は、DNAコンピュータのCPUがサポートする命令を並べたプログラムにより処理される。 その結果はDNA進符号のビット列を表示するDNAチップにより出力される。出力結果を逆変換して対応する分子を調製することも可能である。

遺伝子発現解析のための DNAコンピュータプログラム

DNAチップによる遺伝子多型解析 生活習慣病など病気との相関 薬剤効力、副作用との相関 病気の予防、診断 治療での利用

DNAコンピューティングによるSNPs計測 既存の方法と比べて優れている点は以下のとおりである。 並列性： 　マルチプレックスSNPsタイピングを高速・低コストで行うことができる。 時間：DNAチップによる処理まで含めて約3時間 約2分／SNP コスト：サイト数×多型数＝100のタイピングで約3,000円 約30円／SNP 定量性： 　多個体混合サンプルを用いて、各多型の出現頻度を正確に決定する 　ことができる。 演算性： 　多型のパターンの判定、パターンの探索などの情報処理を行うことが 　できる。

株式会社ノバスジーン News オリンパス光学工業株式会社と三井情報開発株式会社が 研究開発型ベンチャー「株式会社ノバスジーン」を設立 生体分子コンピューティング技術を応用した 遺伝子受託解析サービスを開始 生体分子コンピューティング技術の共同研究開発 主に大学等研究機関の研究者との共同研究により、将来の 生体分子コンピューティング技術の研究開発を進めます。

分子計算の理論 分子計算モデル 新計算パラダイムの探究 横森　貴（早稲田大学） 榊原康文（東京電機大学） 小林　聡（電気通信大学）

研究成果（概要） 反応濃度予測アルゴリズム 分子計算を用いたブール式の 学習アルゴリズム 知的ＤＮＡチップの提案 環状スプライシングモデル 自律的会合モデル：ＹＡＣ 演繹型計算モデル 複数試験管モデル 木スプライシング計算モデル 　細胞膜モデル 反応濃度予測アルゴリズム 分子計算を用いたブール式の 学習アルゴリズム　 　　　　知的ＤＮＡチップの提案　　　　　　　　　　　

DNA計算によるブール式の学習 DNA計算の超並列性を利用して，計算量的に困 難な問題であるブール式の学習を効率よく解く 符号化されたブール式を分子生物学の実験手法を用いて試験管内で評価する方法 セルフアセンブリを用いた大域的並列性と局所的並列性の２つの超並列性を利用

ブール式の符号化と試験管内での評価方法 a = (111) ブール式の例: marker empty stopper ＋ marker アニーリング: PCR伸長:

ブール式の学習の遺伝子発現解析への 応用 知的DNAチップの提案: 知的DNAチップの遺伝子発現解析への応用の提案 ３つ手法の組み合わせ： （例からのブール式の帰納的学習） DNAチップ技術 知的DNAチップ実現方法 知的DNAチップの遺伝子発現解析への応用の提案

DNA計算を用いた遺伝子発現解析の 情報処理：知的DNAチップ 直接入力: 遺伝子の発現 DNAコンピュータ 出力: DNAチップ上 での出力 DNA符号化数 (Encode) GGGGGGGG ATATCCCC CCCCTTTT 試験管内での情報処理 in vitro DNA分子の直接入力 超並列性

萩谷昌己（東京大学） 西川明男（大阪電気通信大学） John Rose（東京大学） 有田正規（産業技術総合研究所） 分子計算の解析と設計支援 萩谷昌己（東京大学） 西川明男（大阪電気通信大学） John Rose（東京大学） 有田正規（産業技術総合研究所）

分子計算の解析と設計支援 分子計算のシミュレーション 符号化のための手法とツール 分子計算の計算量の解析 シミュレータ：VNA (Virtual Nucleic Acid) 格子モデルによるヘアピン形成のシミュレーション 符号化のための手法とツール computational incoherency ｍバランス性 種々の制約を定義できる符号生成ツール 分子計算の計算量の解析 SAT Engineの計算量の解析 確率アルゴリズムとしての分子計算

VNA: Virtual DNAのシミュレータ 抽象塩基による効率化 分子 ― 仮想ストランドのハイブリッド abcd || CDEF シミュレーション方法 分子の組み合わせ的な生成 微分方程式の数値解放による濃度計算 組み合わせ爆発の回避 シミュレーション技術としての新規性 濃度を用いて組み合わせ的な生成を制御 融合

Virtual DNA の反応 hybridization denaturation extension ZA, ua ⇒ | 　　 au denaturation extension ZA ZAU | ⇒ ||| au zau restriction digestion

Virtual DNA の反応 (cont.) self-hybridization ligation b a B A (extension) b a B A

SAT Engine の計算量 エラーの確率 計算のオーダー e 1 : ヘアピン形成に失敗した分子数 (false positive) M exp(-t /n 1.5) < e 1 e 2 : 正しい割り当てが生成されない確率 (false negative) M = (3+a) ln(1/e 2) t > (1+a) n ln(1/e 1 )+ln(ln(1/e 2 ))+n 2.5 ln(3+a) 計算のオーダー 時間 --- O(n 2.5) 分子数 --- O((3+a) n ln(1/e 2))

自律的DNA計算の 分子実装 坂本健作（東京大学） 萩谷昌己（東京大学）

自律的分子計算 Adleman-Liptonパラダイム ワンポット反応 ⇒ 自律的計算 連続した自律的な分子反応による計算 解の候補の生成 ＝ 自律的な反応 解の選択 ＝ 外部からの多くの実験操作 ワンポット反応 ⇒ 自律的計算 連続した自律的な分子反応による計算 WinfreeのDNAタイル 坂本のヘアピン・エンジン Whiplash PCR と SAT Engine より「純粋な形」の分子計算の探求と解析 応用: ナノテクノロジー・ナノマシンーン (computationally inspired) biotechnology

ヘアピン・エンジン Whiplash PCR SAT Engine ヘアピン構造の形成による分子計算 ヘアピン --- 典型的な二次構造 DNAオートマトン: DNAによる状態機械の実現 5回の連続的な状態遷移 SAT Engine ヘアピン構造を用いた解の選択 Adleman-Liptonの第二ステップも自律的になった。 6変数10節の3‐SAT

SAT Engine Sakamoto et al., Science, May 19, 2000. 特願平11-165114 DNAのヘアピン構造による解の選択 制限酵素による切断 exclusive PCR 3-SAT 各節からリテラルを一つずつ選んで ssDNA を生成 相補的なリテラル ＝ 相補的な配列 矛盾の検出 ⇒ ヘアピン 6変数10節の3-SAT問題 SAT計算の本質的な部分 ＝ ヘアピン形成 自律的分子計算

(a∨b∨c)∧(￢d∨e∨￢f)∧ … ∧(￢c∨￢b∨a)∧ ... 制限酵素による切断 exclusive PCR b ￢b

ヘアピン構造による選択 制限酵素による切断 リテラルを表す配列中に制限酵素サイトを挿入 Exclusive PCR 実験操作の数は変数や節の数に依存しない。

分子メモリ 山村雅幸（東京工業大学） Tom Head (Binghamton)

分子メモリ 固体メモリ 分子メモリ （アクエアス・メモリ）

アクエアス・アルゴリズム 特徴 同一分子から出発 水の役割は本質的 最後に1の数を勘定 Write once Initialize 汎用 １１１１１ ０１１１１ １１０１１ １１１１０ Initialize Pour(3) SetToZero(1st) SetToZero(3rd) SetToZero(5th) Unite Pour(4) 特徴 同一分子から出発 汎用 配列設計不要 水の役割は本質的 同一分布で分割 容易に混合 最後に1の数を勘定 電気泳動など 読み取りは要工夫 Write once NP完全のあるクラス さまざまな実装法

環状ＤＮＡへの破壊書込み Cut Extend Ligate

3x3 ナイト配置問題 NAND (e,f) NAND (f,g) NAND (g,h) NAND (h,a) NAND (a,b) 11111111 01111111 10111111 NAND (a,b) NAND (b,c) NAND (c,d) NAND (d,e) a b c d e f g h a b c d e f g h

分子メモリの今後 アクエアス・コンピューティング さまざまな実装が可能 アイデア募集中 破壊書き込みメモリの水溶液 抽象性高、人為操作大の極端なＤＮＡ計算 さまざまな実装が可能 環状DNA＋制限酵素・修飾酵素 Leiden CDL、Binghamton CEL 線状DNA＋PNA侵入 Titech DNA/PNA アイデア募集中 タンパクの利用 光（百万倍早い）　

3SR法に基づく 分子進化リアクター 伏見 譲（埼玉大学）

3SRフローリアクター＝自然淘汰型進化リアクター ＝＞進化型分子コンピュータ 　　　　　　　　　　　　　　　　　　　＝＞進化型分子コンピュータ F V D = 　　　：希釈率　 定常状態： 　　集団平均比増殖速度 = D DNAi RNAi i=1,2,…,1010~15 適応度＝比増殖速度 データ 　　　　塩基配列 　　　物理化学的特性 　　　比増殖速度 プログラム 突然変異、組換えによる 新たなプログラム候補者の発生 　　　分子系によるアルゴリズムの自動獲得 　　　の可能性 （正解）　　　　　　　　　　　　　　　　　　　　　　　　　　 （最大値） (最適プログラム）

核酸分子系による増幅プログラムの自動獲得 環境（実験操作として表現 されたプログラムの不変部分）： 　SP6 RNA polymerase 　HIV-1 RT 　RT-primer 　Promoter-primer 核酸分子系による増幅プログラムの自動獲得 3SR増幅機構をコードしたDNA プロモーター プロモーター ヘアピン増幅機構(1)をコードしたDNA プロモーター ヘアピン増幅機構(2)をコードしたDNA プロモーター CATCH増幅機構をコードしたDNA 各増幅機構は各研究者が考えついたものだが、われわれの分子系は 一つの進化リアクター中でその全てを実現して見せた。

シグナル伝達経路のモデリングと細胞計算への応用 有田 正規（産総研） シグナル伝達経路のモデリングと細胞計算への応用 有田　正規（産総研）

シグナル伝達系のモデル (と細胞計算への応用) シグナルの受容からへ初期遺伝子の発現まで 東大医学部芳賀研究室との共同研究 Grb2/Sos Ras NGF EGF ｐ Raf-1 B-Raf MEK Rap1 MAPK Carbachol PMA PLC CalDAG DAG IP PKC Ca++ zif268 &

NGFでの生物実験 試薬 H7 GF PD EGTA GF+EGTA K252 NGF × ○ △ ○ ○ × EGTA ｐ ｐ K252a EGF PMA Carbachol EGTA ｐ ｐ K252a PLC H7 Grb2/Sos PKC DAG IP Ras GF109203X Raf-1 B-Raf Rap1 CalDAG PD098059 MEK Ca++ & MAPK zif268

NGFの結果の解釈 試薬 H7 GF PD EGTA GF+EGTA K252 NGF × ○ △ ○ ○ × EGTA ｐ ｐ K252a EGF PMA Carbachol EGTA ｐ ｐ K252a PLC Grb2/Sos PKC H7 DAG IP Ras GF109203X Raf-1 B-Raf Rap1 CalDAG MEK Ca++ & PD098059 MAPK zif268

自動推論 NGFから到達可能な点を探索: ｐ H7 … 探索パスの切断点に効くはず K252a 試薬　　H7　　GF　　PD　　EGTA　　GF+EGTA　K252 NGF　　 ×　　 ○ △　　　○　　　　　○　　　　　× NGF NGFから到達可能な点を探索: H7 … 探索パスの切断点に効くはず PD … 切断点でない部位に効くか、ＭＥＫをバイパスする経路が存在 ｐ K252a Grb2/Sos H7 Ras Raf-1 B-Raf MEK PD098059 MAPK zif268

実行画面 Ｊａｖａによる実装 簡単な推論 複数の異なる実験内容を入力できるように工夫

DNAナノテクノロジー ーAFMによるナノテクノロジーとDNA計算によるパターン形成技術の統合の試みー 西川明男（大阪電気通信大学） Sonia Antranz Contera, 文元鐡, 吉信達夫 岩崎裕（大阪大学）

背景と動機 分子計算プロジェクトの成果を活かして、新しい応用を目指したい。 Atomic Force Microscopyによるナノテクノロジーによるパターン生成(top down) DNA計算によるパターン生成(bottom up) AFMによるナノテクノロジーとDNA計算によるパターン生成を組み合わせることでより優れたパターン生成を目指したい。

AFMナノテクノロジー --AFMによる酸化膜のドットパターン-- トップダウン的に シリコン表面に 酸化膜を形成 Silicon oxide pattern by Moon et al.

DNA計算によるパターン生成 SeemanとWinfreeらは、４本のDNAからできているDNAタイルを組み合わせてDNAクリスタルを形成した。この時、４つのsticky endをどう与えるかによってパターンが変わる。 比較的簡単な 2本鎖DNAの末端 を利用すると、配線 などにも使える 可能性あり

本研究のアプローチ 最初に目標とするパターン→より複雑なパターンへ 酸化膜ドットパターン上にSH末端を持つDNAのオリゴマー を固定し、これに別のオリゴマーを計画的にハイブリダイズ させてシリコン表面上にDNAで配線パターン形成

現在までの進展状況 DNAオリゴマーをシリコン酸化膜上に固定する。 (SC1プロセスによる酸化膜） AFMによる固定されたDNAの画像化

今後の課題 DNAの配列に応じて、別々のドットパターンに固定する方法を開発せねばならない。 ドット上にDNAを固定する実験を行う。 バッファの洗浄だけではなく、バッファの選択を再考する必要がある。

Molecular Programming おわりにかえて

分子プログラミング 計算論から設計論への展開 生体分子 (DNA, RNA, protein) --- 組み合わせ的複雑さ 生体分子反応を設計・制御する技術の確立 生体分子 (DNA, RNA, protein) --- 組み合わせ的複雑さ 分子プログラム --- 二つの部分 分子自身に符号化されたプログラム (e.g., DNA配列) 実験操作列によって実行されるプログラム 分子プログラミングとは ... 両者のプログラムを協調させることにより、 生体分子反応を設計・制御 基本的であるがゆえに多くの応用を想定 バイオテクノロジー ナノテクノロジー コンビナトリアル・ケミストリー