生体高分子と結合する低分子化合物の効率的な比較、探索、発見アルゴリズムの開発

开发与生物聚合物结合的低分子化合物的有效比较、搜索和发现算法

• 批准号: 15014217
• 负责人: 馬見塚 拓
• 金额: $ 5.12万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-15014217/
• 关键词: アルゴリズム; 機械学習; 生体生命情報学; プロテオーム

比較・探索手法の開発においては、化合物を分子グラフと呼ぶ特殊なグラフとみなし、任意の2つの分子グラフを入力として、それらの最大共通部分グラフを出力する問題に対する効率的な解法を構築した。一般のグラフに対して、この問題を現実的な計算時間(多項式時間)で解決することは困難であり、分子グラフとしての合理的な制約(例えば、グラフの次数(節点から出ている枝の数)は化合物の各原子での結合数に相当し比較的小さな値に制約を置ける)を置いた場合も同様である。そこで、グラフの複雑性の尺度の一つである木幅(tree-width)に着目した。木幅とは、直感的にグラフの木への近さを示す尺度であり、木であれば1、節点数nのグラフの完全グラフ(全結合グラフ)はn-1となる。ただし、単純に木幅の値に制約を置いても、この問題は効率的に解決できない。我々は、入力グラフの一方に木幅と次数両方の制約を置き、もう一方に弱い制約(グラフの全域木の数が多項式)を置くことにより、効率的な多項式時間アルゴリズムを構築した。この問題設定は、我々の知る限り計算機科学一般において今までの最も広いグラフのクラスを扱っており、計算機科学の観点からも重要な成果である。発見手法の開発においては、相互作用可能な化合物のペアを各事例とする大量データを入力とし学習した規則を使用し、未知の相互作用を高精度に発見する手法を確立した。入力化合物の背景知識を潜在知識として利用した確率モデルのパラメータ学習により、化合物ペアのみならず背景知識に対する規則を獲得することを特徴とする。本手法は、共起データ一般の学習・予測問題への新手法であり、識別問題としての実験的な評価から共起データに対する既存の一般手法の多くをはるかに凌駕することがわかった。この結果は生命情報科学のみならず情報科学一般での本手法の新規性・有効性を示唆しており非常に重要な成果である。

Compare and explore the development of methods for the construction of efficient solutions to the problem of molecular weight, and molecular weight of any two compounds. Generally, the calculation time (polynomial time) of the problem is difficult to solve, and the reasonable constraint of the molecular problem (e.g., the number of times of the problem (the number of branches from the node) is the same as the small constraint of the number of bonds of each atom of the compound). The tree-width of the tree is very important. The width of the tree is equal to the width of the tree. The distance between the tree and the tree is equal to the distance between the tree and the tree. The number of nodes is equal to the distance between the tree and the tree. The problem is solved by setting the limit of the pure wood width. I am going to set up a weak constraint (global polynomial) on the one hand and a polynomial time on the other hand. This problem sets the limits of what we know about computer science in general and what we know about computer science in particular. The development of discovery methods is based on the study of a large number of possible interactions between compounds and the establishment of methods for high-precision discovery of unknown interactions. The background knowledge of the compound is potential knowledge, and the accuracy of the background knowledge is used to obtain the characteristics of the compound This method is a new method for identifying and predicting problems in general. The result is a very important achievement for life information science and information science in general.

项目成果

Mamitsuka, H.: "Efficient Unsupervised Mining from Noisy Data Sets : Application to Clustering Co-occurrence Data"Proceedings of the Third SIAM International Conference on Data Mining. 239-243 (2003)

Mamitsuka, H.：“从噪声数据集中进行高效无监督挖掘：共现数据聚类的应用”第三届 SIAM 国际数据挖掘会议论文集。

Yamaguchi, A, Mamitsuka, H.: "Finding the Maximum Common Subgraph of a Partial k-tree and a Graph with a Polynomially Bounded Number of Spanning Trees"Lecture Notes in Computer Science. 2906. 58-67 (2003)

Yamaguchi, A, Mamitsuka, H.：“查找部分 k 树的最大公共子图和具有多项式有界生成树数的图”计算机科学讲义。

Mamitsuka, H.: "Hierarchical Latent Knowledge Analysis for Co-occurrence Data"Proceedings of the Twentieth International Conference on Machine Learning. 504-511 (2003)

Mamitsuka, H.：“共现数据的分层潜在知识分析”第二十届国际机器学习会议论文集。

Mamitsuka, H., Okuno, Y., Yamaguchi, A.: "Mining Biologically Active Patterns in Metabolic Pathways using Microarray Expression Profiles"ACM SIGKDD Explorations. 5. 113-121 (2003)

Mamitsuka, H.、Okuno, Y.、Yamaguchi, A.：“使用微阵列表达谱挖掘代谢途径中的生物活性模式”ACM SIGKDD 探索。

Mamitsuka, H.: "Efficient Mining from Heterogeneous Data Sets for Predicting Protein-Protein Interactions"Proceedings of the Fourteenth International Workshop on Database and Expert Systems. 32-36 (2003)

Mamitsuka, H.：“从异质数据集中有效挖掘以预测蛋白质-蛋白质相互作用”第十四届数据库和专家系统国际研讨会论文集。