Shan Baozhen, Ma Bin, Zhang Kaizhong, Lajoie Gilles
Department of Computer Science, University of Western Ontario, London, Ontario, N6A 5B7, Canada.
J Bioinform Comput Biol. 2008 Feb;6(1):77-91. doi: 10.1142/s0219720008003291.
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.
确定聚糖结构对于理解细胞与基质、细胞与细胞乃至细胞内的生物学事件至关重要。聚糖测序利用串联质谱法（MS/MS）确定聚糖的一级结构，仍然是蛋白质组学中最重要的任务之一。与肽段从头测序类似，聚糖从头测序无需借助已知聚糖数据库即可确定结构。我们在本文中表明，聚糖从头测序是NP难问题。然后，我们提供了一种启发式算法，并开发了一个软件程序来解决实际案例中的问题。对糖肽的真实MS/MS数据进行的实验表明，我们的启发式算法在实际数据上给出了令人满意的结果。
