A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees

Kiyoko F. Aoki-Kinoshita, Minoru Kanehisa, Ming-Yang Kao, Xiang Yang Li, Weizhao Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

A node-labeled rooted tree T (with root r) is an all-or-nothing subtree (called AoN-subtree) of a node-labeled rooted tree T′ if (1) T is a subtree of the tree rooted at some node u (with the same label as r) of T′, (2) for each internal node v of T, all the neighbors of v in T′ are the neighbors of v in T. Tree T′ is then called an AoN-supertree of T. Given a set of n node-labeled rooted trees, smallest common AoN-supertree problem seeks the smallest possible node-labeled rooted tree (denoted as ) such that every tree Ti in is an AoN-subtree of . It generalizes the smallest superstring problem and it has applications in glycobiology. We present a polynomial-time greedy algorithm with approximation ratio 6.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings
Pages100-110
Number of pages11
DOIs
StatePublished - Dec 1 2006
Event17th International Symposium on Algorithms and Computation, ISAAC 2006 - Kolkata, India
Duration: Dec 18 2006Dec 20 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4288 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other17th International Symposium on Algorithms and Computation, ISAAC 2006
CountryIndia
CityKolkata
Period12/18/0612/20/06

Fingerprint

Approximation algorithms
Rooted Trees
Labels
Approximation Algorithms
Labeled Trees
Polynomials
Computing
Vertex of a graph
Superstring
Greedy Algorithm
Polynomial-time Algorithm
Glycomics
Roots
Internal
Generalise
Approximation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Aoki-Kinoshita, K. F., Kanehisa, M., Kao, M-Y., Li, X. Y., & Wang, W. (2006). A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees. In Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings (pp. 100-110). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4288 LNCS). https://doi.org/10.1007/11940128_12
Aoki-Kinoshita, Kiyoko F. ; Kanehisa, Minoru ; Kao, Ming-Yang ; Li, Xiang Yang ; Wang, Weizhao. / A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees. Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. pp. 100-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{7c1034cf0b7348529f8adadfd818f97c,
title = "A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees",
abstract = "A node-labeled rooted tree T (with root r) is an all-or-nothing subtree (called AoN-subtree) of a node-labeled rooted tree T′ if (1) T is a subtree of the tree rooted at some node u (with the same label as r) of T′, (2) for each internal node v of T, all the neighbors of v in T′ are the neighbors of v in T. Tree T′ is then called an AoN-supertree of T. Given a set of n node-labeled rooted trees, smallest common AoN-supertree problem seeks the smallest possible node-labeled rooted tree (denoted as ) such that every tree Ti in is an AoN-subtree of . It generalizes the smallest superstring problem and it has applications in glycobiology. We present a polynomial-time greedy algorithm with approximation ratio 6.",
author = "Aoki-Kinoshita, {Kiyoko F.} and Minoru Kanehisa and Ming-Yang Kao and Li, {Xiang Yang} and Weizhao Wang",
year = "2006",
month = "12",
day = "1",
doi = "10.1007/11940128_12",
language = "English (US)",
isbn = "3540496947",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "100--110",
booktitle = "Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings",

}

Aoki-Kinoshita, KF, Kanehisa, M, Kao, M-Y, Li, XY & Wang, W 2006, A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees. in Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4288 LNCS, pp. 100-110, 17th International Symposium on Algorithms and Computation, ISAAC 2006, Kolkata, India, 12/18/06. https://doi.org/10.1007/11940128_12

A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees. / Aoki-Kinoshita, Kiyoko F.; Kanehisa, Minoru; Kao, Ming-Yang; Li, Xiang Yang; Wang, Weizhao.

Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. p. 100-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4288 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees

AU - Aoki-Kinoshita, Kiyoko F.

AU - Kanehisa, Minoru

AU - Kao, Ming-Yang

AU - Li, Xiang Yang

AU - Wang, Weizhao

PY - 2006/12/1

Y1 - 2006/12/1

N2 - A node-labeled rooted tree T (with root r) is an all-or-nothing subtree (called AoN-subtree) of a node-labeled rooted tree T′ if (1) T is a subtree of the tree rooted at some node u (with the same label as r) of T′, (2) for each internal node v of T, all the neighbors of v in T′ are the neighbors of v in T. Tree T′ is then called an AoN-supertree of T. Given a set of n node-labeled rooted trees, smallest common AoN-supertree problem seeks the smallest possible node-labeled rooted tree (denoted as ) such that every tree Ti in is an AoN-subtree of . It generalizes the smallest superstring problem and it has applications in glycobiology. We present a polynomial-time greedy algorithm with approximation ratio 6.

AB - A node-labeled rooted tree T (with root r) is an all-or-nothing subtree (called AoN-subtree) of a node-labeled rooted tree T′ if (1) T is a subtree of the tree rooted at some node u (with the same label as r) of T′, (2) for each internal node v of T, all the neighbors of v in T′ are the neighbors of v in T. Tree T′ is then called an AoN-supertree of T. Given a set of n node-labeled rooted trees, smallest common AoN-supertree problem seeks the smallest possible node-labeled rooted tree (denoted as ) such that every tree Ti in is an AoN-subtree of . It generalizes the smallest superstring problem and it has applications in glycobiology. We present a polynomial-time greedy algorithm with approximation ratio 6.

UR - http://www.scopus.com/inward/record.url?scp=77249162232&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77249162232&partnerID=8YFLogxK

U2 - 10.1007/11940128_12

DO - 10.1007/11940128_12

M3 - Conference contribution

AN - SCOPUS:77249162232

SN - 3540496947

SN - 9783540496946

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 100

EP - 110

BT - Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings

ER -

Aoki-Kinoshita KF, Kanehisa M, Kao M-Y, Li XY, Wang W. A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees. In Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. p. 100-110. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11940128_12