Abstract
We present an algorithm for counting glycan topologies of order \(n\) that improves on previously described algorithms by a factor \(n\) in both time and space. More generally, we provide such an algorithm for counting rooted or unrooted \(d\)-ary trees with labels or masses assigned to the vertices, and we give a “recipe” to estimate the asymptotic growth of the resulting sequences. We provide constants for the asymptotic growth of \(d\)-ary trees and labeled quaternary trees (glycan topologies). Finally, we show how a classical result from enumeration theory can be used to count glycan structures where edges are labeled by bond types. Our method also improves time bounds for counting alkanes.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles and news from researchers in related subjects, suggested using machine learning.Notes
In this paper, we do not consider the comparatively rare case of monosaccharide which do not have exactly four carbon hydroxy groups.
References
Bell JP, Burris SN, Yeats KA (2006) Counting rooted trees: the universal law \(t(n)\sim C\rho ^{-n} n^{-3/2}\). Electron J Combin 13(1): R63, 64 (electronic)
Böcker S, Kehr B, Rasche F (2011) Determination of glycan structure from tandem mass spectra. IEEE/ACM Trans Comput Biol Bioinform 8(4):976–986
Böcker S, Lipták Zs (2005) Efficient mass decomposition. In: Proccedings of the ACM symposium on applied computing (ACM SAC 2005), ACM Press, Santa Fe, pp 151–157
Böcker S, Lipták Zs (2007) A fast and simple algorithm for the money changing problem. Algorithmica 48(4):413–432
Cayley A (1881) On the analytical forms called trees. Am J Math 4:266–268
Ethier M, Saba JA, Spearman M, Krokhin O, Butler M, Ens W, Standing KG, Perreault H (2003) Application of the StrOligo algorithm for the automated structure assignment of complex N-linked glycans from glycoproteins using tandem mass spectrometry. Rapid Commun Mass Spectrom 17(24):2713–2720
Flajolet P, Sedgewick R (2009) Analytic combinatorics. Cambridge University Press. Available from http://algo.inria.fr/flajolet/Publications/book.pdf
Gaucher SP, Morrow J, Leary JA (2000) STAT: a saccharide topology analysis tool used in combination with tandem mass spectrometry. Anal Chem 72(11):2331–2336
Goldberg D, Bern MW, Li B, Lebrilla CB (2006) Automatic determination of O-glycan structure from fragmentation spectra. J Proteome Res 5(6):1429–1434
Harary F, Palmer EM (1973) Graphical enumeration. Academic Press, New York
Harary F, Robinson RW, Schwenk AJ (1975) Twenty-step algorithm for determining the asymptotic number of trees of various species. J Aust Math Soc Ser A 20(4):483–503
Henze HR, Blair CM (1931) The number of structurally isomeric alcohols of the methanol series. J Am Chem Soc 53(8):3042–3046
Jayo RG, Li J, Chen DD (2013) Capillary electrophoresis mass spectrometry for the characterization of O-acetylated N-glycans from fish serum. Anal Chem 84(20):8756–8762
Otter R (1948) The number of trees. Ann Math 49(3):583–599
Palmisano G, Antonacci D, Larsen MR (2010) Glycoproteomic profile in wine: a ‘sweet’ molecular renaissance. J Proteome Res 9(12):6148–6159
Pólya G (1937) Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math 68(1):145–254
Rains EM and Sloane NJA (1999) On Cayley’s enumeration of alkanes (or 4-valent trees). J Integer Seq 2:(electronic)
Raman R, Raguram S, Venkataraman G, Paulson JC, Sasisekharan R (2005) Glycomics: an integrated systems approach to structure-function relationships of glycans. Nat Methods 2(11):817–824
Trinajstić N, Jeričević Ž, Knop JV, Müller WR, Szymanski K (1983) Computer generation of isomeric structures. Pure Appl Chem 55(2):379–390
Varki A, Cummings RD, Esko JD, Freeze HH, Stanley P, Bertozzi CR, Hart GW, Etzler ME (eds) (2009) Essentials of glycobiology, 2nd edn. Cold Spring Harbor Laboratory Press. Available from http://www.ncbi.nlm.nih.gov/books/NBK1908/
Acknowledgments
We thank Birte Kehr for preparing Fig. 1. This material is based upon work supported financially by the National Research Foundation of South Africa under grant number 70560.
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Böcker, S., Wagner, S. Counting glycans revisited. J. Math. Biol. 69, 799–816 (2014). https://doi.org/10.1007/s00285-013-0721-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00285-013-0721-3