分子計算の解析と設計支援

背景

分子計算という分野は、情報科学をはじめとする理論的な分野から生命科学の 実験の分野までの広い領域を総合的に融合してはじめて可能になる分野である。

分子計算においては、いかに優れた理論やアルゴリズムを考案しても、実際に 試験管内や装置を用いての実現が出来なければ、その価値は小さくならざるを 得ない面がある。また、いかに優れた実験技術があっても、これをいかに 分子計算に用いるかが明確でなければ、宝の持ち腐れになってしまうという面も ある。分子計算にとっては、これらの領域を有機的に結びつけて新しいものを つくり出すことが重要な課題のひとつとなっている。

このような既存領域の境界を結びつけるために必要なことは、分子計算アルゴ リズムの実現性を検証することやアルゴリズムを実現するための塩基配列を 設計すること、必要な実験操作の組合せで予定している分子の反応が効率的に 可能かどうかを検証することなどが挙げられる。このような作業を支援する 環境の構築も含めて、様々な角度からの研究が必要である。

萩谷、西川、有田、Roseらは、分子計算のアルゴリズムや反応系の設計を支援 することを目標に、分子計算のシミュレーション、分子計算の計算量の解析、 分子計算の反応系の解析、分子計算のための配列設計に関する研究を行って来 た。特に、VNA(Virtual Nucleic Acid)と呼ぶ、DNA計算のシミュレータを開発 した。また、DNA計算のために必要な配列の設計方法に関する研究も活発に行 った。

シミュレーション

DNA計算で新しいアルゴリズムを開発した際、コストの大きい生物学実験を即 座に行なわず、期待する分子反応の実現可能性をシミュレーションを用いて予 測できれば、無駄な労力や時間を費やさずに済む。西川、萩谷らは、DNA配列の情報を入力すると、DNA計 算の反応過程を定量的にシミュレートするソフトウェア、VNA (virtual nucleic acids) をJava言語で作成した [西川00数理科学, Nishikawa99GECCO, Nishikawa99CEC]。

DNA計算のシミュレーションをするにあたり、DNAを一塩基単位でモデルする必 然性はない。実際のDNA計算に用いられる塩基配列も15塩基や20塩基程度を１つの 語(word)として、これを基本とする形になっていることが多い。それゆえ、 DNA計算に必要十分な性質を表現できる細粒度であれば、いくつ かの塩基を一単位として抽象化したレベルで記述したほうが、解析の効率、お よび見通しがよくなる。VNAでは、表1に示した仮想塩基と呼ば れる抽象単位を導入している。

表1: 実在の塩基と仮想塩基の比較

比較項目	実在DNAの塩基	仮想塩基
hybridization	あり	あり
DNA鎖の向き	あり	あり
濃度	あり	あり
反応の種類	あり	６種類だけ
配列の長さ	あり	なし（全て同じと仮定）
GCの割合	あり	なし（全て同じと仮定）
立体構造	あり	一部あり（大きさを無視）
2重鎖が離れる温度	あり	予測できず

図1: VNAによるOgiharaとRayのアルゴリズムのシミュレーション

VNAは、この仮想塩基が化学量論的に濃度変化を起こすことでDNA計算をシミュ レートする。初期状態として存在する仮想塩基配列の濃度と、化学反応の平衡 定数を入力すると、生成される種々の分子濃度が時間経過に沿ってグラフィカ ルに表示される(図\ref{fig:VNA})。モデルする化学反応は以下の6操作である。 (1) Hybridization: 相補的な二本鎖の形成、 (2) Self-hybridization: 自分 自身と相補的な二本鎖を形成、(3) Denaturation: 一本鎖への乖離 （Hybridizationの逆反応）、(4) Restriction: 二本鎖での特定の配列部分を 切断、 (5) Extension: 部分的な二本鎖形成部分をもとに、一本鎖より二本鎖 の形成、 (6) Ligation: 二本鎖どうしの結合。

VNAを用いると、与えられたDNA計算のアルゴリズムで望んだ分子種が期待通り 生成されるかどうか定量的に検証できる。DNA計算の分野におけるいくつかの 代表的な計算モデルをシミュレートしたところ、以下の結果が得られた [西川00数理科学, Nishikawa99GECCO, Nishikawa99CEC]。

