Trouver données correctes - Théorie des Graphes

a marqué ce sujet comme résolu.

Bonjour,

J’ai une question dans mes exercices en introduction à la théorie des graphes que je trouve intéressante.

On a un laboratoire de biologie qui qui mesure des intéractions entre protéines. Les données sont sauvegardées dans ce format:

prot A // protB

p1020 // p2321

p1450 // p3731

La personne qui sauvegarde les données fait deux copies du fichier. Malheureusement, elle a mélangé de manière aléatoire la première colonne des données dans l’un des fichiers ET il ne se souvient plus quel est le bon fichier entre les deux.

Comment peut-on utiliser la théorie des graphes pour dire (au mieux) quel est le bon fichier ?

J’ai du mal à voir comment on pourrait faire mais je trouve l’exercice intéressant… Si vous avez des pistes, je suis preneur :-)

Merci!

+0 -0

Salut,

J’ai un peu du mal à voir où tu veux en venir, pourquoi mentionner la théorie des graphes en particulier si tu n’as pas d’idée sur comment procéder ?

Pour ton problème en particulier, j’ai l’impression que ta meilleure chance de retrouver le bon fichier est si le fichier est censé être organisé d’une façon logique ou si tu as des données existante auxquelles comparer. Quelque idées que tu as sûrement déjà eues, mais sait-on jamais :

  • est-ce qu’il y a un ordre dans lequel les noms d’une colonne sont censés être organisé ?
  • est-ce qu’il y a des couples dont on sait qu’ils n’ont pas été mesurés (par exemple une protéine avec elle-même ou un couple déjà étudié une autre fois) ?
  • est-ce qu’il y a des patterns qui ne peuvent pas se trouver dans un fichier non corrompu (e.g. deux fois le même couple, deux fois de suite la même protéine, etc) ?
  • est-ce que les noms des protéines peuvent être reliés même seulement statistiquement, à la mesure attendu (e.g. interactions plus fortes si les numéro sont plus proches) ?
  • est-ce qu’il y a des jeux de données existants permettant la comparaison ?

Bon sinon un conseil, c’est d’automatiser ce genre de processus, plus il y a de travail manuel, plus le risque de corrompre les données est fort…

J’ai un peu du mal à voir où tu veux en venir, pourquoi mentionner la théorie des graphes en particulier si tu n’as pas d’idée sur comment procéder ?

Simplement parce que c’est dans mon cours d’intro à la théorie des graphes donc je suppose qu’il faut les utiliser :-)

En tout cas merci pour les idées, j’y avais pensé pour la majorité sauf un… pourtant le plus basique et essentiel "est-ce qu’il y a des couples dont on sait qu’ils n’ont pas été mesurés"… C’est effectivement probablement la première chose à vérifier !

Salut,

J’ai du mal aussi à voir comment on pourrait utiliser la théorie des graphes, j’ai l’impression qu’il manque trop d’information pour qu’on puisse s’en servir.

Après on peut toujours essayer de résoudre le problème en se disant qu’il est improbable qu’on ait consigné deux fois la même interaction, et qu’une protéine n’interagit pas avec elle même.

Si on veut caser de la théorie des graphes à tout prix, la phrase précédente se traduit par "le graphe des interactions est simple et sans cycle de longueur 1". Simple signifie qu’il y a au plus une arête entre deux noeuds (donc qu’on a consigné une fois au plus l’interaction), et un cycle de longueur 1, c’est une chaîne d’interactions dont le premier élément de la chaîne est aussi le dernier, et dont la chaîne est de longueur 1. Autrement dit c’est une interaction d’une protéine avec elle même. Donc si un des fichiers transgresse cette affirmation, c’est le mauvais.

Si on avait plus d’informations sur les fichiers on pourrait estimer la probabilité de la réussite de cette approche.

Ah, boucle, c’était le mot que je cherchais. Et du coup effectivement, j’aurais du vérifier la définition de graphe simple. L’avantage c’est que ça simplifie la phrase de la solution, vu qu’on n’a plus qu’à dire qu’on cherche si le graphe est simple.

Merci !

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte