Published in

Institute of Electrical and Electronics Engineers, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(8), p. 976-986, 2011

DOI: 10.1109/tcbb.2010.129

Springer Verlag, Lecture Notes in Computer Science, p. 258-267

DOI: 10.1007/978-3-642-02882-3_26

Links

Tools

Export citation

Search in Google Scholar

Determination of Glycan Structure from Tandem Mass Spectra

Journal article published in 2009 by Sebastian Böcker ORCID, Birte Kehr, Florian Rasche
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

Glycans are molecules made from simple sugars that form complex tree structures. Glycans constitute one of the most important protein modifications and identification of glycans remains a pressing problem in biology. Unfortunately, the structure of glycans is hard to predict from the genome sequence of an organism. In this paper, we consider the problem of deriving the topology of a glycan solely from tandem mass spectrometry (MS) data. We study, how to generate glycan tree candidates that sufficiently match the sample mass spectrum, avoiding the combinatorial explosion of glycan structures. Unfortunately, the resulting problem is known to be computationally hard. We present an efficient exact algorithm for this problem based on fixed-parameter algorithmics that can process a spectrum in a matter of seconds. We also report some preliminary results of our method on experimental data, combining it with a preliminary candidate evaluation scheme. We show that our approach is fast in applications, and that we can reach very well de novo identification results. Finally, we show how to count the number of glycan topologies for a fixed size or a fixed mass. We generalize this result to count the number of (labeled) trees with bounded out degree, improving on results obtained using Pólya's enumeration theorem.