表題番号：2011B-056 日付：2012/03/17
研究課題生体分子の言語理論的進化モデルの研究
研究者所属（当時） 資格 氏名
（代表者） 教育・総合科学学術院 教授 横森　貴
（連携研究者） 教育・総合科学学術院 助手 大久保文哉
研究成果概要
申請者らはここ数年来，分子計算の分野において主に形式言語理論による配列集合に対す
る特徴付けを研究してきた．その過程において，与えられた記号列から新たな記号列を生
成する「ヘアピン・コンプレッション」(HC: hairpin completion)という演算（操作）に
注目した．これは核酸配列がヘアピン構造をつくる現象を基本としてモデル化したもので
ある．我々はHC演算を修正した「ヘアピン・インコンプレッション」(HI: hairpin incompletion)
とよぶ新しい演算を定義し，この演算の持つ計算能力を解析した．HIは，実際にIn Vitro
実験において開発されている“ Whiplash PCR(WPCR)”という制御可能な分子反応操作を忠実
にモデル化した演算である．
　本研究では「記号列の集合である形式言語とその言語族がHI演算に対してどのような振る
舞いを示すか」という視点から，以下の結果を得た([1])．
(1) 正則言語との共通集合演算，正則言語との連接演算，および和集合演算に関して閉じて
いる言語族はHI演算に関しても閉じている．
(2) すべての線形言語を含み，環状順列演算，左微分演算，および代入演算に関して閉じて
いる言語族は繰り返しHI演算に関しても閉じている．
これらの知見から，例えば与えられたDNA配列の有限集合がWhiplash PCRのようなメカニズム
によって進化すると考えるとき，その進化結果は正則言語の範囲内である，と結論つけられる．

　一方，本研究では分子反応系を基本とした計算モデルの研究にも着手し，反応オートマトン
(RA: Reaction Automata)とよぶ計算モデルを導入し，その計算能力を解析した．RAは化学反応
系をモデル化した記号列受理器であり，（従来型のオートマトンと異なり）試験管内や細胞内
の環境を想定した“多重集合(multiset)”を扱う計算モデルという特徴がある．得られた結果
は以下の通りである([2],[3])．
(i) RAはチューリング機械と等価な万能計算能力を有する．
(ii)空間的に制限されたRAに関しては，線形的限定RAは文脈自由言語族と比較不可能な言語族
を形成し，指数的限定RAの計算能力は文脈依存言語族と一致する．
これらの結果は，化学反応による計算/情報処理能力を解明する新しい知見を与える．