著者

遠里 由佳子 松田 秀雄 橋本 昭洋

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)

巻号頁・発行日

vol.1999, no.76, pp.41-44, 1999-09-21

---

正例として与えられた文字列集合からそれらの特徴を表す極小でかつ既約なパターンの組を求める問題をMINL問題と呼び,パターンの組の数を予め制限することにより,この問題を解く多項式時間アルゴリズムが知られている.同じ機能を持つ遺伝子を同じ文字で表すと,このアルゴリズムは遺伝子クラスタの機能分類に応用できるが,遺伝子の機能は階層的に分類されているため,どの階層の機能分類を使うか指定しないとこのアルゴリズムを適用することができない.そこで,本研究では,パターン間に概念階層を導入し,情報量というパターンの評価基準を使ってMINL問題を近似的に解く多項式時間アルゴリズムを提案し,実際に遺伝子クラスタの機能分類に適用した結果をもとに性能評価を行う.The MINL problem is a problem that finds a minimum and reduced set of patterns explaining a given set of positive example strings. By restricting the number of patterns to be a fixed constant in advance, a polynomial time algorithm that solves this problem is known. This algorithm is applicable to determining gene clusters based on functional classification if genes having the same function are expressed with the same character. However, since gene function is typically classified hierarchically, the above algorithm can only be applied on a single level of the classification hierarchy. In this paper, we extend the MINL problem to cover hierarchical classifications, and propose a novel polynomial time algorithm utilizing entropy to solve the extended problem. In an experiment, we applied our method to gene cluster analysis of actual gene data.