Send to

Choose Destination
J Bioinform Comput Biol. 2008 Feb;6(1):77-91.

Complexities and algorithms for glycan sequencing using tandem mass spectrometry.

Author information

Department of Computer Science, University of Western Ontario, London, Ontario, N6A 5B7, Canada.


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.

[Indexed for MEDLINE]

Supplemental Content

Loading ...
Support Center