萩谷 昌己 東京大学 大学院情報理工学系研究科 コンピュータ科学専攻

Slides:



Advertisements
Similar presentations
効率的に計算可能な 加法的誤りの訂正可能性 安永 憲司 九州先端科学技術研究所 SITA 2012 @ 別府湾ロイヤルホテル
Advertisements

プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
ラベル付き区間グラフを列挙するBDDとその応用
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
5.チューリングマシンと計算.
5.チューリングマシンと計算.
単一分子接合の電子輸送特性の実験的検証 東京工業大学 理工学研究科  化学専攻 木口学.
多数の疑似システムを用いた システム同定の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
Object Group ANalizer Graduate School of Information Science and Technology, Osaka University OGAN visualizes representative interactions between a pair.
上坂吉則 尾関和彦 文一総合出版 宮崎大輔2003年6月28日(土)
P,Q比が変更可能なScaLAPACKの コスト見積もり関数の開発
コンピュータ科学としての 分子コンピューティング
9.NP完全問題とNP困難問題.
データ構造と アルゴリズム 知能情報学部 新田直也.
分子プログラミングとは 生体分子=情報処理装置 分子コンピューティング 分子プログラミング 化学反応の自律的制御 → 自身にコード化
岩井 儀雄 コンピュータ基礎演習  ー探索、整列ー 岩井 儀雄
高山建志 五十嵐健夫 テクスチャ合成の新たな応用と展開 k 情報処理 vol.53 No.6 June 2012 pp
10.通信路符号化手法2 (誤り検出と誤り訂正符号)
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
生物科学科(高分子機能学) 生体高分子解析学講座(第3) スタッフ 教授 新田勝利 助教授 出村誠 助手 相沢智康
翻訳 5’ → 3’ の方向 リボソーム上で行われる リボソームは蛋白質とrRNAの複合体 遺伝情報=アミノ酸配列
分子コンピューティング ─計算機科学者(素人)から見た ナノテクノロジーと 分子エレクトロニクス─
7.時間限定チューリングマシンと   クラスP.
分子コンピュータの理論と構築 リーダー: 萩谷昌己(計算機科学・東京大学大学院理学系研究科) メンバー: リサーチ・アソシエート:
高速剰余算アルゴリズムとそのハードウェア実装についての研究
遺伝的アルゴリズムへの 統計力学的アプローチ 大阪大学 大学院理学研究科 鈴木譲 CISJ2005 於早稲田大学理工学部
2. 論理ゲート と ブール代数 五島 正裕.
正規分布における ベーテ近似の解析解と数値解 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
決定木とランダムフォレスト 和田 俊和.
奈良女子大集中講義 バイオインフォマティクス (9) 相互作用推定
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
・Proof readingについて ・PrimerのTm値について
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
22章以降 化学反応の速度 本章 ◎ 反応速度の定義とその測定方法の概観 ◎ 測定結果 ⇒ 反応速度は速度式という微分方程式で表現
オートマトンとチューリング機械.
Introduction to Soft Computing (第11回目)
Chemistry and Biotechnology
遺伝子の解析 第1弾 DNAについて&PCR法
分子生物情報学(2) 配列のマルチプルアライメント法
3. 論理ゲート の 実現 五島 正裕.
Data Clustering: A Review
論文紹介 - Solving NP Complete Problems Using P Systems with Active Membranes 2004/10/20(Wed)
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
適応的近傍を持つ シミュレーテッドアニーリングの性能
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
JAVAバイトコードにおける データ依存解析手法の提案と実装
統計ソフトウエアRの基礎.
B03 量子論理回路の 最適化に関する研究 西野哲朗,垂井淳,太田和夫,國廣昇 電気通信大学 情報通信工学科.
文法と言語 ー文脈自由文法とLR構文解析ー
遺伝的交叉を用いた 並列シミュレーテッドアニーリングによる タンパク質立体構造予測
第16章 動的計画法 アルゴリズムイントロダクション.
情報基礎Ⅱ (第1回) 月曜4限 担当:北川 晃.
構造的類似性を持つ半構造化文書における頻度分析
5.チューリングマシンと計算.
ポッツスピン型隠れ変数による画像領域分割
ガウス分布における ベーテ近似の理論解析 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
4.プッシュダウンオートマトンと 文脈自由文法の等価性
生命情報学特論 (6) 固定パラメータアルゴリズムと 部分k木
発表者: 稲葉 一浩 複雑ネットワーク・地図グラフ セミナー 2017/1/19
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年8月1日 3.2 競合学習
確率的フィルタリングを用いた アンサンブル学習の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
コンパイラ 2012年10月11日
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
集中講義(東京大学)「化学システム工学特論第3」 バイオインフォマティクス的手法による化合物の性質予測(1) バイオインフォマティクス概観
分子生物情報学(0) バイオインフォマティクス
Presentation transcript:

萩谷 昌己 東京大学 大学院情報理工学系研究科 コンピュータ科学専攻 分子コンピューティング概論 萩谷 昌己 東京大学 大学院情報理工学系研究科 コンピュータ科学専攻

生体分子コンピューティングとは 生体分子=情報処理装置 分子コンピューティングの目標 参考文献 化学反応の自律的制御 ⇒ 自身にコード化 微小・省エネルギー 超並列 分子の物理化学的性質 分子コンピューティングの目標 分子反応の持つ潜在的計算能力の理学的解明 分子反応に基づく新しい計算機能の工学的実現 参考文献 萩谷, 横森編: DNAコンピュータ, 培風館, 2001. 萩谷編著: 分子コンピュータの現状と展望 – 分子プログラミングへの展開, サイエンス社, 2004 DNA、RNA、タンパク質などの生体分子と通常分子の根本的な違いは、生体分子の持つ組み合わせてきな複雑さにあります。例えば、DNAなら4種類の塩基、タンパク質は20種類のアミノ酸の配列により複雑な情報を自由に表現することができます。さらに、生体分子は、この組合せ的な複雑さの中に、自分自身の化学反応を自律的に制御するための情報を、自分自身の中に符号化して格納することができます。 この絵はリボソームですが、mRNAという「入力」を(左上から)受け取り、アミノ酸を指定された順序で合成するという「処理」をほどこして、タンパク質を(右下へ)「出力」します。さらに、リボソーム自身はほとんどリボゾーマルRNAからできており、コードが反応を掌るという、われわれが日常使っているストアードメモリ方式の計算機と極めて類似した描像を持っています。 このように、個々の生体分子は計算能力を持った情報処理装置であり、生体はそのような情報処理装置の集合体であるとみなすことができます。 生体分子を情報処理装置と見た場合、従来のシリコンベースの計算機と比べるとかなり異なった特徴を持ちます。まず、サイズがナノメートルオーダーで微小であり、非常に少ないエネルギーで作動します。また、少ないスペースにアボガドロ数オーダーの大量の計算機を同時に持つことができます。分子は固定されておらず水溶液中で常に運動しています。そして、入出力をやはり分子で行うことができます。 分子計算とは、このような生体分子が潜在的に持っている計算能力を理学的に解明することと、これを利用して新しい計算機能を工学的に実現することを目的とする分野です。

