生体中においてDNA分子は，4種の塩基 {A, C, G, T} が並んだ記号列として遺伝情報をコードしている．DNA 分子上の各塩基は互いに相補的な塩基とのみ塩基対を組み，安定な二重らせん構造を形成する．この過程は高度な識別能力を有しており，生命活動を実現するために重要な過程である．DNA 分子が二重鎖を形成することで，酵素による DNA 分子の連結や複製・増幅，組換えといった反応が行われる．また，直接塩基配列を認識する酵素によって，DNA 分子は配列特異的な切断などを受ける．これらの反応によって，DNA 分子上の塩基配列は様々な変換をほどこされ，遺伝情報が処理されている．遺伝情報が発現される際には，配列情報を保持する記録テープとしての DNA 分子から，情報の一部が mRNA に写しとられ（転写），その配列情報をリボソームがスキャンしながらタンパク質が合成される（翻訳）．これは，テープ上の記号をヘッドが読みとりながら移動していく抽象的な計算機の動作とよく似ている．

「DNA コンピューティング」では，生体分子がその属性として持つ情報処理能力に着目し，DNA 分子を用いて任意の演算を行う．このような研究は，1994年に L. M. Adleman が，“むずかしい”組合せ問題である「有向ハミルトン経路問題」の小さな例題を，DNA分子を用いた実験操作によって解いたことで，はじめて現実的なものとなった．その後，種々のモデルが提案され，実際にいくつかの問題が解かれた．そこでは，溶液中に存在する膨大な数の DNA 分子に「解」の候補をコードさせる．これらの分子のなかから正しい解の条件を満たす候補分子を，分子生物学的な操作によっていっせいにスクリーニングする．最終的に得られた分子がコードする情報を，電気泳動やシーケンシングなどの操作で読み出す．DNA 分子の情報担体としての側面を「分子メモリ」として利用し，たくさんのデータに対する並列な演算が，人手を要する操作によって実験室規模で実現された．

これに対し，生体分子が本来持っている「自律的」かつ「特異的」に相互作用するという性質を，積極的に演算に活用する研究も行われている．そこでは，塩基配列特異的な反応を利用して演算をプログラミングし，DNA をはじめとする生体分子が自律的に演算を実行する．このような演算では，問題を解くために必要な実験操作の数が，対象とする問題の規模によらず一定ですむ．だが，これまでに実装された計算モデルでは，いずれもプログラムを複数の分子に分割してコードしていた．そのため並列性という点については，1つの反応容器内で1つのプログラムを実行するものであった．

本研究では，DNA 分子が自律的に相補塩基の探索を行う能力にもとづいて，連続的な状態遷移を実行する分子機械を実装する．この分子機械のデザインでは，3'末端の配列が機械の「内部状態」を表現する．一本鎖 DNA 分子が二次構造を形成すると，それにともなって DNA ポリメラーゼによる伸長反応が行われる．3'末端の配列は順次書き換えられていき，状態は連続的に変化する．各 DNA 分子は，5'末端側の塩基配列上に状態遷移についてのプログラムをコードしており，このプログラムにしたがって状態遷移を実行する．個々の分子はそれぞれ独立した「分子計算機」としてはたらき，原理的には一つの反応容器内で，複数の入力に対して複数のプログラムを同時に実行することが可能である．新規な並列性を有するこの分子機械について，実際に多段階の状態遷移を行うことに成功し，組み合わせ問題の解法に応用したことを報告する．

研究概要

分子計算機のデザイン

DNA 分子は，溶液中のイオン濃度や温度，他の分子との相互作用によって様々なコンフォメーションや2次構造をとり得る．それぞれをひとつの状態と対応づけると，分子がそれらの間を変化する過程は状態遷移とみなせるので，演算に利用できる．しかし，多段階の高次構造変化を任意にデザインし，厳密に制御することは困難である．これに対し，塩基配列によって状態を定義するというより単純な方法は，配列の組み合わせ的多様さを活用することができるので，有効であると考えられる．また，状態を塩基配列によってコードし，酵素反応によってなんらかの変換を配列にほどこす場合，配列を特異的に認識する酵素にもとづいたデザインでは，酵素の認識配列の多様性によって，やはりとり得る状態の数が制限されてしまう．そこで，塩基配列特異的な過程については酵素反応を必要とせず，配列特異的な過程が行われた後に，酵素が配列非特異的に反応を行うような分子機械をデザインした．

伸長停止法

