「パラメータ制御方式による分子計算」
研究代表者：
研究分担者：大内山本
川村

東 （北海道大学大学院情報科学研究科）
雅人（北海道大学大学院情報科学研究科）
秀憲（北海道大学大学院情報科学研究科）

１．研究の目的
化学反応のもつ超並列性を利用した分子計算が注目を浴びるようになって以来，解候補の並列的生成，及び，検査といったいわゆる Adleman-Lipton パラダイムや，状態機械の実現による計算方式など数多くの分子計算手法が提案されてきた．これらに共通する問題として，計算誤差に関する議論がある．分子計算が生体分子を用いた化学反応に基づく計算手法である以上，計算誤差に関する議論は避けて通れない．計算誤差を望まれない反応が起こることとして用いることとする．計算誤差には，反応温度や分子濃度といった実験操作に起因する外在的なものが存在するが，これらは実験プロトコルの最適化を行うことによって誤差の減少が期待できるものである．しかしながら，こういった実験プロトコルの詳細な分析や，反応時間と反応効率の関係などの分析についての研究が行われていない現状がある．また，
DNA 濃度などが計算の重要な役割を果たす計算モデルでは，DNA 濃度の定量性の議論も必要となってきている．このような定量性を含めた計算モデルでは，より信頼性の高い計算手法が重要となる．一方，計算誤差は，塩基配列設計の問題に起因する場合も多い．従って，高信頼性を有する分子計算手法を確立するためには，DNA 塩基配列へのコーディングの問題，及び，実験過程におけるプロトコルの問題，の両面からアプローチする必要がある．
以上のような背景から本研究では，分子計算，特に，DNA を用いた計算において，計算の信頼性を向上することが重要であると考える．DNA 分子による計算(DNA コンピューティング)において，実験結果に影響を及ぼすパラメータは非常に多い．用いる DNA の塩基配列，DNA の種類や濃度，反応プロトコル(温度，バッファ，反応時間，他多数)などによって計算結果は著しく異なるといってよい．しかしながら，こういった様々なパラメータについての詳細な分析や，反応時間と結果の関係などの分析についての研究が行われていない現状がある．本研究では，これらの現状をふまえて，DNA 計算の信頼性向上を大きな目的とし，塩基配列設計の問題を中心に検討し，DNA 計算の応用技術についても実現を試みる．

２．研究の項目と役割分担
目的達成のために，大内班では，主に化学実験に関する部分を山本が担当し，大内，川村は，塩基配列設計手法や実験プロトコルの最適化理論等について担当している．具体的な研究項目は以下の通りである．
(1) 自由エネルギーに基づいた塩基配列設計アルゴリズムの提案

(2) 自由エネルギーに基づいた塩基配列設計の有効性の検証(3) DNA タイルのための自由エネルギーを考慮した塩基配列設計アルゴリズムの提案(4) DNA リレーショナルデータベースの実現とデータ検索

３．各項目について(1) 自由エネルギーに基づいた塩基配列設計
DNA コンピューティングの多くは，相補対な DNA の結合によって自律的に二本鎖を形成する性質を利用している．そのため，二本鎖を形成するハイブリダイゼーション反応の制御が信頼性向上の最も重要な要素の一つである．DNA の二本鎖の形成の様相は，塩基配列に強く依存するため，塩基配列設計が非常に重要となる．塩基配列設計では，DNA の塩基配列を適切に設計し，意図した結合のみが形成される必要がある．従来の塩基配列設計では，結合の安定性の指標として相補対の数（以下，BP）を用いていたが，これは粗い近似に過ぎないために，意図しない結合を防ぐことができないという問題があった．
本研究では，結合の安定性の指標として最小自由エネルギー（以下， ΔGmin ）を用いた塩基配列設計法を提案した．特に，自身の相補鎖とのみ結合するような塩基配列集合の設計問題に関してアルゴリズムの提案および評価を行った． ΔGmin の予測には計算コストがかかるため，限られた時間では多数の解候補を探索するには局所的な探索が適していると考えられている．このような背景から，提案するアルゴリズムは，ランダムに解候補を生成し，解候補が全ての制約条件を満たした場合にのみ解集合に加えるという手続きを繰り返すアルゴリズムである generate-and-test 法を採用した．その際，制約条件判定のために 3 つのフィルターを用いて探索を行う．Tm フィルターと ΔGmin フィルターは，それぞれ Tm と ΔGmin に関する制約の判定を行うために用いられる．実際には， ΔGmin の予測の計算コストを軽減するため， ΔGmin の粗い近似であり計算コストのかからない ΔG gre という尺度を提案し， ΔG gre の値に基づき，制約を満たさない配列を除くことのできる ΔG gre フィルターを提案した（図 1）．