分子コンピューティングの目標 分子反応の持つ計算能力の解析と その応用 分子反応に基づく新しい計算パラダイム 分子による計算を活用した分子計測技術 ⇒ バイオテクノロジーへの応用 プログラムされた自己組織化や分子マシン ⇒ ナノテクノロジーへの応用 分子による進化的計算 ⇒ 分子進化工学への応用 分子反応に基づく新しい計算パラダイム

関連分野(生物と情報) 分子生物学 バイオ 数理生物 分子進化工学 人工生命 進化⊂計算 インフォマティクス 生体分子 なまもの ソフトウェア 分子生物学   バイオ インフォマティクス 生体分子   コンピューティング 進化的計算 分子進化工学 人工生命 分析 数理生物 合成 進化⊂計算

関連分野(分子) 分子エレクトロニクス ナノテクノロジー 超分子化学 量子コンピューティング 光コンピューティング 分子素子を用いた電子回路 (既存の計算パラダイム) 分子回路の構成技術(ナノテクノロジー)としての 分子コンピューティング ナノテクノロジー 超分子化学 量子コンピューティング 光コンピューティング 分子生物学・バイオテクノロジー 分子進化工学

萩谷研ウェット実験室 工学部9号館501号室 工学部9号館の耐震工事が 3月末にようやく終わる。 4月より、実験再開。 4月19日大掃除

分子コンピューティング概論:目次 分子反応の持つ計算能力の解析 分子システム設計の計算論的側面 分子反応の持つ計算能力の応用 計算モデル・計算可能性・計算量 分子システム設計の計算論的側面 分子の設計・分子反応の設計 分子反応の持つ計算能力の応用 知的分子計測 自己組織化 分子マシン 分子反応に基づく新しい計算パラダイム 膜コンピューティング、アモルファス・コンピューティング 光や量子との融合 分子エレクトロニクスとの融合

分子コンピューティング概論:目次 分子反応の持つ計算能力の解析 分子システム設計の計算論的側面 分子反応の持つ計算能力の応用 計算モデル・計算可能性・計算量 分子システム設計の計算論的側面 分子の設計・分子反応の設計 分子反応の持つ計算能力の応用 知的分子計測 自己組織化 分子マシン 分子反応に基づく新しい計算パラダイム 膜コンピューティング、アモルファス・コンピューティング 光や量子との融合 分子エレクトロニクスとの融合

分子反応の持つ計算能力の解析 様々な計算モデル (計算モデルの)計算能力の解析 分子間の反応 vs. 分子内の反応 液相 vs. 固相 試験管、膜、細胞 他律的 vs. 自律的 (計算モデルの)計算能力の解析 計算可能性 計算量 --- 時間、領域 エラーや収量 --- 確率的な解析 現実の分子反応により忠実な解析へ

様々な計算モデルとその解析 Adleman-Lipton Seeman-Winfree DNAの選択的ハイブリダイゼーションを利用した 解の候補のランダムな生成 データ並列計算による解の抽出 Suyama --- dynamic programming Sakamoto-Hagiya --- SAT Engine Head-Yamamura --- aqueous computing Seeman-Winfree 各種形態のDNA分子の自己組織化(self-assembly) 自己組織化による計算

様々な計算モデルとその解析 Head Ogihara-Ray Hagiya-Sakamoto Shapiro 遺伝子の組み換えによる言語の生成 Ogihara-Ray ブール回路の並列計算 Hagiya-Sakamoto 状態機械(Whiplash) Shapiro 有限オートマトン 分子マシンのところで

Adleman-Liptonパラダイム Adleman (Science 1994) Lipton, et al. 分子による超並列計算 ハミルトン経路問題をDNAを用いて解く。 Lipton, et al. SAT問題をDNAを用いて解く。 分子による超並列計算 主として組み合わせ的最適化 DNAの自己会合によるランダムな生成 解の候補 = DNA分子 生物学実験技術を駆使した解の抽出 現状ではバイオテクノロジーのベンチマーク 遺伝子解析への応用を視野に入れた研究

Adlemanの最初のDNAコンピュータ O0 O6 PCR PAGE AF-SEP O1 O2 O3 O4 O5 HP

Adleman による実験 実験操作へ 頂点3 頂点4 ATCGATCG TAAGATA TAGCATTC 有向辺3 4 ATCGATCG (Science 1994) 4 3 1 start 6 goal 2 5 実験操作へ 頂点3 頂点4 ATCGATCG TAAGATA TAGCATTC 有向辺3 4 ハイブリダイゼーション ATCGATCG TAAGATA 抽出・検知 TAGCATTC 解分子

解の抽出・検知 PCR 長さ20 長さ140 頂点6 頂点0 ゲル電気泳動 頂点5の 相補配列 頂点1の 相補配列 磁石 頂点2を含む配列の抽出 各頂点について実行 解分子の抽出 磁石 頂点5を含む配列の抽出

Adleman-Liptonパラダイム 全ての解候補の生成 解の検査と抽出 解の検出 全ての 代入の生成 (Lipton 1995, 充足可能性問題) 0 0 0 0 変数Xn 変数X1 変数X2 変数X3 1 1 1 1 解の検査と抽出 Ti : 文字列の多重集合 (試験管) 解の検出 [Detect 命令] [Separate命令] T2 =+(T1, s) : s を含む配列の抽出 T2 =-(T1, s) : s を含まない配列の抽出 [Merge命令] T3 =T1 U T2 : T1 と T2 の混合 [Amplify命令] (T2, T3) =T1 : T1 の増幅(コピー)

SuyamaのDNAコンピュータ “counting” (Ogihara and Ray) O(20.4n) molecules for n-variable 3-SAT “dynamic programming” (Suyama) 生成と選択の繰り返し 解の候補の部分的な生成 解の候補の選択 指数オーダーには変わりはないが、 O(20.4n) は O(2n) よりずっと少ない。 固相法 磁気ビーズによるアフィニティ・セパレーション 自動化に適している ⇒ Robot!

基本演算とその実装 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

3CNF-SAT を解く DP的なDNA アルゴリズム

3CNF-SAT問題とその解

