Stoichiometry Determination for Mass-spectrometry Data: the Interval Case
Résumé
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/.
En protéomique structurale, étant données les masses exactes d'un ensemble de protéines et la masse exacte d'un complexe, le problème de la détermination de la stoechiométrie (SD), consiste à énumérer les stoechiométries de ces protéines permettant de reconstituer la masse du complexe. Si celle-ci présente une incertitude, il s'agit d'énumérer les stoechiométries compatibles avec une masse appartenant à un intervalle. Nous présentons des contributions dans deux registres. D'un point de vue théorique, nous apportons des modifications aux algorithmes exacts de SD, afin de résoudre le problème par intervalle. La première modification concerne l'algorithme de recherche exhaustif, et conduit à l'algorithme DIOPHANTINE qui travaille à mémoire constante. La seconde concerne l'algorithme état de l'art utilisant la programmation dynamique, et conduit à l'algorithme DP++, lequel est sensible à la sortie. D'un point de vue appliqué, nous présentons trois résultats. Tout d'abord, nous montrons que DIOPHANTINE et DP++ sont plus rapides de 3 à 4 ordres de grandeur que l'algorithme état de l'art résolvant le problème exact, pour des complexes protéiques typiques présentant des incertitudes de l'ordre de 0.1% a 1%. Nous montrons que ce gain tient à l'évitement de calculs redondants lorsque l'algorithme exact est appellé sur chacune des masses d'un intervalle. D'autre part, nous montrons que DIOPHANTINE a un comportement d'autant plus sensible à la sortie que la taille de l'intervalle augmente. Enfin et d'un point de vue biologique, en étudiant plusieurs complexes protéiques (facteur de traduction eucaryote, exosome de la levure, sous-unité 19S du protéasome, pore nucléaire), nous soulignons l'importance des solutions multiples, même à un niveau d'incertitude nul. Nous introduisons également une représentation de toutes les solutions d'un problème par intervalle, mettant en evidence les types de protéines les plus utilisés. Les programmes sont disponibles via http://team.inria.fr/abs/addict/.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...