Format

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

1
Department of Computer Science, University of Western Ontario, London, Ontario, N6A 5B7, Canada. bxshan@csd.uwo.ca

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.

PMID:
18324747
[Indexed for MEDLINE]

Supplemental Content

Loading ...
Support Center