3CNF-SATを解くDP的アルゴリズム k のループ : k は変数の番号を動く j のループ : j は節の番号を動く if xk が j 番目の節の3番目のリテラル then 1番目のリテラルも二番目のリテラルも 充足しない割り当ては削除する XkF を残りの割り当てに追加する (Øxk が3番目のリテラルの場合も同様) k = 3 x3 X1T X2T X1T X2T X3F X1F X2T ) ( 3 2 1 x Ú Ø X1T X2F X3F X1T X2F X1F X2F ) ( 3 2 1 x Ú

3CNF-SATを解くDP的アルゴリズム k のループ : k は変数の番号を動く j のループ : j は節の番号を動く if xk が j 番目の節の3番目のリテラル then 1番目のリテラルも二番目のリテラルも 充足しない割り当ては削除する XkF を残りの割り当てに追加する (Øxk が3番目のリテラルの場合も同様) k = 3 Øx3 X1T X2T ) ( 3 2 1 x Ø Ú X1F X2T X3T X1F X2T X1T X2F ) ( 3 2 1 x Ø Ú X1FX2F X3T X1F X2F

3CNF-SATを解くDP的アルゴリズム k のループ : k は変数の番号を動く j のループ : j は節の番号を動く if xk が j 番目の節の3番目のリテラル then 1番目のリテラルも二番目のリテラルも 充足しない割り当ては削除する XkF を残りの割り当てに追加する (Øxk が3番目のリテラルの場合も同様) k = 4 x4 X1F X2T X3T ) ( 4 3 2 x Ú Ø X1F X2F X3T ) ( 4 3 2 x Ú Ø X1T X2T X3F X4F X1T X2T X3F X1T X2F X3F ) ( 4 3 2 x Ú

10-variable and 43-clause instance of 3SAT

DNA Computer Robot based on MAGTRATIONTM (Prototype No.1)

DNAコンピュータのプログラミング protocol-level script-level Pascal/C-level [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

Akira Suyama 東大教授(生物物理)

ヘアピン・エンジン(SATエンジン) 特平11-165114 Sakamoto et al., Science, May 19, 2000. DNAのヘアピン構造を利用した選択 ヘアピンの制限酵素切断 exclusive PCR 3-SAT 各節から選んだリテラルから成る一本鎖 DNA 相補的なリテラル = 相補的配列 矛盾したリテラルの選択 ⇒ ヘアピン 6-variable 10-clause 3-SAT Problem SAT計算の本質的部分 = ヘアピン形成 節や変数の数によらないステップ数 Autonomous molecular computation

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

ヘアピン構造による選択 制限酵素による切断 リテラルを表す配列中に 制限酵素サイトを挿入 Exclusive PCR 増幅率が低い。 exclusive PCRでは、各サイクルで溶液を薄めることにより、ヘアピンと非ヘアピンの増幅率の差を大きくしている。 実験操作の数は変数や節の数に依存しない。

Kensaku Sakamoto 東大&理研(生物化学)

Adleman-Liptonパラダイムに関する 現在のコンセンサス 電子コンピュータを凌駕するには程遠い。 スケールアップ問題 「分子が計算する」ことの proof of conceptとしては重要。 少なくとも、バイオテクノロジーの ベンチマークとして使うことができる。 さらに、遺伝子計測への応用(Suyama)。

Seeman-Winfreeの DNAの自己組織化による計算 3分岐 ... 線形 .... ヘアピン .... DX(ダブルクロスオーバー) 様々なDNA構造分子

Winfreeのタイリング Sierpinskiの三角形

DNA9, 2003

LaBeanたちによるtriple crossover分子

Headの遺伝子組み換えによる計算 数学的モデル(スプライシング・モデル) スプライシング操作 制限酵素とライゲースによる遺伝子組み換えの CC C TTAA G CC x= GG G AATT C GG EcoRI y= AA G AATT C TT TT C TTAA G AA AATT CTT GAA AAG TTC TTAA GGG CCC TTAA AATT CGG GCC z= GGG AATT CTT CCC TTAA GAA w= AAG AATT CGG TTC TTAA GCC

組み換えによる言語の生成 スプライシング規則: r = u1$u2#u3$u4 (x1u1u2x2, y1u3u4y2) |-r (x1u1u4y2, y1u3u2x2) R: スプライシング規則の集合 A: 文字列の集合(公理) L: RとAによって生成される言語 xÎA ならば、 xÎL x, yÎL かつ rÎR かつ (x, y)|-r (z,w) ならば、 z,wÎL RとAが有限ならば、Lは正則になる。

分子コンピューティング概論:目次 分子反応の持つ計算能力の解析 分子システム設計の計算論的側面 分子反応の持つ計算能力の応用 計算モデル・計算可能性・計算量 分子システム設計の計算論的側面 分子の設計・分子反応の設計 分子反応の持つ計算能力の応用 知的分子計測 自己組織化 分子マシン 分子反応に基づく新しい計算パラダイム 膜コンピューティング、アモルファス・コンピューティング 光や量子との融合 分子エレクトロニクスとの融合

分子計算の計算可能性 DNAの自己組織化の計算可能性 Winfreeの結果 遺伝子組み換えの計算可能性 スプライシング・モデルの様々な拡張

Winfreeの結果 (線形)構造分子によって生成される言語族 =正則言語族 (線形+ヘアピン+3分岐)構造分子によって 生成される言語族 =文脈自由言語族 (線形+DX)構造分子によって =帰納的可算言語族 =チューリング計算可能

Winfreeのモデルによる計算過程の例 c = f(a,b) d = g(a,b) c d a b a b Initial Configuration 1次元セルオートマトンの模倣

Erik Winfree Caltech, Assistant Professor (CS) MacArthur Fellow Presidential Early Career Award

スプライシング・モデルの拡張 いくつかの答え: 環状分子 マルチ試験管 時間差 スプライシング・モデル の生成能力 < 正則言語族 < 正則言語族 (スプライシング)+α? = 万能計算能力 いくつかの答え: 環状分子 マルチ試験管 時間差

環状組換えシステム プラスα として 環状文字列(環状DNA)を用いることを許す。 終端記号と非終端記号の区別を許す。 ( e.g. 大腸菌染色体とFプラスミドの組換え ) x u u x u u x 1 1 4 1 1 2 2 u u 3 4 u x 2 2 u 3 y スプライシング規則: u1$u2#u3$u4 y

分子コンピューティング概論:目次 分子反応の持つ計算能力の解析 分子システム設計の計算論的側面 分子反応の持つ計算能力の応用 計算モデル・計算可能性・計算量 分子システム設計の計算論的側面 分子の設計・分子反応の設計 分子反応の持つ計算能力の応用 知的分子計測 自己組織化 分子マシン 分子反応に基づく新しい計算パラダイム 膜コンピューティング、アモルファス・コンピューティング 光や量子との融合 分子エレクトロニクスとの融合

分子計算の計算量 時間 領域(=並列度) トレードオフの解析が重要 実験操作の回数 各操作に必要な時間 分子の数 分子の大きさ(長さ) 分子の計算能力の解析にはより本質的 領域(=並列度) 分子の数 最大 トータル 分子の大きさ(長さ) トレードオフの解析が重要

計算量の解析(Adleman-Lipton) Reif (SPAA’95) 非決定性チューリング機械において、入力長 n、空間 s、時間 2O(s) の計算は、我々のPAMモデルのもとで、O(s) ステップのPA-Match操作と、O(s log s) ステップのそれ以外の操作により、長さ O(s) の集合体を用いて実行することができる。 Beaver (DNA1, 1995) 多項式ステップの分子コンピュータは、PSPACEを計算する。 Rooß and Wagner (I&C, 1996) Liptonのモデルを用いて、ちょうど PNP=DP2 に属する問題を多項式時間で解くことができる。

Rooß and Wagner (I&C, 1996) Liptonのモデルを用いて、ちょうど PNP=DP2 に属する問題を多項式時間で解くことができる。 BIO({UN,BX,IN},{EM})-P = PNP= DP2 UN: 合併(マージ) T3 =T1 U T2 BX: ビット抽出(分離) T2 =+(T1, s) T2 =-(T1, s) IN: 初期化(ランダム生成) EM: 空テスト(検出) -P: 多項式時間(ステップ) PNP: NPオラクルを用いた多項式時間

計算量の解析(自己組織化) Rothemund and Winfree (STOC 2000) 任意の非増加非有界の計算可能関数 f (N) が与えられたとき、無限個の N に対して、f (N) より小さい個数のタイルを用いて、N×N の正方形を自己組織化により生成することができる。 Winfree, Eng and Rozenberg (DNA6, 2000) ストリング・タイルの線形自己組織化により、有限訪問チューリング機械(テープの各位置を訪れる回数の上限が存在するチューリング機械)の出力言語を生成することができる。

反応のエラーと収量 収量 エラー 確率的な解析 平衡 --- 平衡定数 (K) 平衡に到達する時間 --- 反応速度 (k) 例: A « B [B] = (K/(1+K))(1-e-(k+k-1) t ) K = k/k-1 エラー 例: ミス・ハイブリダイゼーション エラーの確率は0にはならない。 確率的な解析

確率的な解析 Karp, Keynon and Waarts (SODA’96) Kurtz (DNA2, 1996) 耐エラーのビット評価を達成するために必要な抽出操作の回数は Q(éloge dù×élogg dù) である。 Kurtz (DNA2, 1996) Adlemanの実験における経路生成の熱力学的解析 ハミルトン経路の生成に必要な時間 --- W(n2) Winfree (1998, Ph.D. Thesis) DNAタイリングの熱力学的解析 Rose, et al. (GECCO’99, etc.) 計算論的非一貫性 (ミス・ハイブリダイゼーションの熱力学的解析)

分子コンピューティング:目次 分子反応の持つ計算能力の解析 分子システム設計の計算論的側面 分子反応の持つ計算能力の応用 計算モデル・計算可能性・計算量 分子システム設計の計算論的側面 分子の設計・分子反応の設計 分子反応の持つ計算能力の応用 知的分子計測 自己組織化 分子マシン 分子反応に基づく新しい計算パラダイム 膜コンピューティング、アモルファス・コンピューティング 光や量子との融合 分子エレクトロニクスとの融合

分子システム設計の計算論的側面 「分子プログラミング」 分子の設計 分子反応の設計 分子マシン DNAの場合 = 配列設計 構造 ⇒ 配列(inverse folding) 自己組織化パターンの設計・分子マシンの設計 分子反応の設計 反応条件や操作順序の設計 シミュレーション・ツール 分子マシン 分子プログラミングの現在の目標の一つ

分子コンピューティング:目次 分子反応の持つ計算能力の解析 分子システム設計の計算論的側面 分子反応の持つ計算能力の応用 計算モデル・計算可能性・計算量 分子システム設計の計算論的側面 分子の設計・分子反応の設計 分子反応の持つ計算能力の応用 知的分子計測 自己組織化 分子マシン 分子反応に基づく新しい計算パラダイム 膜コンピューティング、アモルファス・コンピューティング 光や量子との融合 分子エレクトロニクスとの融合

配列設計 配列セットの評価 配列セットの探索 逆問題 ミスハイブリダイゼーションの回避 ハミング距離 エネルギー計算 ⇒ mfold(Zuker)、Viennaパッケージ 一様なTm(融解温度、melting temperature) 配列セットの探索 遺伝的アルゴリズム 符号理論 --- 有田のテンプレート法 逆問題 構造 ⇒ 配列(inverse folding) Viennaグループ

[AT]か [GC] の位置を全配列共通にする テンプレート法 Arita and Kobayashi, 2002 [AT]か [GC] の位置を全配列共通にする (これをテンプレートと呼ぶ) 例. 011010 より ACCTGA, TGCTCA, TCGACA, etc. → こうすると、全配列の融解温度は揃う。

スタッキング・エネルギー -DG kcal/mol (DNA/DNA) by Sugimoto et al. 2 1 AA AT TA CA CT GA GT CG GC GG TT TA AT GT GA CT CA GC CG CC

どうずらしても、連結した部分を考えても、 ミスマッチを含むテンプレート 上手にテンプレートを選べば、 シフト、リバースの際でも必ずミスマッチをもつ。 例: 110100のとき 110100 110100 110100 110100 110100 110100 110100 どうずらしても、連結した部分を考えても、 ミスマッチは最低2個存在

テンプレートの選び方 テンプレート T を、以下のパターンに対して、 最低 d 個のミスマッチを持つように選ぶ。 TR TTR 、 TRT TT、 TRTR 注: TRはTの逆配列。 T=110100ならば、TR=001011

テンプレートの例 長さ 6 (ミスマッチ 2) 110100 (26個中) 長さ 11 (ミスマッチ 4) 110100  (26個中) 長さ 11 (ミスマッチ 4)   01110100100, 01011100010, 11000100101  (211個中) 長さ 23 (ミスマッチ 9)  01111010110011001010000, 10110011001010000011110, 11100000101001100110101 (223個中)

DNA配列の設計法 “テンプレート + 誤り訂正符号” 1 1 0 1 0 0 (テンプレート) 誤り訂正符号は何でも利用可。 BCH 符号 Golay 符号 Hamming 符号 など。 A T C A G G  (DNA配列) 1 1 0 1 0 0 (テンプレート) + 0 1 0 0 1 1 (任意の符号語)

Masanori Arita 東大助教授(バイオインフォマティクス)

Inverse Folding Viennaグループ McCaskillのアルゴリズムの利用 コスト関数の最小化による配列の探索 Ω : 目的の構造 x: 配列 E(x,Ω): x におけるΩ の自由エネルギー G(x): 配列 x の集団自由エネルギー(McCaskill) p: x におけるΩ の確率

左の図の木の辺の数字はエネルギーの壁の高さ。頂点の数字は安定度の順位。

各温度でのエネルギーの壁の高さを表すグラフ。

分子コンピューティング:目次 分子反応の持つ計算能力の解析 分子システム設計の計算論的側面 分子反応の持つ計算能力の応用 計算モデル・計算可能性・計算量 分子システム設計の計算論的側面 分子の設計・分子反応の設計 分子反応の持つ計算能力の応用 知的分子計測 自己組織化 分子マシン 分子反応に基づく新しい計算パラダイム 膜コンピューティング、アモルファス・コンピューティング 光や量子との融合 分子エレクトロニクスとの融合

分子反応の設計 反応条件 操作の順序 シミュレーション 温度 塩濃度 時間 e-PCR VNA http://www.ncbi.nlm.nih.gov/genome/sts/epcr.cgi VNA

VNA: 仮想 DNAのシミュレータ 抽象的だが、十分に物理的 反応 抽象モデルと実際の反応との間の橋渡し 分子 ― 仮想ストランドのハイブリッド abcd || CDEF 反応 hybridization denaturation restriction ligation self-hybridization extension

VNA (続き) 目的 実行例 実装 DNA計算の方式の実現可能性の検証 生物学実験の妥当性の検証 (e.g., PCR実験) 生物学実験の適切なパラメータの探索 実行例 OgiharaとRayによるブール式の計算 Winfreeによるdouble-crossover unitの生成 PCR実験 実装 Java ⇒ アプレットとして実行可能

VNA (続き) 方法 組み合せ的爆発の回避 融合 シミュレーション技術における貢献 GAによるパラメータ探索 組み合せ的数え上げ 連続的シミュレーション (微分方程式) 組み合せ的爆発の回避 シミュレーション技術における貢献 閾値 確率的 GAによるパラメータ探索 PCR実験の増幅率の最適化 融合

分子コンピューティング概論:目次 分子反応の持つ計算能力の解析 分子システム設計の計算論的側面 分子反応の持つ計算能力の応用 計算モデル・計算可能性・計算量 分子システム設計の計算論的側面 分子の設計・分子反応の設計 分子反応の持つ計算能力の応用 知的分子計測 自己組織化 分子マシン 分子反応に基づく新しい計算パラダイム 膜コンピューティング、アモルファス・コンピューティング 光や量子との融合 分子エレクトロニクスとの融合

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

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

知的DNAチップ “(Dcn1∧¬Dcn2)∨Dcn3” “Dcn1∨Dcn3” “¬Dcn1∨ (Dcn2 ∧ ¬Dcn3)” Dcn3 marker stopper ¬Dcn2 Dcn1 label Dcn3 marker stopper Dcn1 label label ¬Dcn3 Dcn2 marker stopper ¬Dcn1

分子コンピューティング概論:目次 分子反応の持つ計算能力の解析 分子システム設計の計算論的側面 分子反応の持つ計算能力の応用 計算モデル・計算可能性・計算量 分子システム設計の計算論的側面 分子の設計・分子反応の設計 分子反応の持つ計算能力の応用 知的分子計測 自己組織化 分子マシン 分子反応に基づく新しい計算パラダイム 膜コンピューティング、アモルファス・コンピューティング 光や量子との融合 分子エレクトロニクスとの融合

DNAナノテクノロジー DNAによる自己組織化 DNAの網 分子糊としてのDNA DNAによるナノ粒子の自己組織化 DNAによるナノワイアの自己組織化 DNAタイル DNA自身による構造形成 プログラムされた自己組織化

ここで、DNAの大きさについて Seeman先生 二本鎖の直径は2nm。 一回転が10~10.5ベースペア。 スタックの幅が0.34nm、従って、一回転が3.5nmくらい。 Seeman先生

DNAの網 (阪大・産研・川合研究室) SiO2/Si基盤 親水性のあるSiO2基板上にのみネットワークを形成 写真はμメートル四方 http://www.sanken.osaka-u.ac.jp/labs/kawai-lab/02Lrep/32spm.htm

DNAによるナノ粒子の自己組織化初期の研究 C. A. Mirkin et al. DNA-based method for rationally assembling nanoparticles into macroscopic materials. Nature 382, 607-609 (1996) A. P. Alivisatos et al. Organization of ‘nanocrystal molecules’ using DNA. Nature 382, 609-611 (1996)

ナノ粒子:C. A. Mirkin et al. Nature (1996)                                                                                                        直径13nm http://www.chem.nwu.edu/~mkngrp/dnasubgr.html

ナノ粒子:A. P. Alivisatos et al. Nature (1996)

ナノ粒子からワイヤへ E. Braun et al. Nature (1998) 電極間の距離は12~16μm。 λ-DNA ワイヤの長さは12μm、直径は100nm。 銀イオン

ナノワイアの自己組織化 N. I. Kovtyukhova and T. E. Mallouk Nanowires as Building Blocks for Self-Assembling Logic and Memory Circuits Chem. Eur. J., 8, 4355-4363 (2002) ワイアの直径は15nmから350nm。

Winfree-SeemanのDNAタイル (double crossover分子)

Journal of Nanoparticle Research 4: 313-317 (2002) 金のナノパーティクル 直径は1.4nm S. Xiao et al. Journal of Nanoparticle Research 4: 313-317 (2002)

Nadrian Seeman New York University, Professor (chemistry) 1995 Feynman Prize in Nanotechnology

LaBeanたち: Four Four-arm Junctions 強固な構造へと変化する。

DNAチューブ(リボン) 幅約6nm、長さ約5μm

DNA碁盤 隣り合う junction の表に出る面を交互にすることにより、 歪みを打ち消すことに成功した。

応用例 Streptavidinタンパクの配置 銀の導入⇒DNAワイヤ

分子コンピューティング概論:目次 分子反応の持つ計算能力の解析 分子システム設計の計算論的側面 分子反応の持つ計算能力の応用 計算モデル・計算可能性・計算量 分子システム設計の計算論的側面 分子の設計・分子反応の設計 分子反応の持つ計算能力の応用 知的分子計測 自己組織化 分子マシン 分子反応に基づく新しい計算パラダイム 膜コンピューティング、アモルファス・コンピューティング 光や量子との融合 分子エレクトロニクスとの融合

分子マシン アクチュエータとしてのマシン 抽象的なマシン --- 有限状態機械(オートマトン) 両者はまだ渾然一体としている。 モーター トランスポータ 抽象的なマシン --- 有限状態機械(オートマトン) 有限の状態を持つ。 その状態を自律的もしくは入力に従って遷移させる。 出力を行うかもしれない。 汎用コンピュータへの第一歩 多くの応用 スイッチ・センサー メモリ(記憶保持・アドレシング) 両者はまだ渾然一体としている。

分子システム 入力: 情報処理 計算 出力: 分子システムによる有限状態機 分子 温度変化 光 塩濃度変化 電圧 移動 形態変化 構造形成  分子  温度変化  光  塩濃度変化  電圧 情報処理 計算 出力:  移動  形態変化  構造形成  光  電気  熱

分子(DNA)状態機械 末端配列機械 形態機械(Conformational Machine) 末端配列が状態を表現 Whiplash PCR(鞭打ちPCR) 状態が遷移するにつれ長くなる。 Shapiroのオートマトン 状態が遷移するにつれ短くなる。 形態機械(Conformational Machine) 分子の形態が状態を表現 YurkのMolecular Tweezers(分子ピンセット) SeemanのPX-JX2 Switch 我々のHairpin-Based Machine

SeemanのDNAモーター 2状態のDX分子

1) 2) Komiya et al. Whiplash PCR (WPCR) B B A C B A B A C : stopper sequence B 1) B A C B A B A C 2) This figure shows the scheme of successive transitions. The head A anneals onto the transition table, and then the new state B is polymerized. After the polymerization, the formed hairpin structure is denatured, and the head B is ready for the next transition. Komiya et al.

