title: Complexities and algorithms for glycan sequencing using tandem mass spectrometry.
abstract: Determining glycan structures is vital to comprehend cell-matrix, cell-cell, and even intracellular biological events. Glycan sequencing, which determines the primary structure of a glycan using tandem mass spectrometry (MS/MS), remains one of the most important tasks in proteomics. Analogous to peptide de novo sequencing, glycan de novo sequencing determines the structure without the aid of a known glycan database. We show in this paper that glycan de novo sequencing is NP-hard. We then provide a heuristic algorithm and develop a software program to solve the problem in practical cases. Experiments on real MS/MS data of glycopeptides demonstrate that our heuristic algorithm gives satisfactory results on practical data.
authors.affiliation: Department of Computer Science, University of Western Ontario, London, Ontario, N6A 5B7, Canada. bxshan@csd.uwo.ca
authors.forename: Baozhen
authors.initials: B
authors.lastname: Shan
authors.forename: Bin
authors.initials: B
authors.lastname: Ma
authors.forename: Kaizhong
authors.initials: K
authors.lastname: Zhang
authors.forename: Gilles
authors.initials: G
authors.lastname: Lajoie
mesh_terms: D000465:Algorithms; D002240:Carbohydrate Sequence; D002241:Carbohydrates / Q000737:chemistry*; D013058:Mass Spectrometry / Q000379:methods*; D008969:Molecular Sequence Data; D011134:Polysaccharides / Q000737:chemistry*; D017421:Sequence Analysis / Q000379:methods*
chemical_list: D002241:Carbohydrates; D011134:Polysaccharides