属性の創造と探索によるDNAシグナル配列発見方式の研究

基于属性创建和搜索的DNA信号序列发现方法研究

• 批准号: 13780290
• 负责人: 丸山 修
• 金额: $ 1.34万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13780290/
• 关键词: 属性創造; 探索アルゴリズム; DNAシグナル; 発見方式; 枝刈り; degenerate pattern; yeast; 類似度; 属性探索; view; DNA; シグナル配列; multiple unordered motif; bit operation

本研究の目的は,属性創造と属性空間の探索により,シグナル配列発見問題を解決することである.本年度は,シグナル配列を捉える個々のパターンを属性と捉え,これらの包含関係に着目し,様々なパターンからなる巨大探索空間を効率よく探索する枝刈り探索アルゴリズムを開発・実装した.また,計算機実験による手法の有効性の検証を行った.問題の定式化と計算量:シグナル配列の特徴を表すパターンモデルの一つにIUPAC核酸コード上の文字列があげられる.本研究では,これをdegenerate patternとしてフォーマルに定式化し,与えられた配列データセットに対する最適degenerate patternを見つける計算問題がNP-完全であることを明らかにした.属性空間の探索:degenerate patternが定義する言語の包含関係から得られるパターンの評価値の上限に関する特徴付けを利用したdegenerate patternのための枝刈りアルゴリズムを開発した.計算機実験:開発した手法の有効性を合成データと実データを用いて既存手法との比較実験を行った.実データを用いた実験においては,yeastのデータベースSCPD(the promoter database of Saccharomyces cerevisiae, http://cgsigma.cshl.org/jian/)に登録されている既知のシグナル配列の検出率を基準とした.これにより,多くの既知配列に対して手法の有効性が確認された.また,以上の研究の発展として,これらパターンを基礎の属性とする帰納的仮説モデル(例えば,決定木や論理式など)が与える甚大な探索空間を効率よく探索するための基礎理論を構築する研究にも着手した.そこでは,仮説モデル間の類似度を与えるメジャーを定式化し,代表的な帰納的仮説モデル間の類似度を解析することに成功している.

本研究的目的是通过创建属性和搜索属性空间来解决信号序列发现问题。今年，我们将考虑将信号序列捕获为属性的个体模式，重点关注它们的包含关系，并研究各种剪枝以有效搜索由模式组成的巨大搜索空间我们开发并实现了一种搜索算法。我们还通过计算机实验验证了该方法的有效性。问题表述和计算复杂性：代表信号序列特征的模式模型之一是IUPAC核酸代码上的字符串。研究，我们退化了这个正式地表述为模式，我们发现为给定数组数据集找到最佳简并模式的计算问题是NP完全的。探索属性空间：简并模式可以从使用简并定义的语言的包含关系中获得。模式评估值上限的表征我们开发了一种模式剪枝算法。计算机实验：我们使用合成数据和真实数据进行了对比实验，以比较所开发方法与现有方法的有效性。在使用真实数据的实验中，数据库SCPD（酿酒酵母的启动子数据库） ,以http://cgsigma.cshl.org/jian/中登记的已知信号序列的检出率为标准。这证实了该方法对许多已知序列的有效性，作为上述研究的发展。开发了一种使用这些模式作为基本属性的归纳方法。我们还开始研究构建一种基本理论，用于有效搜索假设模型（例如决策树、逻辑公式等）提供的巨大搜索空间。我们制定了一种衡量假设模型之间相似程度的方法，并成功分析了代表性归纳假设模型之间的相似性。