IEICE TRANSACTIONS on Information
Tree Edit Distance Problems: Algorithms and Applications to Bioinformatics
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E93-D No.2 pp.208-218
- Publication Date
- 2010/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E93.D.208
- Type of Manuscript
- Special Section INVITED PAPER (Special Section on Foundations of Computer Science)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tatsuya AKUTSU, "Tree Edit Distance Problems: Algorithms and Applications to Bioinformatics" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 2, pp. 208-218, February 2010, doi: 10.1587/transinf.E93.D.208.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.208/_p
Copy
@ARTICLE{e93-d_2_208,
author={Tatsuya AKUTSU, },
journal={IEICE TRANSACTIONS on Information},
title={Tree Edit Distance Problems: Algorithms and Applications to Bioinformatics},
year={2010},
volume={E93-D},
number={2},
pages={208-218},
abstract={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.},
keywords={},
doi={10.1587/transinf.E93.D.208},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Tree Edit Distance Problems: Algorithms and Applications to Bioinformatics
T2 - IEICE TRANSACTIONS on Information
SP - 208
EP - 218
AU - Tatsuya AKUTSU
PY - 2010
DO - 10.1587/transinf.E93.D.208
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2010
AB - 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.
ER -
English
