Antilope—A Lagrangian Relaxation Approach to the de novo Peptide Sequencing Problem

peer-reviewed · IEEE/ACM Transactions on Computational Biology and Bioinformatics · 2012

peer-reviewed · IEEE/ACM Transactions on Computational Biology and Bioinformatics · 2012. Sandro Andreotti et al. Peptide sequencing from mass spectrometry data is a key step in proteome research. Especially de novo…
Date 2012-03-01
Type peer-reviewed
Venue IEEE/ACM Transactions on Computational Biology and Bioinformatics
Publisher IEEE
Contribution algorithm
DOI 10.1109/TCBB.2011.59
Citations (OpenAlex) 20
Venue 2-year citedness 4.84

Preprint version: Antilope – A Lagrangian Relaxation Approach to the de novo Peptide Sequencing Problem (2011-02-19, arXiv)

Abstract

Peptide sequencing from mass spectrometry data is a key step in proteome research. Especially de novo sequencing, the identification of a peptide from its spectrum alone, is still a challenge even for state-of-the-art algorithmic approaches. In this paper, we present ANTILOPE, a new fast and flexible approach based on mathematical programming. It builds on the spectrum graph model and works with a variety of scoring schemes. ANTILOPE combines Lagrangian relaxation for solving an integer linear programming formulation with an adaptation of Yen’s k shortest paths algorithm. It shows a significant improvement in running time compared to mixed integer optimization and performs at the same speed like other state-of-the-art tools. We also implemented a generic probabilistic scoring scheme that can be trained automatically for a data set of annotated spectra and is independent of the mass spectrometer type. Evaluations on benchmark data show that ANTILOPE is competitive to the popular state-of-the-art programs PepNovo and NovoHMM both in terms of runtime and accuracy. Furthermore, it offers increased flexibility in the number of considered ion types. ANTILOPE will be freely available as part of the open source proteomics library OpenMS.

Authors

  1. Sandro Andreotti · Freie Universität Berlin, International Max Planck Research School
  2. Gunnar W. Klau · Centrum Wiskunde & Informatica (CWI), Freie Universität Berlin
  3. Knut Reinert · Freie Universität Berlin

Methods and tools

  • Antilope: Lagrangian-relaxation formulation of de novo peptide sequencing. Frames the problem as a constrained optimization over the spectrum graph and solves it with iterative subgradient ascent.

Cites (11)

Cited by (7)

Seen in the charts

Back to the full map

Back to top