title: Efficient tree-matching methods for accurate carbohydrate database queries.
abstract: One aspect of glycome informatics is the analysis of carbohydrate sugar chains, or glycans, whose basic structure is not a sequence, but a tree structure. Although there has been much work in the development of sequence databases and matching algorithms for sequences (for performing queries and analyzing similarity), the more complicated tree structure of glycans does not allow a direct implementation of such a database for glycans, and further, does not allow for the direct application of sequence alignment algorithms for performing searches or analyzing similarity. Therefore, we have utilized a polynomial-time dynamic programming algorithm for solving the maximum common subtree of two trees to implement an accurate and efficient tool for finding and aligning maximally matching glycan trees. The KEGG Glycan database for glycan structures released recently incorporates our tree-structure alignment algorithm with various parameters to adapt to the needs of a variety of users. Because we use similarity scores as opposed to a distance metric, our methods are more readily used to display trees of higher similarity. We present the two methods developed for this purpose and illustrate its validity.
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, Japan. kiyoko@kuicr.kyoto-u.ac.jp
authors.forename: Kiyoko F
authors.initials: KF
authors.lastname: Aoki
authors.forename: Atsuko
authors.initials: A
authors.lastname: Yamaguchi
authors.forename: Yasushi
authors.initials: Y
authors.lastname: Okuno
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
authors.forename: Nobuhisa
authors.initials: N
authors.lastname: Ueda
authors.forename: Minoru
authors.initials: M
authors.lastname: Kanehisa
authors.forename: Hiroshi
authors.initials: H
authors.lastname: Mamitsuka
mesh_terms: D000465:Algorithms; D002236:Carbohydrate Conformation; D002240:Carbohydrate Sequence; D002241:Carbohydrates / Q000737:chemistry*; D016208:Databases, Factual; D003663:Decision Trees; D008969:Molecular Sequence Data; D009844:Oligosaccharides / Q000737:chemistry; D011134:Polysaccharides / Q000737:chemistry*; D015203:Reproducibility of Results
chemical_list: D002241:Carbohydrates; D009844:Oligosaccharides; D011134:Polysaccharides