連続的な状態遷移を DNA 分子が自律的に行うためには，状態遷移を実現する反応を段階的に実行する必要がある．各「状態」を15塩基の配列で定義する．状態配列が二つ並んだ状態対により「遷移則」を表現し，この遷移則をひとつの分子上に並べることで，「遷移テーブル」を塩基配列によってコードすることができる．DNA 分子の3'末端にある配列は内部状態を表すと同時に，分子機械の「ヘッド」として遷移テーブル内の相補部位にハイブリダイゼーションする．DNA 分子がヘアピン構造を形成すると，3'末端から DNA ポリメラーゼによる相補鎖伸長が起こる．この際，伸長反応の鋳型となる遷移テーブル部位のちょうど1状態分伸長した先に，1種の塩基が連続した配列 (AAA) を入れておく．反応溶液中からこれと相補的なヌクレオチド (dTTP) をのぞくことで，伸長反応をそこで停止させることができる (Fig.1).

連続状態遷移

1段階の状態遷移が伸長停止法によって完了した後，ヘアピン構造を変性させる．伸長反応によって3'末端に付加された配列は，新たな内部状態を表しており，遷移テーブル内の別の相補部位にハイブリダイゼーションすると，次段階の伸長反応が起こる．この「ヘアピン形成→伸長→変性」と，それにともなう伸長反応のサイクルを繰り返すことにより，状態遷移が連続的に進行していく．

はじめに，2段階の状態遷移が可能な DNA 分子を設計した．1段階目の遷移を完了した分子は，状態配列2つ分の長さの2本鎖部位を解離させ，新たに状態配列1つ分の長さの2本鎖を形成して，2段階目の遷移を行わなければならない．これは自由エネルギー的には不利な過程であるが，実際に連続状態遷移をこころみた結果，等温条件下で上記の反応サイクルが進行し，2段階の状態遷移を実行することに成功した．

次に，分子機械への入力系を確立した．DNA 分子に任意の演算を行わせるためには，任意の入力ができなければならない．短鎖 DNA 分子を鋳型とした相補鎖伸長により，初期状態の入力を実現した．

さらに，多段階の状態遷移が可能かどうかを検討するため，8段階の状態遷移が可能なDNA分子を設計した．予期しない分子間反応が起こることを避けるため，反応は固相上で行った．分子機械としての DNA の5'末端をビオチン化し，ストレプトアビジンビーズ上に結合する．実際に連続状態遷移をこころみた結果，8段階すべての遷移を効率よく実行させることに成功した (Fig.2A)．反応条件を検討したところ，72〜80℃という温度範囲内で8段階の遷移が進行することを明らかにした．また，全体のうちどれくらいの割合の DNA 分子が何段階までの状態遷移に成功したかを明らかにするため，リアルタイム PCR 法による定量的解析を行った．その結果，現行の反応条件下では，平均して70％以上の割合で状態遷移が進行すること (Fig. 2B)，および反応時間を増加させることで状態遷移がさらに進行することを示した．

組合せ問題の解法

「有向ハミルトン経路問題」は，頂点と各頂点間を結ぶ向きのある経路からなるグラフについて，始点となる頂点を出発して，すべての頂点を1回ずつ通って終点となる頂点にたどりつく経路（ハミルトン経路）が存在するか否かを検証する問題である．この問題は，頂点の数が増えるにしたがって検証すべき「解の候補」経路の数が指数関数的に増加する，「NP完全問題」と呼ばれるクラスに属している．そのため，逐次計算型である電子コンピュータでは解くことがむずかしい問題である．6頂点のグラフを例にとり，状態遷移する一本鎖DNA分子を用いた解法をこころみた．解法アルゴリズムを以下に示す．

（i）すべての解の候補経路をランダムに生成する．（ii）始点である頂点から始まり，終点である頂点で終わる経路を選び出す．（iii）すべての頂点を通る経路を選び出す．（iv）6つの頂点を通る経路を選び出す．（v）（iv）までの操作で解の候補経路が残っていたら，その経路はハミルトン経路であり，このグラフにはハミルトン経路が存在する．

アルゴリズムの（i）は制限酵素の認識配列内に経路配列をコードすることにより，制限酵素切断とその後のライゲーション反応を行うことで，（ii）は特異的プライマーを用いた PCR 増幅によって，（iii）は連続状態遷移とその後の制限酵素切断および PCR 増幅によって，（iv）は電気泳動によって分子の長さで分離することで，それぞれ実行した．その結果，ハミルトン経路をコードしているはずの DNA 分子が得られた．この分子の配列を決定し，正しい順番で頂点が並んだハミルトン経路をコードしていることを確認した．この解法により，異なるプログラムをコードする複数種の DNA 分子が，一つの反応容器内でそれぞれ独立に状態遷移を実行したことを示した．

本研究で実装した一本鎖 DNA による分子機械は，遷移テーブル内にコードした情報を3'末端に次々と写しとりながら，状態遷移を連続的に実行する．この遷移にともなって付加された配列は，演算の履歴を表している．履歴部分の着脱を可能にすれば，ひとつの分子機械が行った演算の結果を出力し，別の分子機械の入力とする通信が実現できる．ひとつひとつの分子が実行する局所的な演算を組み合わせて，反応溶液全体で行う大域的な演算への拡張が可能である．

