An Improved Clique-Based Method for Computing Edit Distance between Rooted Unordered Trees

スポンサーリンク

概要

• 論文の詳細を見る

• Tree structures are suitable for representing biological objects such as RNA secondary structures so that it is important in computational biology to compare tree structures. Though there are various metrics proposed for computing similarity between tree structured data, tree edit distance is one of the most widely used. However, it is known that the tree edit distance problem is NP-hard for unordered trees. Fukagawa et al. have recently proposed a clique-based method for computing the tree edit distance between unordered trees in which each instance of the tree edit distance problem is transformed into an instance of the maximum vertex weighted clique problem and then an existing clique algorithm is applied. In this article, we propose an improved clique-based method for computing the tree edit distance between rooted unordered trees. Different from the previous method, we combine a dynamic programming approach with clique-based approach. Furthermore, we introduce heuristic techniques, which do not violate the optimality of the solution. Applied to comparison of large glycan structures, our improved method is much faster than the previous method in most cases of comparison of large glycan structures.

• 2011-09-06

著者

• 深川 大路

  国立情報学研究所

• 深川 大路

  National Institute of Informatics

• Tatsuya Akutsu

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

• Takeyuki Tamura

  Bioinformatics Center Institute For Chemical Research Kyoto Univerty

• Tatsuya Akutsu

  Bioinformatics Center Institute For Chemical Research Kyoto University

• Tatsuya Akutsu

  Bioinformatics Center Institute For Chemical Research Kyoto Univerty

• Atsuhiro Takasu

  National Institute Of Informatics

• Etsuji Tomita

  University Of Electro-communications

• Tomoya Mori

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

• Daiji Fukagawa

  Faculty of Culture and Information Science, Doshisha University

• Fukagawa Daiji

  Graduate School Of Information Science And Technology The University Of Tokyo

• Daiji Fukagawa

  Faculty Of Culture And Information Science Doshisha University

• 深川 大路

  同志社大学文化情報学部

• Tomoya Mori

  Bioinformatics Center Institute For Chemical Research Kyoto University

• Takeyuki Tamura

  Bioinformatics Center Institute For Chemical Research Kyoto University

関連論文

• 高さの制限された無順序木の編集距離問題に対する近似アルゴリズム
• マージン最大化によるメトリック空間分割手法(一般,「ユビキタス,センサ環境におけるデータベース」,及び一般)
• 学術情報の統合に向けた大規模リンケージ基盤の構築
• 3.アカデミックリンケージ : 膨大な学術情報へのアクセスを支援するリンケージ基盤(パートII:情報分野研究者のためのオンリーワン共有イノベーションプラットフォーム,情報爆発時代におけるわくわくするITの創出を目指して)
• 高さの制限された2個の無順序木に対する最大共通部分木の近似アルゴリズムの改良
• 2J-3 確率モデルに基づく木の類似度のパラメータ学習について(情報爆発時代におけるマルチメディアデータと交通情報システム,一般セッション,「情報爆発」時代に向けた新しいIT基盤技術)
• Statistical learning algorithm for tree similarity (特集「知識発見の諸科学への応用」および一般)
• 木の編集距離の文字列の編集距離による近似
• 特徴ベクトルからの化学構造の推定(Bioinformatics)
• パス頻度ベクトルからのグラフ推定問題の困難性について
• 類似度の高い無順序木の比較に対する高速アルゴリズム
• ブール関数推定のための貪欲アルゴリズムの性能解析
• Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
• Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
• RNA-RNA Interaction Prediction Using Integer Programming with Threshold Cut
• 無順序木の編集距離計算のための厳密アルゴリズム
• A clique-based method for the edit distance between unordered trees (特集 「脳科学と知識処理」および一般)
• A Quadsection Algorithm for Grammar-Based Image Compression
• Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
• パス頻度ベクトルからのグラフ推定問題の困難性について
• D-008 類似検索の高速化を目的としたPivot選択手法の実験評価(D分野:データベース,一般論文)
• 2K-2 索引木の均衡を考慮した類似検索索引手法(情報爆発時代におけるアルゴリズム高率化,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
• 2K-1 高さ制約付き無順序木の高速類似検索アルゴリズムについて(情報爆発時代におけるアルゴリズム高率化,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
• Conditional Random Field Approach to Prediction of Protein-protein Interactions Using Domain Information
• Integer Programming and Dynamic Programming-based Methods of Optimizing Control Policy in Probabilistic Boolean Networks with Hard Constraints
• An Improved Clique-Based Method for Computing Edit Distance between Rooted Unordered Trees
• TCGにおけるシャッフル手法に関する計算機実験を用いた考察
• Prediction of protein residue contacts using discriminative random field
• Prediction of protein residue contacts using discriminative random field
• Margin-Based Pivot Selection for Similarity Search Indexes
• Efficient Computation of Impact Degrees for Multiple Reactions in Metabolic Networks with Cycles
• Prediction of RNA Secondary Structures with Binding Sites Using Dynamic Programming Algorithm
• Optimal Pivot Selection Method Based on the Partition and the Pruning Effect for Metric Space Indexes
• Message from the Editor-in-Chief
• Message from the Editor-in-Chief
• Message from the Editor-in-Chief
• Protein complex prediction via improved verification methods using constrained domain-domain matching
• Predicting Protein-RNA Residue-base Contacts Using Two-dimensional Conditional Random Field
• 無順序木の編集距離の指数時間厳密アルゴリズム
• Finding Conserved Regions in Protein Structures Using Support Vector Machines and Structure Alignment
• Extended Bayesian Model for Multi-criteria Recommender System
• Extended Bayesian Model for Multi-criteria Recommender System
• Inferring Strengths of Protein-Protein Interactions Using Support Vector Regression
• 無順序木の編集距離の指数時間厳密アルゴリズム
• Evaluating Effectiveness of Accessibility to Infer RNA-RNA Interactions
• Survival Analysis by Penalized Regression and Matrix Factorization
• A Dominating Set Approach to Structural Controllability of Unidirectional Bipartite Networks
• Prediction of Heterodimeric Protein Complexes from Weighted Protein-Protein Interaction Networks Using Novel Features and Kernel Functions
• Prediction of Heterodimeric Protein Complexes from Weighted Protein-Protein Interaction Networks Using Novel Features and Kernel Functions
• Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
• Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
• Algorithms for Finding a Largest Common Subtree of Bounded Degree
• Parallelization of Enumerating Tree-like Chemical Compounds by Breadth-first Search Order
• Prediction of Heterotrimeric Protein Complexes by Two-phase Learning Using Neighboring Kernels
• Prediction of Heterotrimeric Protein Complexes by Two-phase Learning Using Neighboring Kernels
• Grammar-based Compression for Multiple Trees Using Integer Programming
• Grammar-based Compression for Multiple Trees Using Integer Programming
• 無順序木の編集距離の指数時間厳密アルゴリズム

もっと見る 閉じる

スポンサーリンク