DNA計算における局所探索法による反応障壁近似計算

• Item type: SIG Technical Reports(1)
• 公開日: 2004-10-15
• タイトル: DNA計算における局所探索法による反応障壁近似計算
• タイトル / 言語: en
• タイトル: A Local Search Algorithm for Barrier Heights Estimation in DNA computing
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州大学大学院システム情報科学府
• 著者所属: 九州大学大学院システム情報科学研究院
• 著者所属: 九州大学大学院システム情報科学研究院
• 著者所属: 九州大学大学院システム情報科学研究院
• 著者所属(英): en
• 著者所属(英): Dept. of Computer Science and Communication Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Dept. of Computer Science and Communication Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Dept. of Computer Science and Communication Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Dept. of Computer Science and Communication Engineering, Kyushu University
• 著者名: 武田, 勉; 小野, 廣隆; 定兼, 邦彦; 山下雅史
• 著者名(英): Tsutomu, Takeda; Hirotaka, Ono; Kunihiko, Sadakane; MasafumiYamashita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: DNA計算はDNA分子の形態変化を計算規則とみなす計算パラダイムであり，望ましい形態変化を行う分子配列の設計（配列設計問題）が様々な角度から研究されている．本研究は配列設計において大きな役割を果たすといわれる．反応エネルギー障壁値を求める問題について考える．エネルギー障壁は，分子反応の（通常は分子長の指数オーダー分存在する）中間形態により定まるものであり，前探索による求解は現時的ではない．本研究では，局所探索法に基づく高速な近似解法を提案する．計算機実験による既存の厳密解法との比較では，多くの配列例で本近似解法により高速に比較的良い解を得られることが確認された．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: DNA computing is a computing paradigm utilizing transitions of DNA molecules as computation. In the context, sequence design problem has been studied to design DNA molecules whose transitions are suitable for computation. In this paper, we consider the problem of estimating the height of the energy barrier that plays an important role in the sequence design. The barrier height depends on intermediate structures in all transition paths. Unfortunately, the number of intermediate structures is exponential of the sequence length, and the exhaustive search is not practical. We propose a fast approximation algorithm based on the local search. Computational experiment shows that our algorithm finds relatively good solutions as the exitsting exact algorithm in short time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2004, 号 101(2004-AL-097), p. 101-106, 発行日 2004-10-15
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会