3) 4) Whiplash PCR (WPCR) B A B A C B B A C C The head B, now the current state of the machine, searches and anneals onto the next position in the transition table. The annealing of “B” allows the next state C to be newly polymerized. By iterating this “Annealing, Polymerization, and Denaturation” cycle according to the transition table, DNA molecules perform successive state transitions. B A C 4) C

Polymerization Stop I explain the basic biochemical reaction composing Whiplash PCR. Each state is encoded by a 15-nucleotide sequence. A sequence at the 3’-end of a DNA molecule works as the head of a state machine, simultaneously representing a current state. A concatenation of two states, termed “state pair”, defines a transition rule. A transition table is represented by a sequence of transition rules. The head anneals onto its complementary sequence in the transition table by forming a hairpin structure intramolecularly, and then a DNA polymerase catalyzes the polymerization of the new state. If the reaction mixture doesn’t contain dTTP, polymerization will stop exactly before the repeated “A”, the stopper sequence. We call this method “Polymerization Stop”.

Back-hybridization B A B A C B B A C B A C Note here that, the new state B can anneal not only onto the next position, but also onto the previous position where B was just polymerized. We call this kind of hairpin formation “back-hybridization”. Back-hybridization does not trigger any polymerization, but may cause a reduction in the efficiency of Whiplash PCR. Distribution of competing alternative hairpin forms and probability of success in transitions should be estimated. Competing Alternative Hairpin Forms

