論文

査読有り
2003年12月

Efficient Tree Matching Methods for Accurate Carbohydrate Database Queries.

Genome Informatics (Proceedings of the Fourteenth International Conference on Genome Informatics)
  • Aoki, K. F
  • ,
  • Yamaguchi, A
  • ,
  • Okuno, Y
  • ,
  • Akutsu, T
  • ,
  • Ueda, N
  • ,
  • Kanehisa, M
  • ,
  • Mamitsuka, H

14
開始ページ
134
終了ページ
143
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.11234/gi1990.14.134

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.

リンク情報
DOI
https://doi.org/10.11234/gi1990.14.134
PubMed
https://www.ncbi.nlm.nih.gov/pubmed/15706528
URL
https://www.jstage.jst.go.jp/article/gi1990/14/0/14_0_134/_article
Scopus
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=3242879778&origin=inward
Scopus Citedby
https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=3242879778&origin=inward
ID情報
  • DOI : 10.11234/gi1990.14.134
  • ISSN : 0919-9454
  • PubMed ID : 15706528
  • SCOPUS ID : 3242879778

エクスポート
BibTeX RIS