Repository: Freie Universität Berlin, Math Department

Determination of Glycan Structure from Tandem Mass Spectra

Böcker, S. and Kehr, B. and Rasche, F. (2011) Determination of Glycan Structure from Tandem Mass Spectra. IEEE/ACM Transactions on Computational Biology and Bioinformatics , 8 (4). pp. 976-986. ISSN 1545-4963

Full text not available from this repository.

Official URL:


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.

Item Type:Article
Subjects:Mathematical and Computer Sciences > Computer Science
Divisions:Department of Mathematics and Computer Science > Institute of Computer Science > Algorithmic Bioinformatics Group
ID Code:1132
Deposited By: Anja Kasseckert
Deposited On:10 Apr 2012 14:19
Last Modified:16 May 2012 14:17

Repository Staff Only: item control page