Temperature optimization for WPCR ・8 M urea 8% PAGE Komiya, et al. not 59.8 65.9 74.0 82.1 89.8 incubated 62.2 69.9 78.0 86.1 92.2 (℃) This figure shows temperature optimization for Whiplash PCR of 2 rounds on liquid phase with PLATINUM Pfx DNA polymerase. After denaturation at high temperature, transitions were performed under the isothermal condition. Bands that appeared at the highest position are the DNA molecules before transitions. Those at the lowest position are the molecules that finished the 1st round of transitions. And those at the middle position are the molecules that accomplished the 2nd round. The middle band with the highest intensity appeared in the lane of 78℃. Note that, under the thermal cycle schedule like normal PCR, the efficiency decreases. This result is supported by the statistical thermodynamic analysis recently reported in Physical Review E by John A.Rose. Thermal schedule 94℃ for 1 min.   ↓ x ℃ for 5 min. x =59.8 ~ 92.2 in 1X Pfx buffer (the composition unknown) 1 mM MgSO4 0.2 mM dATP, dCTP, dGTP 1.5 units Platinum Pfx DNA polymerase

・12% PAGE Successful implementation of transitions Komiya, et al. ( bp ) 155 140 125 110 This picture shows the successful implementation of 8 successive transitions. PCR products are analyzed by 12% polyacrylamide gel electrophoresis. In all lanes from 1 to 8, bands appeared at the positions of the expected length, respectively. The band in the lane i indicates there exist DNA molecules that finished the transition of the ith round and up. We excised the band in the lane 8, and confirmed the implementation of 8 successive transitions by sequencing analysis. 95 80 65 50

