パス頻度の上下限制約を満たす木状化合物の二段階列挙法

• Item type: SIG Technical Reports(1)
• 公開日: 2012-03-21
• タイトル: パス頻度の上下限制約を満たす木状化合物の二段階列挙法
• タイトル / 言語: en
• タイトル: A 2-Phase Algorithm for Enumerating Tree-like Chemical Graphs Satisfying Given Upper and Lower Bounds
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学
• 著者所属: 京都大学
• 著者所属: 京都大学
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者名: 鈴木, 政喜; 永持, 仁; 阿久津, 達也
• 著者名(英): Masaki, Suzuki; Hiroshi, Nagamochi; Tatsuya, Akutsu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 分子構造の部分情報が与えられたとき，それに基づく化合物の推定問題は生物情報学において重要な課題の一つであり，薬剤設計などの多くの分野に応用することが期待される．本研究では，部分的な分子構造として，長さが与えられた整数K ≧ 0以下である部分パスを取扱い，このような部分パスに関する特徴ベクトルの上限と下限が与えられたときに，この上下限制約の範囲内の特徴ベクトルに一致する木状の化合物を全て列挙する問題を考える．ここで特徴ベクトルは，化合物における原子のパスの出現頻度を表す特徴量により定める．これまで一本の特徴ベクトルに一致する木状化合物を列挙する問題に対しては，すでに石田ら(2008)，(2010)によって高速な分枝限定法アルゴリズムとして一段階法，二段階法が提案されている．さらに，清水ら(2010)は，このうち一段階法アルゴリズムを基に，上下限制約を持つ木状化合物列挙問題を解く分枝限定法を用いた厳密アルゴリズムを実現した．本研究では，上下限制約を持つ木状化合物列挙問題に対する二段階法アルゴリズムを提案する．この提案するアルゴリズムは，分枝操作として中野と宇野(2003)によるラベル付き木の列挙アルゴリズムを用いる．限定操作としては，特徴ベクトルに上限と下限が与えられているため，石田ら(2010)による二段階法の限定操作をそのまま用いることはできないので，上下限制約にも対応できる新たなアルゴリズムを提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Enumeration of chemical graphs satisfying given constraints is one of the fundamental problems in chemoinfomatics since they lead to a variety of useful applications including drug design. In this extended abstract, we consider the problem of enumerating all tree-like chemical graphs from a given set of feature vectors, which is specified by a pair of upper and lower feature vectors, where a feature vector represents the frequency of prescribed paths in a chemical conpound to be constructed. To solve the problem for a single feature vectors, Ishida et al. proposed 1-Phase Algorithm and 2-Phase Algorithm. The problem for a given set can be solved by applying the algorithms proposed by Ishida et al. to each single feature vector in the given set, but this method may take a large amount of computation time because in general there are many feature vectors in a given set. Therefore Shimizu et al. proposed a new exact branch-and-bound algorithm based on 1-Phase Algorithm for the problem so that all the feature vectors in a given set are handled directly. We propose a new exact branch-and bound algorithm based on 2-Phase Algorithm for the problem. In our algorithm, the branching operation is based on Nakano and Uno's enumeration algorithm on labeled trees. Since we cannot use the bounding operation proposed Ishida et al. due to the new upper and lower constraints, we introduce new bounding operations based on upper and lower feature vectors, a bond constraint, and a detachment condition.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12055912
• 書誌情報: 研究報告バイオ情報学（BIO）; 巻 2012-BIO-28, 号 17, p. 1-8, 発行日 2012-03-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会