木構造と化合物のマッチングアルゴリズム
Pattern matching algorithms for trees and chemical compounds

概要

本発表では木構造や化合物の類似性判定を行うための高速なアルゴリズムと、結合則や交換則を許すunification問題やマッチング問題に対する固定パラメータアルゴリズムを紹介する。木構造の編集距離の計算は順序木に対しては多項式時間アルゴリズムが存在するが、無順序木に対しては次数やアルファベットのサイズが固定された時ですらNP困難である。本研究では木のサイズが$n_1$と$n_2$である時に$O(1.26^{n_1+n_2})$時間、さらに次数とアルファベットのサイズが固定された時に$O((1+\epsilon)^{n_1+n_2})$時間で無順序木の編集距離を計算するアルゴリズムを紹介する。また最大重みクリークを用いた実用的な編集距離計算アルゴリズムも紹介する。

産業界への展開例・適用分野

創薬などのプロセスにおいて、未知の化合物の生理活性をネットワーク構造に基づいて予測することは重要である。糖鎖などの化合物は無順序木で表現することが可能であり、また9割以上の化合物が部分k木(k=3)であることが知られている。これらの化合物の類似性を高速に計算することは、実際に人手や薬品を伴う実験のコストを大幅に削減することにつながる。
また結合則や交換則を許すunification問題やマッチング問題は、数式検索などへの応用が期待できる。

研究者

氏名	専攻	研究室	役職/学年
田村 武幸	知能情報学専攻	阿久津	助教

---