Ken Komiya 東大(生物化学) http://www.rel-ay.com/

ShapiroのDNAオートマトン IIS型制限酵素 認識部位 スペーサ a’ 入力の残り <S,a> <S,a> 遷移分子 a’ 入力の残り 入力の残り <S’,a’> 入力文字a’の配列は、各S’に対して<S’,a’>を含んでいる。 遷移分子は、スペーサを調整して、適切な個所で切断する。

ShapiroのDNAオートマトン Nature 2001 2入力文字、2状態 FokI a=CTGGCT b=CGCAGC 5’-p…22…GGATGTAC 3’-GGT…22…CCTACATGCCGAp S0,a→S0 5’-p…22…GGATGACGAC 3’-GGT…22…CCTACTGCTGCCGAp S0,a→S1

ギネスブック認定 (世界最小のコンピュータ)                                                      http://gnn.tigr.org/articles/03_03/fuels.shtml

体内における投薬制御への応用 Nature 2004 対象遺伝子のmRNAをブロック

遺伝子(mRNA)の活性によって 遷移分子の有効にしたり 無効にしたりする。 二分木プログラムを実現。

YurkeのDNAピンセット

三状態機械

Seeman: DNAによるDXの制御

System to Test the PX-JX2 Device

AFM Evidence for Operation of the PX-JX2 Device Yan, H., Zhang, X., Shen, Z. & Seeman, N.C. (2002), Nature 415, 62-65.

分子コンピューティング概論:目次 分子反応の持つ計算能力の解析 分子システム設計の計算論的側面 分子反応の持つ計算能力の応用 計算モデル・計算可能性・計算量 分子システム設計の計算論的側面 分子の設計・分子反応の設計 分子反応の持つ計算能力の応用 知的分子計測 自己組織化 分子マシン 分子反応に基づく新しい計算パラダイム 膜コンピューティング、アモルファス・コンピューティング 光や量子との融合 分子エレクトロニクスとの融合

新しい計算パラダイム 膜コンピューティング アモルファス・コンピューティング その他にも… Paun MIT のグループ Abelson と Sussman Knight その他にも… Smart Dust Programmable Matter Quantum-Dot Cell Automaton …

