An accurate de novo algorithm for glycan topology determination from mass spectra

Liang Dong, Bing Shi, Guangdong Tian, Yan Bo Li, Bing Wang, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


Determining the glycan topology automatically from mass spectra represents a great challenge. Existing methods fall into approximate and exact ones. The former including greedy and heuristic ones can reduce the computational complexity, but suffer from information lost in the procedure of glycan interpretation. The latter including dynamic programming and exhaustive enumeration are much slower than the former. In the past years, nearly all emerging methods adopted a tree structure to represent a glycan. They share such problems as repetitive peak counting in reconstructing a candidate structure. Besides, tree-based glycan representation methods often have to give different computational formulas for binary and ternary glycans. We propose a new directed acyclic graph structure for glycan representation. Based on it, this work develops a de novo algorithm to accurately reconstruct the tree structure iteratively from mass spectra with logical constraints and some known biosynthesis rules, by a single computational formula. The experiments on multiple complex glycans extracted from human serum show that the proposed algorithm can achieve higher accuracy to determine a glycan topology than prior methods without increasing computational burden.

Original languageEnglish (US)
Article number2368981
Pages (from-to)568-578
Number of pages11
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Issue number3
StatePublished - May 1 2015

All Science Journal Classification (ASJC) codes

  • Biotechnology
  • Genetics
  • Applied Mathematics


  • De novo algorithm
  • Glycan topology interpretation
  • Mass spectra
  • Optimization
  • Tandem mass spectrometry (MS/MS)


Dive into the research topics of 'An accurate de novo algorithm for glycan topology determination from mass spectra'. Together they form a unique fingerprint.

Cite this