Connectivity Inference in Mass Spectrometry based Structure Determination - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2013

Connectivity Inference in Mass Spectrometry based Structure Determination

Résumé

We consider the following Minimum Connectivity Inference problem (MCI), which arises in structural biology: given vertex sets $V_i\subseteq V, i\in I$, find the graph $G=(V,E)$ minimizing the size of the edge set $E$, such that the sub-graph of $G$ induced by each $V_i$ is connected. This problem arises in structural biology, when one aims at finding the pairwise contacts between the proteins of a protein assembly, given the lists of proteins involved in sub-complexes. We present four contributions. First, using a reduction of the set cover problem, we establish that MCI is APX-hard. Second, we show how to solve the problem to optimality using a mixed integer linear programming formulation (MILP). Third, we develop a greedy algorithm based on union-find data structures (Greedy), yielding a $2(\log_2 |V|+\log_2 \kappa)$-approximation, with $\kappa$ the maximum number of subsets $V_i$ a vertex belongs to. Fourth, application-wise, we use the MILP and the greedy heuristic to solve the aforementioned connectivity inference problem in structural biology. We show that the solutions of MILP and Greedy are more parsimonious than those reported by the algorithm initially developed in biophysics, which are not qualified in terms of optimality. Since MILP outputs a set of optimal solutions, we introduce the notion of consensus solution. Using assemblies whose pairwise contacts are known exhaustively, we show an almost perfect agreement between the contacts predicted by our algorithms and the experimentally determined ones, especially for consensus solutions.
Nous considérons le problème d'Inférence de Connectivité Minimale (MCI) qui se pose en biologie structurale: étant donnés des ensembles de sommets $V_i\subseteq V, i\in I$, trouver le graphe $G=(V,E)$ minimisant la taille de l'ensemble des arêtes $E$, de telle sorte que le sous-graphe de $G$ induit par un chaque ensemble $V_i$ soit connexe. Ce problème se pose en biologie structurale, pour la determination des contacts plausibles entre les protéines d'un assemblage, à partir des listes de protéines présentes dans des sous-complexes. Nous présentons quatre contributions. Premièrement, nous montrons que le problème MCI est APX-hard en utilisant une réduction de set cover. Deuxièmement, nous présentons une formulation en programme linéaire mixte (MILP) permettant de résoudre MCI de façon optimale. Troisièmement, nous proposons un algorithme glouton (Greedy) basé sur des structures de données Union-Find. Nous montrons que cet algorithme est une $2(\log_2 |V|+\log_2 \kappa)$-approximation de l'optimal, où $\kappa$ est le nombre maximum d'ensembles $V_i$ contenant un sommet donné. Quatrièmement, d'un point de vue appliqué, nous utilisons l'approche MILP et l'algorithme glouton pour résoudre le problème MCI en biologie structurale. Nous montrons que les solutions calculées par MILP et Greedy sont plus parcimonieuses que celles produites par l'algorithme utilisé à ce jour en bio-physique --- lequel n'est pas qualifié en terme d'optimalité. Les algorithmes MILP et Greedy générant des ensembles de solutions, nous introduisons la notion de solution consensus. En utilisant le cas d'assemblages dont les contacts sont connus de façon exhaustive, nous montrons un accord presque parfait entre les contacts determinés par nos algorithmes et ceux determinés expérimentalement, en particulier pour les solutions consensus.
Fichier principal
Vignette du fichier
RR-8320-MCI.pdf (940.71 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00837496 , version 1 (22-06-2013)

Identifiants

  • HAL Id : hal-00837496 , version 1

Citer

Deepesh Agarwal, Julio Araujo, Christelle Caillouet, Frédéric Cazals, David Coudert, et al.. Connectivity Inference in Mass Spectrometry based Structure Determination. [Research Report] RR-8320, INRIA. 2013, pp.23. ⟨hal-00837496⟩
519 Consultations
494 Téléchargements

Partager

Gmail Facebook X LinkedIn More