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

概要

論文の詳細を見る
分子構造の部分情報が与えられたとき,それに基づく化合物の推定問題は生物情報学において重要な課題の一つであり,薬剤設計などの多くの分野に応用することが期待される.本研究では,部分的な分子構造として,長さが与えられた整数K ≧ 0以下である部分パスを取扱い,このような部分パスに関する特徴ベクトルの上限と下限が与えられたときに,この上下限制約の範囲内の特徴ベクトルに一致する木状の化合物を全て列挙する問題を考える.ここで特徴ベクトルは,化合物における原子のパスの出現頻度を表す特徴量により定める.これまで一本の特徴ベクトルに一致する木状化合物を列挙する問題に対しては,すでに石田ら(2008),(2010)によって高速な分枝限定法アルゴリズムとして一段階法,二段階法が提案されている.さらに,清水ら(2010)は,このうち一段階法アルゴリズムを基に,上下限制約を持つ木状化合物列挙問題を解く分枝限定法を用いた厳密アルゴリズムを実現した.本研究では,上下限制約を持つ木状化合物列挙問題に対する二段階法アルゴリズムを提案する.この提案するアルゴリズムは,分枝操作として中野と宇野(2003)によるラベル付き木の列挙アルゴリズムを用いる.限定操作としては,特徴ベクトルに上限と下限が与えられているため,石田ら(2010)による二段階法の限定操作をそのまま用いることはできないので,上下限制約にも対応できる新たなアルゴリズムを提案する.
2012-03-21

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

スポンサーリンク

概要

著者

関連論文

スポンサーリンク