• Ogihara, Rayの提案したブール回路のアルゴリズムは、本来、メチル化 を巧みに用いたアルゴリズムであるが、メチル化を使わなくてもある程度の効 率で実行可能なアルゴリズムであることが、シミュレート出来た。 （元のアルゴリズムで想定した演算結果は4番目に多い分子であった。） これにより、多段階の論理回路のような反応中間体の種類の少ないアルゴリズ ムは比較的容易にシミュレート出来ることがわかった。
• Hagiyaらが提案したWhiplash PCRの反応は、7段階目の遷移まで反応で きる分子数が非常に少なくなる。よって、遷移ステップを増やすためには反応 条件や反応機構に何らかの工夫が必要となる。この結果は実際の実験結果や、 後に述べるRoseらの解析ともほぼ一致する。
• WinfreeによるDNAタイルは、DNAが重合する過程で組合せ的に 非常に多種類の反応中間体のパターンが出現するため、分子種の量で閾値を 設けるVNAのやりかたではシミュレーションができない。しかしながら、確率的な アプローチでは、ある程度のシミュレーションが可能であることも同時にわか った。DNAタイルのような非常に多種類の反応中間体が生成する複雑な問題に 対処する場合は、シミュレーション技法や抽象のレベル等についてさらなる 検討が必要と考えられる。

反応解析

分子の持つ計算能力の解析という観点からは、化学反応の精密な解析が重要で ある。分子計算において、化学反応は二つの側面から解析される。一つは生成 量(yield)であり、もう一つはエラーである。例えば、アニーリング反応の場 合、期待される二重鎖の量と、期待されない二重鎖の量がこれらに対応する。

化学反応は平衡状態に至るので、生成量を多くするためには生成物が多くなる ような平衡状態を設定しなければならない。これは平衡定数に依存する。さら に、平衡状態に到達する時間を短くしなければならない。これは反応定数に依 存する。いくら平衡定数が大きくても、反応定数が小さいと計算にかかる時間 が大きくなってしまう。分子アルゴリズムの正しい計算量を見積もるにはこの バランスを考慮せねばならない。

確率的アルゴリズムとしてのDNA計算

萩谷らはヘアピン形成に必要な時間などを考慮に入れて、SATエンジンを確率 アルゴリズムとして解析した[萩谷00MPS]。ヘアピンが形成される確率は、n をヘアピンのループ長とすると 1/n^1.5 に比例する。これから、ヘアピン を形成すべき分子がヘアピンを形成できない確率を ε 以下に押えるた めには n^1.5 log(1/ε) 以上の反応時間が必要なことがわかった。 またSATエンジンにおいて正解をコードする分子が生成されない確率を ε 以下に押えるには、組合せの解析から (3+α)ⁿ log(1/ε) （α は任意の正数）以上の分子数が必要なことがわ かった。これらの結果を用いて萩谷らは、O(3ⁿ) の分子を用いた時でもルー プを形成しない分子の個数を ε 以下に防ぐには、O(n^2.5) の反応 時間で十分であることを明らかにした。

計算機科学における確率アルゴリズムで3SAT問題を解くには現在最速なもので も O(1.334ⁿ log(1/ε)) 計算時間かかる。これに対しDNA計算では、必 要な分子数は問題サイズに対し指数的に増えるものの、反応時間は多項式時間 で押えられており、意義のある結果が得られている。ただし、この解析にはエ ラーが試算されていないため、エラーを含めた解析が今後の課題となっている。

熱力学的解析

DNA計算におけるエラーの大きな原因はアニーリングのエラー(予期しない部位 でのアニーリング)である。これを避けるためには、温度や塩濃度などの反応 条件の調整と、よい配列の設計が必要である。Roseは、熱力学的な解析によっ てアニーリングのエラーの評価を行った。その結果として、computational incoherencyという尺度を定義した。これはエラーの可能性を数値化したもの である。Roseは、computational incoherencyに基づいた配列の評価方法を提 案し、実際にその評価方法に従って配列設計を行っている[Rose00MPS]。

