About KCaM

KCaM (KEGG Carbohydrate Matcher) is a dynamic programming method for comparing branched carbohydrate chain structures. It has been implemented in the KEGG system for searching against glycan structure databases. To put it simply, KCaM utilizes efficient methodologies from bioinformatics and theoretical computer science to perform its carbohydrate chain comparisons. Because of the generally small size of carbohydrate chain structures, the thoroughness of the Smith-Waterman sequence alignment algorithm has been modified for carbohydrate chains. In addition, a known polynomial time algorithm for finding the maximum common subtree of two trees has also been combined with the alignment algorithm.

example
Example of search result
The algorithm compares all monosaccharides, or sugars, in the first carbohydrate structure with all of those in the second. A mapping is generated for the children of each of these nodes to compare them. The type of comparison is determined by the options the user selects. A score is applied whenever a comparison is satisfied. Then the following set of comparisons is performed by traversing up the tree structure of the carbohydrate chain (to the nodes' parents) and the comparison is repeated. This recursion ends at the root of the trees, and the maximum value is the score returned. (see reference)

Search options

The user has the option of selecting several types of searches which vary according to the purpose of the query. The user may also select to query from KEGG Glycan or the original CarbBank database. A brief outline of the search options is given below.

Approximate Match vs. Exact Match:
Approximate Match aligns monosaccharides with one another and allows gaps in the query. Exact Match aligns bonds with one another and does not allow gaps.

Local vs. Global:
Local matching searches for patterns within a smaller range of the structure. Global matching performs an overall search over the entire structure (i.e., global matching is more loose in its matching criteria).

References
- Aoki, K.F., Yamaguchi, A., Ueda, N., Akutsu, T., Mamitsuka, H., Goto, S., and Kanehisa, M.; KCaM (KEGG Carbohydrate Matcher): a software tool for analyzing the structures of carbohydrate sugar chains. Nucleic Acids Res. 32, W267-W272 (2004). [pubmed]
- Aoki, K.F., Yamaguchi, A., Okuno, Y., Akutsu, T., Ueda, N., Kanehisa, M., and Mamitsuka, H.; Efficient tree-matching methods for accurate carbohydrate database queries. Genome Informatics 14, 134-143 (2003). [pubmed]

Last updated: April 1, 2009

« Back