2003年12月
Efficient Tree Matching Methods for Accurate Carbohydrate Database Queries.
Genome Informatics (Proceedings of the Fourteenth International Conference on Genome Informatics)
- ,
- ,
- ,
- ,
- ,
- ,
- 巻
- 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