Managing and analyzing carbohydrate data

ABSTRACT

One of the most vital molecules in multicellular organisms is the carbohydrate, as it is structurally important in the construction of such organisms. In fact, all cells in nature carry carbohydrate sugar chains, or glycans, that help modulate various cell-cell events for the development of the organism. Unfortunately, informatics research on glycans has been slow in comparison to DNA and proteins, largely due to difficulties in the biological analysis of glycan structures. Our work consists of data engineering approaches in order to glean some understanding of the current glycan data that is publicly available. In particular, by modeling glycans as labeled unordered trees, we have implemented a tree-matching algorithm for measuring tree similarity. Our algorithm utilizes proven efficient methodologies in computer science that has been extended and developed for glycan data. Moreover, since glycans are recognized by various agents in multicellular organisms, in order to capture the patterns that might be recognized, we needed to somehow capture the dependencies that seem to range beyond the directly connected nodes in a tree. Therefore, by defining glycans as labeled ordered trees, we were able to develop a new probabilistic tree model such that sibling patterns across a tree could be mined. We provide promising results from our methodologies that could prove useful for the future of glycome informatics.

REFERENCES

• 1: K. F. AOKI ET AL., Efficient tree-matching methods for accurate carbohydrate database queries, Genome Informatics, 14 (2003), pp. 134--143.
• 2: K. F. AOKI ET AL., Application of a new probabilistic model for recognizing complex patterns in glycans, in ISMB, 2004.
• 3: Tatsuya Asai , Hiroki Arimura , Kenji Abe , Shinji Kawasoe , Setsuo Arikawa, Online Algorithms for Mining Semi-structured Data Stream, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.27, December 09-12, 2002
• 4: E. BAUM AND T. PETRIE, Statistical inference for probabilistic functions of infinite state Markov chains, Ann. Math. Stat., 37 (1966), pp. 1554--1563.
• 5: C. R. BERTOZZI AND L. L. KIESSLING, Carbohydrates and glycobiology review: Chemical glycobiology, Science, 291 (2001), pp. 2357--2364.
• 6: S. A. BROOKS ET AL., Functional and Molecular Glycobiology, BIOS Scientific Publishers Ltd., 2002.
• 7: A. DEMPSTER, N. LAIRD, AND D. RUBIN, Maximum likelihood from incomplete data via the EM algorithm, J. R. Statist. Soc. B, 39 (1977), pp. 1--38.
• 8: Michelangelo Diligenti , Paolo Frasconi , Marco Gori, Hidden Tree Markov Models for Document Image Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.519-523, April 2003
• 9: K. DRICKAMER, Two distinct classes of carbohydrate-recognition domains in animal lectins, J. Biol. Chem., 263 (1988), pp. 9557--9560.
• 10: R. DURBIN ET AL., Biological sequence analysis, Cambridge University Press, Cambridge, 1998.
• 11: J. EDMONDS AND D. MATULA, An algorithm for subtree identification, SIAM Rev., 10 (1968), pp. 273--274.
• 12: P. FALK, L. C. HOSKINS, AND G. LARSON, Bacteria of the human intestinal microbiota produce glycosidases specific for lacto-series glycosphingolipids, J. Biochem, 108 (1990), pp. 466--474.
• 13: Shai Fine , Yoram Singer , Naftali Tishby, The Hierarchical Hidden Markov Model: Analysis and Applications, Machine Learning, v.32 n.1, p.41-62, July 1998 [doi>10.1023/A:1007469218079]
• 14: C. HYEOKHO AND R. BARANIUK, Multiscale image segmentation using wavelet-domain hidden Markov models, IEEE Trans. Image Proc., 46 (2001), pp. 886--902.
• 15: M. KANEHISA ET AL., The KEGG resource for deciphering the genome, NAR, 32 (2004), pp. D277-D280.
• 16: Hisashi Kashima , Teruo Koyanagi, Kernels for Semi-Structured Data, Proceedings of the Nineteenth International Conference on Machine Learning, p.291-298, July 08-12, 2002
• 17: Guo-Hui Lin , Bin Ma , Kaizhong Zhang, Edit distance between two RNA structures, Proceedings of the fifth annual international conference on Computational biology, p.211-220, April 22-25, 2001, Montreal, Quebec, Canada [doi>10.1145/369133.369214]
• 18: I. MARCHAL, G. GOLFIER, O. DUGAS, AND M. MAJED., Bioinformatics in glycobiology, Biochimie, 85 (2003), pp. 75--81.
• 19: Lawrence Rabiner , Biing-Hwang Juang, Fundamentals of speech recognition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 20: T. F. SMITH AND M. S. WATERMAN, Identification of common molecular subsequences, J. Mol. Biol., 147 (1981), pp. 195--197.
• 21: Kuo-Chung Tai, The Tree-to-Tree Correction Problem, Journal of the ACM (JACM), v.26 n.3, p.422-433, july 1979 [doi>10.1145/322139.322143]
• 22: N. UEDA, K. F. AOKI, AND H. MAMITSUKA, A general probabilistic framework for mining labeled ordered trees, in SIAM DM, 2004.
• 23: A. VARKI, Sialic acids as ligands in recognition phenomena, FASEB J., 11 (1997), pp. 248--255.
• 24: A. VARKI ET AL., eds., Essentials of Glycobiology, Cold Spring Harbor Lab. Press, New York, 1999.
• 25: Mohammed J. Zaki , Charu C. Aggarwal, XRules: an effective structural classifier for XML data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956787]