細胞膜モデル G. Paun (1998) 細胞膜(membrane)による計算過程の制御 スーパーセルシステム=万能計算モデル (例) G=(V,μ, M ,..., M ,  (R ,ρ ),...,(R ,ρ ),4) 1 4 1 4 1 4 V={a,b,b',c,f} アルファベット μ=[ [ [ ] [ ] ] ] 膜構造 1 2 3 3 4 4 2 1 M 膜 i 内要素の多重集合 i (R , ρ ) 膜 i 内の規則の順序集合 i i

細胞膜モデルによる n の計算 1 1 4 4 3 2 2 1 1 4 4 2 a, f b' f a ->b' a ->bδ f ->ff n+1 2 3 b ->b' b ->b(c, in ) (f->ff)>(f ->aδ) b ->b' b ->b(c, in ) (f->ff)>(f ->aδ) 4 4 2 2 1 1 n+1 4 n+1 b a 4 b f n n+1 n+1 2 (n+1) 2 2 c c a 2 b ->b' b ->b(c, in ) (f->ff)>(f ->aδ) 4 2 細胞膜モデルによる n の計算 2

アモルファス計算 自己組織化のための新しい計算パラダイム Computational particle 微細加工技術と細胞工学 低コストで様々なプロセッサ Computational particle 小さい計算力と少量メモリー 不規則配置、可動性 非同期、局地的相互作用 誤った挙動、環境の影響 同一プログラム 自分たちの位置や方向に 関する情報をもたない 近接のparticleと短距離 (半径r)の通信をする。 全体としては超並列計算システムになっている。 回路の自己組織化のシミュレーション

Amorphous Computingとは 背景 微細加工技術と細胞工学 低コストで様々なプロセッサを作る (厳密に正確な動作は不要) 新しい計算パラダイムとしての研究 不規則に配置されて、 非同期に局地的に相互作用するような, 計算機能の要素“computational particle”の 集合としてモデル化。 効果的にプログラムするにはどうすればよいか。 生物学的な組織の形成に関連? 生物学は単なるメタファーでなく,実装に使えないか?

Computational particleの性質 誤った挙動を示す可能性もある。 環境に影響される。 何らかの動作をするかもしれない。 動き回るかもしれない。 小さい計算能力と少量のメモリーを持つ。 全particleは同様にプログラムされている。 (局所状態の保持や乱数発生は可能) 自分たちの位置や方向に関する情報をもたない。 近接のparticleと短距離(半径r)の通信をする。 全体としては超並列計算システムになっている。 Cellular automata, 自己組織化システム

Wave propagationによる パターン形成 最初の“anchor” particleから始めてメッセージ(ホップの情報を持つ)を伝達していく。 生物学的なパターン形成と関連。 2つのanchor particleにより「成長の阻害」や「屈動性(tropism)」などもプログラムできる。 Cooreによるgrowing-point language(GPL)で プログラミングし、コンパイルしてparticleに セット。 Packet-radio network

Growing-point languageによる プログラムの例

パターン形成の例

http://www.swiss.ai.mit.edu/projects/amorphous/

量子ドット・コンピュータ QCAによるインバータ キワモノか? 量子コンピュータとは違う。 量子ドット・セル・オートマトン(QCA) ドミノのように四個の 量子ドットを並べる。 ドミノ内ではトンネル効果に よって電子が移動。 ドミノの相互作用により 状態が伝搬する。 配線が必要無い? しかし、量子ドットを正確に 配置しなければならない。 QCAによるインバータ ドミノはセルという。 セルには四個の量子ドットと二個の電子。 隣り合うセル内の電子はクーロン力によって相互作用する。 http://www.nd.edu/~qcahome/

計算モデル論(萩谷分) DNA/RNAの二次構造を予測する方法、動的プログラミングにより最小エネルギーおよび分配関数を求める方法、二次構造から配列を設計する方法について説明せよ。(文献を調べるとよい。) DNAを用いた自己組織化や分子マシンの実現可能性や応用について述べよ。

BASICS

DNA 糖 リン酸 塩基 デオキシリボース プリン塩基 --- 6角形と5角形の二つのリング ピリミジン塩基 --- 6角形一つ アデニン(A:Adenine) グアニン(G:Guanine) ピリミジン塩基 --- 6角形一つ チミン(T:Thymine) シトシン(C:Cytosine)

正確にはnucleoside リン酸基が付くとnucleotide

リン酸基 5’ 3’

二本鎖の直径は2nm。 一回転が10~10.5ベースペア。 スタックの幅が0.34nm、従って、一回転が3.5nmくらい。

A-DNA B-DNA Z-DNA

RNAとDNA

実験操作 PCR(ポリメラーゼ連鎖反応) ゲル電気泳動 アフィニティ・セパレーション 制限酵素による切断 ライゲースによる連結 クローニングとシーケンシング

PCR(ポリメラーゼ連鎖反応) プライマー 変性 プライマー プライミング 伸張 3’ 3’

ゲル電気泳動 長い分子 短い分子 下 上 ポリアクリルアミドゲル電気泳動 マイナス極 プラス極

DNA一本鎖の分離 標 的 分 子 プローブ 相補的 アニ―リング アビジン ビーズ ビオチン 抽出 磁石

DNA(RNA)の二次構造と その予測

DNA(RNA)の二次構造 ベースペア i.j の集合 k-ループ --- k 個のベースペアで囲まれたループ 1-ループ ヘアピン(hairpin) 2-ループ スタック(stack) バルジ(bulge) 内部(interior) マルチ・ループ(multi-loop) ループに対してエネルギーが割り当てられる。

ヘアピン スタック バルジ 内部 3-ループ これらの構造にエネルギーを割り当てる。 (nearest neighborモデル)

a. ヘアピン b. 内部 c. バルジ d. マルチ e. スタック f. シュードノット

動的プログラミング W(i, j) : i 番目のベースと j 番目の間の最小エネルギー V(i, j) : i と j がペアである場合の最小エネルギー W(i, j) = min(W(i+1, j), W(i, j-1), V(i, j), min(W(i, k)+W(k+1, j)) i£k<j V(i, j) = min(eh(i, j), es(i, j)+V(i+1, j-1), VBI(i, j), VM(i, j)) eh(i, j) : ヘアピンのエネルギー es(i, j) : スタックのエネルギー

動的プログラミング VBI(i, j) = min(ebi(i, j, i¢, j¢)+V(i¢, j¢)) i<i¢<j¢<j i¢-i+j-j¢>2 ebi(i, j, i¢, j¢) : 内部ループのエネルギー O(n4) になってしまう。 VM(i, j) = min(W(i+1, k)+W(k+1, j-1)) i<k<j-1 マルチ・ループのエネルギーが 0 の場合。

内部ループ 内部ループのエネルギー ebi(i, j, i¢, j¢) が、 ループの長さ (i¢-i+j-j¢)×c ならば、 VBI(i, j) = min(VBI(i, j, l)) l VBI(i, j, l) = min(VBI(i+1, j, l-1) + c, VBI(i, j-1, l-1) + c, c×l + V(i+1, j-l+1), c×l + V(i+l-1, j-1)) O(n3) になる。

マルチ・ループ マルチ・ループのエネルギーの近似: a + b×k´ + c×k k´ = 5 k = 3 k´: ペアを組まない塩基の数 O(n3) になる。 k´ = 5 k = 3

McCaskillのアルゴリズム 個々の構造のエネルギーを求めるのではなく、 可能なすべての構造のエネルギーの分布を 求める。 分配関数(partition function) 特定のベースペアが形成される確率 動的プログラミングによる。

基本配列 w[i,j] iとjの間の最小エネルギー ww[k,j] kがペアを作っている条件のもとでのw[k,j] 実際にはjとj-1の場合だけ記憶すればよいので、 再利用することができる。 v[i,j] iとjがペアを作っている場合の 配列はすべてINF(無限大)で初期化する。

for (j=2; j<=n; j++) for (i=j-1; i>=1; i--) { ww[i,j] = ww[i,j-1]; if (i.jがペア) ww[i,j] = min(ww[i,j], v[i,j]); for (temp=INF, k=i+1; k<=j; k++) temp = min(temp, w[i,k-1]+ww[k,j]); w[i,j] = min(temp, ww[i,j]); }

マルチループのための配列 v[i,j] iとjがペアを作っている場合の iとjの間の最小エネルギー vm[i,j] 仮定したときの最小エネルギー 最低一個はペアを含む。 vvm[k,j] kがペアを作っている条件のもとでのvm[k,j] 実際にはjとj-1の場合だけ記憶すればよいので、 再利用することができる。

for (j=2; j<=n; j++) for (i=j-1; i>=1; i--) { if (i.jがペア) { v[i,j] = min(v[i,j], ヘアピンのエネルギー); for (l=i+2; l<j-1; l++) for (k=l-1; k>i; k--) if (k.lがペア) v[i,j] = min(v[i,j], v[k,l]+2ループのエネルギー); for (temp=INF, k=i+2; k<=j-1; k++) temp = min(temp, vm[i+1,k-1]+vvm[k,j-1]); v[i,j] = min(v[i,j], temp+MLclosing+MLintern); } vmとvvmの設定;

マルチ・ループ MLclosing MLintern MLbase マルチ・ループのエネルギーの近似: a + b×k´ + c×k O(n3) になる。 MLintern MLbase k´ = 5 k = 3

vmとvvmの設定: vvm[i,j] = vvm[i,j-1]+MLbase; if (i.jがペア) vvm[i,j] = min(vvm[i,j], v[i,j]+MLintern); for (temp=INF, k=i+1; k<=j; k++) { temp = min(temp, vm[i,k-1]+vvm[k,j]); temp = min(temp, MLbase*(k-i)+vvm[k,j]); } vm[i,j] = min(temp, vvm[i,j]);

分配関数 構造が現れる確率は、 構造のエネルギーを G としたとき、 ボルツマン因子 exp(-G/kT) に比例する。 分配関数 Z とは、 すべての構造のボルツマン因子を 足し合わせたもの。 エネルギー G の構造の出現確率は、 exp(-G/kT)/Z で与えられる。

分配関数の計算 二次構造を網羅しながら 最小エネルギーを求めていたところを、 二次構造を網羅しながら、 ボルツマン因子を足し合わせればよい。 G exp(-G/kT) 初期値INF 初期値0 min + *

基本配列 w[i,j] iとjの間の分配関数 ww[k,j] kがペアを作っている条件のもとでのw[k,j] 実際にはjとj-1の場合だけ記憶すればよいので、 再利用することができる。 v[i,j] iとjがペアを作っている場合の 配列はすべて0で初期化する。

for (j=2; j<=n; j++) for (i=j-1; i>=1; i--) { ww[i,j] = ww[i,j-1]; if (i.jがペア) ww[i,j] = ww[i,j]+v[i,j]; for (temp=0, k=i+1; k<=j; k++) temp = temp+w[i,k-1]*ww[k,j]; w[i,j] = temp+ww[i,j]; }

マルチループのための配列 v[i,j] iとjがペアを作っている場合の iとjの間の分配関数 vm[i,j] 仮定したときの分配関数 最低一個はペアを含む。 vvm[k,j] kがペアを作っている条件のもとでのvm[k,j] 実際にはjとj-1の場合だけ記憶すればよいので、 再利用することができる。

for (j=2; j<=n; j++) for (i=j-1; i>=1; i--) { if (i.jがペア) { v[i,j] = v[i,j]+ヘアピンの分配関数; for (l=i+2; l<j-1; l++) for (k=l-1; k>i; k--) if (k.lがペア) v[i,j] = v[i,j]+v[k,l]*2ループの分配関数; for (temp=0, k=i+2; k<=j-1; k++) temp = temp+vm[i+1,k-1]*vvm[k,j-1]; v[i,j] = v[i,j]+temp*expMLclosing*expMLintern; } vmとvvmの設定;

vmとvvmの設定: vvm[i,j] = vvm[i,j-1]*expMLbase; if (i.jがペア) vvm[i,j] = vvm[i,j]+v[i,j]*expMLintern; for (temp=0, k=i+1; k<=j; k++) { temp = temp+vm[i,k-1]*vvm[k,j]; temp = temp+expMLbase^(k-i)*vvm[k,j]; } vm[i,j] = temp+vvm[i,j];

分子エレクトロニクス

                                                                      1974年にIBMのAviramとRatnerが提案した分子ダイオード

                                                

ロタクサン C. P. Collier et al. Science 285, 391-394 (1999) この他、単一分子素子として有名なのは、 1974年にIBMのAviramとRatnerが提案した分子ダイオード 1988年にAviramが提案した分子トランジスタ 三つの繋がったベンゼン環の真中がねじれるやつ カーボンナノチューブ C60分子(フラーレン)を使った単電子トランジスタ(Wada他、2000) C. P. Collier et al. Science 285, 391-394 (1999)

カテナン C. P. Collier et al. Science 289, 1172-1175 (2000) +2Vでopen -2Vでclose ~0.1Vでread UCLA ⇒ HP C. P. Collier et al. Science 289, 1172-1175 (2000)

自己組織化

自己組織化というけれど… 人によって千差万別。 粒子やドット、もしくは、その配列の形成を 意味することが多い。 自己組織化の場も色々。 液相・気相・界面・膜・・・ 回路のような複雑なパターンを 自己組織化させる試みは決して多くはない。 DNAナノテクノロジー プログラムされた自己組織化 Algorithmic self-assembly

量子ドットの自己組織化 (電通大・山口浩一研究室) http://crystal.ee.uec.ac.jp/dot.html GaAs上にInAsの微小な結晶粒を自己組織化。 SK成長モード(Stanski-Krastnaow)と呼ばれる成長条件(歪の利用) 高さ6nm、底辺20nm。 透過型電子顕微鏡 http://crystal.ee.uec.ac.jp/dot.html

タンパクによる量子ドット配列の自己組織化 (松下電器・山下一郎研究室+奈良先端大・冬木研究室) タンパクによる量子ドット配列の自己組織化 (松下電器・山下一郎研究室+奈良先端大・冬木研究室) 直径12nmのフェリチンに直径6nmの粒子を貯蔵させる。 http://adw3.aist-nara.ac.jp/EVENT/tokyo-sympo2002/fuyuki.htm

分子の鎖でナノワイヤー配線 (理研・青野研究室) ジアセチレン化合物分子 ワイアの太さは3nm http://www.riken.go.jp/r-world/info/release/press/2001/010205/