RoseはまたWhiplash PCRの挙動を熱力学的に解析している[Rose00MPS]。 Whiplash PCRの反 応は、バックハイブリダイゼーションと呼ばれる過去の遷移ステップに対応す るヘアピンを再形成しやすい欠点を持つ。Roseは、配列長や温度、酵素との反 応を考慮した熱力学的解析により、遷移を重ねるたびにバックハイブリダイゼー ションの形成確率が増え、正しい遷移を行なう分子が指数的に減少することを 明らかにした。そして解析結果に基づいたシミュレーションを行ない、5段階 の遷移後には反応できる分子数が十分に小さくなることを予測し、初期に行な われた実験結果とも結果がほぼ一致することを示した。この解析以降、初期の 実験で使われていた条件設定（特に温度）の改善がなされ、現在は8段階の遷 移が実験的には可能になっている。また、RoseのシミュレーションではPNAを 併用したWhiplash PCRの解析もなされた。この場合、DNAのみを用いた遷移よ りもはるかに効率が上がり、20段階以上の遷移が可能であると示されている。 現在、この理論的解析を実証すべくPNAを用いた実験を計画中である。

配列設計

DNA計算において、配列設計は実験の成否を左右する重要な問題である。意図 したDNA計算を行うには、実験に用いる配列が予期しない部位でアニールした り、予期しない二次構造を形成しては困る。DNA計算では、計算方式毎に異な る符号化や酵素を用いるため、様々な制約を満たす配列が必要となる。

このため有田らは汎用の配列設計ツールを作成した[Arita00GECCO]。 配列設計における制約を 大別すると、エラーを防ぐために「必ず」満たすべき制約と、計算効率を上げ るために「なるべく」満たすべき制約に分けられる。作成した配列設計ツール では、前者の制約を

• 使用する制限酵素の認識配列が、予定の箇所以外に現れない、
• 各DNA配列の3'末端の6塩基が、他の配列やその相補配列、また 配列が連結された際のつなぎ目に現れない、

• DNA配列（とその相補配列）どうしの類似度を低くする、
• 全DNA配列のGC含量を揃える、
• 同一塩基の長い繰り返しを作らない、

と定めた。さらにDNA計算のモデルによっては、DNAの4種類の塩基のうち3種し か使わない等の制約が追加される。

配列設計問題とは、使用するDNA配列の本数と長さ、そして制限酵素の認識配 列の位置等あらかじめ決まった塩基配列部分を入力とし、残りの配列未決定部 分を上記の制約を満たすように決定するものである。従来のDNA計算では、上 記のように制約を二種類に分けることがなく、またDNA配列の3'末端のアニー リングも特に考慮されてこなかった。また設計法にも、遺伝的アルゴリズムな どの進化的計算を用いたものと、ランダムに生成した配列から制約をなるべく 満たすものを選択するランダム生成型のものが存在したが、両者の特徴や 優劣の比較はあまり行なわれてこなかった。

有田らは、配列設計における問題点を明確にするために、従来型の進化的計算 を用いた配列設計ツールと、ランダム生成型の配列設計ツールと、二通りに実 現し、それらの性能を比較した。そして以下の結論を導いた[Arita00GECCO]。

• 進化的計算による設計では、各DNA配列に一つの評価値を与えて淘汰を 行なう。しかし複数ある制約の相対的な重要度が容易にわからないため、各制約の違 反度に対するペナルティを決めるのが困難である。また、全体の配列中に不適当な配列 を少数含む場合でも配列全体の評価が良くなってしまう可能性がある。
• ランダム生成型の設計では、効率を上げるための制約に「しきい値」を 設け、その値をクリアするような配列を採用する。しかし、このしきい値の上 限は問題によって異なり、あらかじめ見積もることは難しい。
• 従って、進化的計算を用いて効率化制約のしきい値を見積もる作業を行 ない、見積もった制約を用いてランダム生成による配列設計を行なう手法が配 列設計に最も適した方法である。

上に述べた配列設計の制約には、配列のGC含量を揃えることと同一塩基の繰り 返しを作らないことが含まれている。これらはともに塩基の「ばらつき」を示 す指標である。このばらつきをより理論的に解析するために、西川らは、待ち 行列理論で考案されたm-バランスという無限列に対する指標をDNA配列の設計や解析に 応用することを試みた[西川00MPS]。この指標を用いて、GC含量や塩基の繰り返しの制約を満たすのに実験的に 失敗する配列と、同じ制約を満たし実験にも成功する配列のバランスを比較す る作業を行なった。そして、実験が失敗する配列には、配列の前半部と後半部 とでバランスの不均衡かある事実を発見した。現在、このバランス指標を配列 設計時の制約として用いるため、有田らの作成したツールに組み込む作業を行 なっている。