Connectivity Inference in Mass Spectrometry based Structure Determination

Deepesh Agarwal 1 Julio Araujo 2 Christelle Caillouet 2 Frédéric Cazals 1, * David Coudert 2 Stéphane Pérennes 2
* Auteur correspondant
1 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : 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.
Liste complète des métadonnées


https://hal.inria.fr/hal-00837496
Contributeur : Frederic Cazals <>
Soumis le : samedi 22 juin 2013 - 11:44:46
Dernière modification le : mardi 13 décembre 2016 - 15:40:21
Document(s) archivé(s) le : lundi 23 septembre 2013 - 03:05:08

Fichier

RR-8320-MCI.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00837496, version 1

Collections

Citation

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>

Partager

Métriques

Consultations de
la notice

659

Téléchargements du document

382