ΔGmin フィルターで除くべき候補の塩基配列を ΔG gre フィルターで前もって除くことが可能となるため， ΔGmin 計算を省略することができ，全体の計算時間の削減が確認できた．

(2) 自由エネルギーに基づいた塩基配列設計の有効性の検証(1)の研究で述べたように、従来の塩基配列手法の多くは，相補対の数 BP を主な指標として用いていた．(1)では，最小自由エネルギー ΔGmin に基づく塩基配列手法を提案した．本研
究では，この最小自由エネルギーに基づく塩基配列設計がこれまでの BP での設計手法と比較して，計算の信頼性の立場から，本当に有効であるかどうかを化学実験によって検証した．

ランダムに配列を生成
yes
O (L )

Tm filter

noyes( )ΔG gre filter

O L2noyes( )ΔG min filter

O L3noyes
配列数が規定の数

noyes終了

図 1 自由エネルギーを考慮した塩基配列設計アルゴリズムの概要
具体的には，BP による評価が同じであるが，最小自由エネルギーの異なる複数の一本鎖塩基配列対を用意し，一般的な条件下でハイブリダイゼーション反応を行い，二本鎖の形成が行われているかを電気泳動によって確認した．二本鎖が形成された場合は，ゲル内の移動度が減少し，一本鎖の場合に比べて，異なるバンドとして検出できる．
実験の結果から，BP に比べて最小自由エネルギーによる評価の方が適切であること，また，ハイブリダイゼーションにより二本鎖を形成するためには，計算される最小自由エネルギーの絶対値がある閾値以下とならなくてはならないことがわかった．これらの知見は，(1)での塩基配列設計手法と組み合わせることで，ミスハイブリダイゼーションを起こさない塩基配ΔGmin (kcal/mol)

列の設計が可能となると考える．

0-2-4-6-8-10-12-14-16-18-20-22-24-26-28

結合していない結合している

8910111213141516171819BP

図２BP と ΔGmin の値と二本鎖形成との関係( ΔGmin がほぼ-15 付近より低い場合は，二本鎖への結合反応が観測された．一方，BP の値と結合の間には弱い相関しか見られない．)

(3) DNA タイルのための自由エネルギーを考慮した塩基配列設計アルゴリズムの提案
複数の一本鎖 DNA を巧みに交叉させながら相補結合させることで，平面的なタイル構造を作ることができる．このようなタイル構造を DNA タイルと呼ぶ．一般に，各 DNA タイルは複数の粘着末端(一本鎖 DNA)を持っており，他のタイルの相補的な粘着末端と特異的に結合することで，より大きな構造を形成することが可能である．粘着末端部を適切に変えて(プログラムして)DNAタイルを自己組織的に反応させることで，さまざまな構造やタイルパターンの生成を制御する試みが行われている．しかしながら，DNA タイルによってタイルパターンの生成を制御するた

