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 Scopus citations

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A 6-Approximation algorithm for computing smallest common AoN-supertree with application to the reconstruction of glycan trees'. Together they form a unique fingerprint.

  • 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