Complexities and algorithms for glycan sequencing using tandem mass spectrometry.
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.
Shan
Baozhen
B
Department of Computer Science, University of Western Ontario, London, Ontario, N6A 5B7, Canada. bxshan@csd.uwo.ca
Ma
Bin
B
Zhang
Kaizhong
K
Lajoie
Gilles
G
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*
D002241:Carbohydrates; D011134:Polysaccharides