めるには，DNA タイルの構成要素となる複数の一本鎖 DNA の塩基配列を適切に設計する必要がある．しかしながら，現状では，複数の一本鎖 DNA を用いて複雑なタイル構造を生成するための塩基配列設計手法はほとんど確立されていないといってよい．ほとんどの DNA タイルは，Seeman による配列設計手法を採用しているが，これは各一本鎖 DNA に含まれるある長さ以上の部分塩基配列が他の一本鎖 DNA の部分配列として現れないような塩基配列を探すインタラクティブなプログラムである．この手法は，シンプルで分かりやすいが一本鎖DNA 間の結合性を単なる部分配列の相補性のみで近似しているのみで，安定性の判定基準としては不十分である．
本研究では，一本鎖 DNA 間の結合性の尺度として自由エネルギーを用いて，DNA タイルの構成要素となる複数の一本鎖 DNA 間の結合安定度を予測し，望みの相補結合はより安定に，望まない相補結合はより不安定になるような塩基配列の設計手法の開発を行った．提案した手法を Yan らによって提案された 4×4 タイルに適用して，Yan らの設計した DNA タイルとの安定性について議論した．提案した評価尺度が実際に安定性の尺度として適切であるかの化学実験的検証が必要ではあるが，従来の塩基配列設計手法と比較して，容易により安定なDNA タイルを設計できる可能性があることを示した．

I１: 一本鎖DNAが最も安定な二次構造をとるときのΔGA
GA
ACA
GTC
GT C
T G

低いTT

ΔＧCGCGAAAAT GCG

I１の値が大きいほど良い

高い

I2: タイル形成に不必要な結合が起こるときのΔGＡＧＴＡＡＴＴＣＧＣ

Ａ ＴＴ
ＡＧＴＡ ＣＧＣ
ＴＣＡＧＣ ＴＧＣＧ

低い

ＴＣＡＧＣＴＧＣＧ

ΔＧ高い

会合してはならない一本鎖ＤＮＡ同士

I２の値が大きいほど良い

I3: タイル形成に必要な結合が起こるときのΔGの絶対値
Ａ ＴＴ
ＡＧＴＡ ＣＧＣ
ＴＣＡＧＣ ＴＧＣＧ

低い

図３

ＡＧＴＡＡＴＴＣＧＣ
TCATTAAGCG

ΔG高い

会合しなければならない
一本鎖ＤＮＡ同士
I3の値が大きいほど良い

DNA タイルの安定性評価のための評価項目

(4) DNA リレーショナルデータベースの実現とデータ検索
DNA計算を利用した応用については様々なものがある．DNAタイルを用いた計算やナノテクノロジーへの応用と並んで，DNAをメモリとして利用しようという試みもなされている．
その中で，ゲノム情報などのウェットな情報をDNAの形としてそのまま保存できるようなデータベースの構築を目指す研究も行われている．DNAの形で保存して，必要な際には，データ検索を実行してそのままウェットな実験を行うことも可能であり，また，容易にコピーができないことやデータの読み取りが容易でないことからセキュリティの高いデータベースとして注目されている．本研究では，DNAを用いたリレーショナルデータベース実現とデータの内容に基づいた検索操作の実行について検証を行った．
データベースの各データ要素に対して，一種類の一本鎖DNAを対応させるモデルを提案し，基本となる5種類の関係演算の実行が可能であることを実験的に示した．また，データの内容に基づくクエリの実現方法を提案し，実際に3つのタプル(レコード)から検索条件にマッチする一つのタプルを取り出す実験に成功した．
また，任意のクエリを実験操作列に変換するアルゴリズムを提案し，その出力結果をもとに計算時間の見積もりやエラーの見積もりを行う方法を提案した．

初期溶液：1分子の長さ48塩基

A1A2A3namegenderdiagnosis

t1t2A

male

positivet1t2t3B

femalenegative

DCM

t3C

male

negative

RSQL
SELECT *FROM patient
WHERE gender = ‘male’AND diagnosis = ‘negative’

name gender

図４

F1 := CollectID( S1 ), F2 := CollectID( S 2 )Converter

