カオスダイナミクスに基づく組み合わせ最適化技法を用いた配列モチーフ解析

使用基于混沌动力学的组合优化技术进行序列基序分析

• 批准号: 15014101
• 负责人: 池口 徹
• 金额: $ 3.9万
• 依托单位: Saitama University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-15014101/
• 关键词: カオス; ニューラルネットワーク; 組み合わせ最適化; タブーサーチ; モチーフ; DNA; アナログ電子回路; ギプスサンプリング

ゲノム情報解析技術の急速な発展により,生命を記述する膨大な量の遺伝情報が解読されつつある.どのような情報が遺伝子のどの位置に埋め込まれているかを解析する技術の開発が急務である.この中でも特に,DNAからのモチーフ抽出は,蛋白質の機能・構造の推定に関する知見を与える重要課題である.本研究は,研究代表者らが既にその有効性生を十分に示してきたカオスダイナミクスを用いた組み合わせ最適化技法を用いて,モチーフ抽出問題に関する効果的な解法を実現する.その際,提案アルゴリズムを配列モチーフ解析問題に適した形に改良し,それをハードウェアとして実装することにより,大量の配列モチーフ解析を高速実行できる解析装置のコア部分の開発に繋げることが眼目である.本年度は,公募班として一年目であるため,以下の課題を中心に検討した.1.ギプスサンプラの改良による抽出技法の開発モチーフ抽出の従来技法の一つにギプスサンプリング法がある.この手法は,対象となる塩基配列中のモチーフ候補群から推定される尤度に比例した確率分布により,モチーフ候補を更新する手法であり,従来技法の中でも最も強力な手法の一つであるとされている.提案技法では,推定された尤度に基づいて決定論的に抽出を行うが,その際に生じる局所最適解への収束という問題を,タブーサーチ法の導入により解決を図るものである.大量の数値実験に基づく解析の結果,ギプスサンプリング法を充分に凌駕する手法であることが分かった.2.新しいタブーサーチアルゴリズムによる抽出技法の開発モチーフ抽出問題にタブー・サーチ法を適用する場合に,探索過程において不要な振動が発生することがある.そこで,探索履歴をタブーとする時間を強制的に遅延させることによる探索過程の多様化を実現する新しいタブーサーチ法を提案した.大量の数値実験に基づく解析の結果,ワーストケースにおいても従来の単純なタブーサーチ法の性能を充分に上回る性能を有することが示された.

随着基因组信息分析技术的快速发展，大量描述生命的遗传信息正在被解密。迫切需要开发技术来分析哪种信息嵌入基因中。其中，从DNA中提取基序是一个重要的问题，可以深入了解蛋白质功能和结构的估计。这项研究使用了使用混沌动力学的组合优化技术，该技术已经被充分证明，并且能够开发基序提取问题。目的是实现一个有效的解决方案。在这种情况下，提出的算法是将提出的算法改进适合序列基序分析问题的形状并将其作为硬件实施，从而导致分析设备的核心部分的发展，该分析设备可以高速执行大量序列基序分析。今年，我们是公共招聘小组的第一年，因此我们专注于以下问题1。通过改进铸造者开发提取技术是提取基序的常规技术之一。 This method is targeted at This method is used to update motif candidates by a probability distribution proportional to the likelihood estimated from the group of motif candidates in the base sequence, and is said to be one of the most powerful techniques among conventional techniques.The proposed technique is deterministically extracted based on the estimated likelihood, and the problem of convergence to the local optimal solution that occurs during this process is solved by introducing a禁忌搜索方法。作为基于大量数值实验的分析的结果，已经发现，通过铸造采样可以很好地超越该方法。 2。使用新禁忌搜索算法的开发提取技术在应用禁忌搜索方法提取图案时，在搜索过程中可能会发生不必要的振动。因此，我们提出了一种新的禁忌搜索方法，该方法通过强行延迟搜索历史记录禁忌的时间来实现搜索过程的多样化。基于大量数值实验的分析表明，即使在最坏的情况下，也可以实现超过常规简单禁忌搜索方法的性能的性能。

项目成果

エウィン・マルダナ: "カオスニユーラルネットワークによるNP困難問題解決法のオブジェクト指向プログラミング開発"日本神経回路学会第13回全国大会講演論文集. 228-229 (2003)

Ewin Maldana：“使用混沌神经网络解决 NP 难题的面向对象编程的开发”日本神经网络学会第 13 届全国会议论文集 228-229 (2003)。

E.Marhdana: "An Integral Tabu Search for finding DNA Motifs"Proceedings of the 2004 RISP International Symposium on Nonlinear Circuits and Signal Processing. 323-326 (2004)

E.Marhdana：“寻找 DNA 基序的整体禁忌搜索”2004 年 RISP 国际非线性电路和信号处理研讨会论文集。

上手洋子: "Performance of Chaos Noise Injected to Hopfield NN for Associative Memory"平成15年度電気関係学会四国支部連合大会講演論文集. 17-8. (2003)

Yoko Kami：“为联想记忆注入 Hopfield NN 的混沌噪声的性能”电气工程学会 2003 年四国分会会议记录（2003 年）。

佐藤慶一: "組み合わせ最適化問題のニューラル解法に関する理論的考察"電子情報通信学会技術研究報告. 103(136). 31-36 (2003)

Keiichi Sato：“组合优化问题的神经解决方案的理论考虑”IEICE 技术报告 103(136)。

E.Mardhana: "NEUROSEARCH : A Program Library for Neural Network Driven Search Meta-Heuristics"Proceedings of the 2003 IEEE International Symposium on Circuits and Systems. 5. 697-700 (2003)

E.Mardhana：“NEUROSEARCH：神经网络驱动搜索元启发式程序库”2003 年 IEEE 国际电路与系统研讨会论文集。