Tree Edit Distance Problems: Algorithms and Applications to Bioinformatics
スポンサーリンク
概要
- 論文の詳細を見る
Tree structured data often appear in bioinformatics. For example, glycans, RNA secondary structures and phylogenetic trees usually have tree structures. Comparison of trees is one of fundamental tasks in analysis of these data. Various distance measures have been proposed and utilized for comparison of trees, among which extensive studies have been done on tree edit distance. In this paper, we review key results and our recent results on the tree edit distance problem and related problems. In particular, we review polynomial time exact algorithms and more efficient approximation algorithms for the edit distance problem for ordered trees, and approximation algorithms for the largest common sub-tree problem for unordered trees. We also review applications of tree edit distance and its variants to bioinformatics with focusing on comparison of glycan structures.
- （社）電子情報通信学会の論文
- 2010-02-01
著者
-
Akutsu Tatsuya
Bioinformatics Center, Institute for Chemical Research, Kyoto University
-
Akutsu Tatsuya
Bioinformatics Center Institute For Chemical Research Kyoto University
-
Akutsu Tatsuya
Bioinformatics Center Inst. For Chemical Res. Kyoto Univ.
関連論文
- Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
- Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
- On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
- Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences(Discrete Mathematics and Its Applications)
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Dynamic Programming and Clique Based Approaches for Protein Threading with Profiles and Constraints(Discrete Mathematics and Its Applications)
- Hardness Results on Local Multiple Alignment of Biological Sequences
- 1P-279 酸化ストレス下におけるアポトーシス制御機構の数理的解明(放射線生物/活性酸素,第46回日本生物物理学会年会)
- Detecting a Singleton Attractor in a Boolean Network Utilizing SAT Algorithms
- Exact Algorithms for Finding a Minimum Reaction Cut under a Boolean Model of Metabolic Networks
- On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
- Tree Edit Distance Problems: Algorithms and Applications to Bioinformatics
- Message from the Editor-in-Chief
- Message from the Editor-in-Chief
- Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Message from the Editor-in-Chief
- Message from the Editor-in-Chief
- Hardness Results on Local Multiple Alignment of Biological Sequences
- Kernel Methods for Chemical Compounds: From Classification to Design
- Conservation Laws and Symmetries in Competitive Systems
- Measuring the Similarity of Protein Structures Using Image Compression Algorithms
- An Efficient Method of Computing Impact Degrees for Multiple Reactions in Metabolic Networks with Cycles
- Conservation Laws and Symmetries in Competitive Systems
- Integer Programming-Based Approach to Attractor Detection and Control of Boolean Networks
- On the Complexity of Inference and Completion of Boolean Networks from Given Singleton Attractors