Divide(U , U 3 )S 3 := Amplify (U 3 , FW , F1 )S 4 := Amplify ( S 3 , FW , F2 )U ':= Separate+ ( S 4 )

導出結果

導出表
CDivide(U , U 1 , U 2 )S1 := Get (U 1 ,+ s male ), S 2 := Get (U 2 ,+ s negative )malediagnosis
negativet3

DNA リレーショナルデータベースにおけるクエリーの実現【研究発表等】[1] Satoshi Kashiwamura, Masahito Yamamoto, Atsushi Kameda, and Azuma Ohuchi：“Experimental
Challenge of Scaled-up Hierarchical DNA Memory Expressing 10,000-Address Space”，Proceedingsof The 11th International Meeting on DNA Computing，pp.396 (2005)[2] Fumiaki Tanaka, Atsushi Kameda, Masahito Yamamoto, and Azuma Ohuchi: “Specificity ofHybridization between DNA Sequences Based on Free Energy”，Proceedings of The 11th InternationalMeeting on DNA Computing，pp. 366-375 (2005)

[3] Atsushi Kameda, Masahito Yamamoto, Hiroki Uejima, Masami Hagiya, Kensaku Sakamoto,Azuma Ohuchi: Hairpin-based state machine and conformational addressing: Design and experiment,
Natural Computing, Vol. 4, No. 2, pp. 103-126 (2005)[4] 山本 雅人：”DNA ナノテクノロジー －DNA タイルによる自己組織的ナノ構造制御－”，第4 回情報科学技術フォーラム (FIT2005), イベント企画チュートリアル「分子計算のしくみ」(2005)[5] 北 豊, 柏村 聡, 亀田 充史, 山本 雅人, 大内 東：“DNA 分子を利用したリレーショナルデータベースの開発”, 第 4 回情報科学技術フォーラム (FIT2005), A-010, pp. 21-23 (2005)[6] 飯村 直記，山本 雅人，田中 文昭，亀田 充史，大内 東："自由エネルギーを用いた DNA
ナノ構造形成のための塩基配列設計", 第４回情報科学技術フォーラム (FIT2005), 講演論文
集, H-031, pp. 371-373 (2005)[7] 田中 文昭，亀田 充史，山本 雅人，大内 東：“自由エネルギーに基づいた塩基配列設計に関する研究”，第４回情報科学技術フォーラム (FIT2005), H-032, pp. 375-377 (2005)[8] 柏村 聡，山本 雅人，亀田 充史，大内 東：“DNA を記憶素子として用いた分子メモリの開発と大容量化に関する検討”，第４回情報科学技術フォーラム (FIT2005), H-030, pp. 367-359(2005)[9] 飯村 直記，山本 雅人，田中 文昭，亀田 充史，大内 東： “DNA タイル構造の安定性評
価法”，北海道情報処理シンポジウム, 講演論文集 pp. 126-127 (2005)[10] 山本 雅人，飯村 直記，田中 文昭，亀田 充史，大内 東：”DNA タイルによる計算論的ナノテクノロジー”，第 28 回日本分子生物学会年会，シンポジウム「ナノバイオテクノロジー・分析から構築の科学へ」(2005)[11] Naoki Iimura, Masahito Yamamoto, Fumiaki Tanaka, Atsushi Kameda, Azuma Ohuchi: "Stabilityevaluation method of DNA tile structure", Proceedings of The 11th International Symposium onArtificial Life and Robotics (AROB 11th '06), CD-ROM GS18-2, Beppu, Japan (2006)[12] Yutaka Kita, Satoshi Kashiwamura, Atsushi Kameda, Masahito Yamamoto, Azuma Ohuchi: “DataManipulation of DNA Relational Database”, Proceedings of the The Eleventh InternationalSymposium on Artificial Life and Robotics (AROB 11th ‘06), pp. 629-632 (2006)