Stoichiometry Determination for Mass-spectrometry Data: the Interval Case

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/.

Data and Resources

Additional Info

Field Value
Source https://inria.hal.science/hal-00741491
Author Agarwal, Deepesh, Cazals, Frédéric, Malod-Dognin, Noël
Maintainer CCSD
Last Updated May 14, 2026, 14:49 (UTC)
Created May 14, 2026, 14:49 (UTC)
Identifier Report N°: RR-8101
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Algorithms, Biology, Structure (ABS) ; Centre Inria d'Université Côte d'Azur ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
creator Agarwal, Deepesh
date 2013-02-08T00:00:00
harvest_object_id feace10a-1ce4-47e4-a8a5-6694f910e997
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-10-24T00:00:00
set_spec type:REPORT