伸長停止法

2A　8回連続状態遷移の確認　レーンM :20 bp ladder マーカーレーン i(i=0〜8) : (35+15i)bpのバンドはi回目の状態遷移に成功したことを示す.

2B　8回連続状態遷移の定量解析　指数近似曲線を青で示す．各段階の状態遷移に成功した分子のうち，およそ70％が次段階の遷移に成功している．

生体中においてDNA分子は，4種の塩基 {A, C, G, T} が並んだ記号列として遺伝情報を符号化（コード）している．DNA 分子上の各塩基は互いに相補的な塩基とのみ塩基対を組み，安定な二重らせん構造を形成する．この過程にもとづいて行われる様々な反応を利用した塩基配列の変換によって，任意の演算を実行することができる．

従来の「DNA コンピュティング」では，溶液中に存在する膨大な数の DNA 分子を用いて「解」の候補をコードし，正しい解の条件を満たす候補分子を分子生物学的な実験操作によってスクリーニングすることで，たくさんのデータを同時に処理する演算についての研究が主に行われてきた．そこでは，DNA 分子は「分子メモリ」として活用され，実際にいくつかの問題について解法が報告されている．これに対して，生体分子が本来持っている「自律的」かつ「特異的」に相互作用するという性質を，演算に活用するこころみも行われてきた．そこでは，塩基配列特異的な反応を利用して，各演算ステップを実現する反応を実行する手順をプログラミングすることで，自律的に進行する演算が実現される．だが，これまでに実装された計算モデルでは，いずれもプログラムを複数の分子に分割してコードしており，1つの反応容器内で1つのプログラムを処理するものであった．そのため，複数のプログラムについて，同時に段階的な演算ステップを実行することが要求される問題の解法を行うことは不可能であった．

論文提出者は，分子生物学的な実験により，一本鎖 DNA 分子を用いた分子機械を構築した．この分子機械のデザインによれば，連続的な状態の変化（状態遷移）を行うことが可能であり，1つの反応容器内で複数のプログラムを同時に処理することができる．論文提出者は，分子機械の動作を実験によって検証し，自律的なプログラムの実行について研究を行った．本論文では，その研究の成果が述べられている．

本論文は5章からなる．第1章では，DNA コンピューティング研究の経緯と，論文提出者が行った研究のこの分野における位置づけについて述べられている．第2章では，研究の概要と，連続的な状態遷移が実行できる新規な反応のデザインについて述べられている．第3章と第4章では，論文提出者が行った実験について，材料と方法，および結果と考察がそれぞれ述べられている．まず，新規にデザインされた反応によって複数回の状態遷移を行うことが実現可能であるのかどうかを，連続2回の遷移反応について解析している．この解析において論文提出者は，複数のヘアピン構造が競合する状態遷移反応が，比較的高温な等温条件下での非平衡状態を利用して進行させることができることを見出し，効率の良い反応条件を決定している．この結果にもとづいて，さらに多段階の遷移反応をこころみ，配列セットの設計や相補鎖伸長を利用した分子機械への入力法とあわせて，連続8回の遷移反応を行うことに成功している．そして，連続8回の状態遷移反応を行った結果については，DNAコンピューティング研究では数少ない定量レベルでの解析を行っており，分子機械の性能やこれを用いた演算の妥当性についての考察を行っている．さらに論文提出者は，プログラムの同時処理という新規な並列性を有する演算パラダイムの実現可能性を検証するため，変数の数が増えるにしたがって検証すべき解の候補の数が指数関数的に増加する，「NP完全問題」と呼ばれるクラスに属する「有向ハミルトン経路問題」を例にとり，実験による解法を行っている．異なるプログラムをコードする複数種の DNA 分子を用いて，一つの反応容器内でそれぞれ独立に遷移反応を実行させて問題を解くことに成功しており，個々の分子がそれぞれ独立した「分子計算機」としてはたらくことを示している．以上の成果にもとづいて，第5章においては，総合討論を行っている．

なお，本論文の第2〜5章の一部は，東京大学の横山茂之教授，萩谷昌己教授，坂本健作助手，西川明男博士，合津秀隆研究員，電子技術総合研究所の有田正規博士との共同研究，第3〜4章の一部は，埼玉大学の伏見譲教授，北海道大学の大内東教授，山本雅人助教授，亀田充史博士との共同研究であるが，論文提出者が主体となって研究を遂行し，解析および検証を行ったもので，論文提出者の寄与が十分であると判断する．

したがって，博士（理学）の学位を授与できると認める．