title: Counting glycans revisited.
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.
authors: Lehrstuhl für Bioinformatik, Friedrich-Schiller-Universität Jena, Ernst-Abbe-Platz 2, Jena, Germany, sebastian.boecker@uni-jena.de.
authors: Sebastian
authors: S
authors: Böcker
authors: Stephan
authors: S
authors: Wagner
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D010802:Phylogeny; D011134:Polysaccharides / Q000737:chemistry* / Q000648:ultrastructure
chemical_list: D011134:Polysaccharides
references: Nat Methods. 2005 Nov;2(11):817-24
references: 16278650
references: Anal Chem. 2000 Jun 1;72(11):2331-6
references: 10857602
references: J Proteome Res. 2006 Jun;5(6):1429-34
references: 16739994
references: Anal Chem. 2012 Oct 16;84(20):8756-62
references: 22971167
references: IEEE/ACM Trans Comput Biol Bioinform. 2011 Jul-Aug;8(4):976-86
references: 21173459
references: J Proteome Res. 2010 Dec 3;9(12):6148-59
references: 20923237
references: Rapid Commun Mass Spectrom. 2003;17(24):2713-20
references: 14673818