Stoichiometry Determination for Mass-spectrometry Data: the Interval Case

Deepesh Agarwal 1, * Frédéric Cazals 1 Noël Malod-Dognin 1
* Corresponding author
1 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In structural proteomics, given the individual masses of a set of protein types and the exact mass of a protein complex, the exact stoichiometry determination problem (SD), also known as the money-change problem, consists of enumerating all the stoichiometries of these types which allow to recover the target mass. If the target mass suffers from experimental uncertainties, the interval SD problem consists of finding all the stoichiometry vectors compatible with a target mass within an interval. We make contributions in two directions. From an algorithmic standpoint, we make two modifications to exact SD algorithms, to inherently address the interval SD problem. The first modification concerns the classical tree-like exploration, resulting in algorithm DIOPHANTINE, which solves the interval SD problem using constant-memory space. The second modification concerns the classical dynamic programming based algorithm, resulting in algorithm DP++, which solves the interval SD problem in an output sensitive manner. From an applied perspective, we raise three points. First, we show that DIOPHANTINE and DP++ yield an improvement from 3 to 4 orders of magnitude over state-of-the-art exact SD algorithms, for typical protein complexes facing uncertainties on the target mass in the range 0.1-1%. It is shown that this gain comes from the ability of DP++ and DIOPHANTINE to avoid redundant calculations occurring when solving the interval SD problem as a sequence of exact SD problems. Second, we show that DIOPHANTINE behaves like an output-sensitive algorithm---especially when the interval width increases, albeit such a property cannot be expected in general. Third, from a biological perspective, using a panel of biological complexes (eukaryotic translation factor, yeast exosome, 19S proteasome sub-unit, nuclear pore complex), we stress the importance of enumeration, even at a null noise level. We also propose a representation of all solutions of an interval SD problem using a directed acyclic graph stressing the prominent protein types. The programs accompanying this paper are available from http://team.inria.fr/abs/addict/.
Complete list of metadatas

Cited literature [40 references]  Display  Hide  Download

https://hal.inria.fr/hal-00741491
Contributor : Frederic Cazals <>
Submitted on : Friday, February 8, 2013 - 12:26:23 PM
Last modification on : Thursday, January 11, 2018 - 4:31:49 PM
Long-term archiving on : Saturday, April 1, 2017 - 8:27:09 PM

File

RR-8101-addict.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00741491, version 3

Collections

Citation

Deepesh Agarwal, Frédéric Cazals, Noël Malod-Dognin. Stoichiometry Determination for Mass-spectrometry Data: the Interval Case. [Research Report] RR-8101, INRIA. 2013, pp.52. ⟨hal-00741491v3⟩

Share

Metrics

Record views

473

Files downloads

239