Extraction de motifs dans les graphes de workflows scientifiques

La quantité de données scientifiques, plus particulièrement les données biologiques (par exemple les données produites par les techniques du séquencement haut débit), est en pleine croissance. Une fois ces données brutes collectées et conservées, il faut les analyser et les comparer aux données existantes pour obtenir de nouvelles connaissances. Cette analyse se fait grâce à l’utilisation de différents outils, scripts ou programmes. C’est ainsi que de plus en plus de travaux se développés pour permettre d’assembler, de concevoir et d’exécuter ces ensembles de programmes de traitement de données, à l’aide de systèmes de gestion de workflows scientifiques.

L’utilisation des systèmes de workflows pour analyser les données est en plein essor, donnant lieu à un important développement des bases de données pour stocker ces workflows. Cependant, très peu de techniques ont été mises en oeuvre pour pouvoir aider les utilisateurs dans la conception des workflows scientifiques, notamment pour les aider à tirer au mieux partie des workflows existants dans les bases qui pourraient être réutilisés. Un besoin fort est présent dans la communauté bioinformatique pour proposer des techniques pour guider les utilisateurs dans leur choix d’ensemble d’outils à (ré)utiliser. C’est dans ce cadre que s’articulera les travaux de mon stage académique. Plus précisément, notre objectif est d’extraire des workflows scientifiques des sous-structures fréquentes et intéressantes pour pouvoir aider les utilisateurs lors de la conception de leurs workflows. L’objectif à court terme est de constituer des librairies de motifs, à partir des motifs extraits. À plus long terme, l’idée est d’utiliser ces motifs pour faire de la recommandation : en fonction d’un workflow particulièrement conçu, on pourrait suggérer à l’utilisateur de compléter son workflow par un (ensemble de) motif(s).

Etat de l’art

Conception des workflows scientifiques

Les workflows Un workflow est une représentation d’une suite ordonnée de tâches éffectuées par une personne, une entreprise etc, servant à décrire et exécuter un processus ou permettant de décrire et exécuter de manière automatique les étapes de traitements complexes et pertinent des données. Il existe deux types de workflows : les business workflows et les workflows scientifiques [13]. Une meilleure définition, compréhension des workflows scientifiques découle d’une comparaison des deux types de workflows.

D’une part, les business workflows sont des workflows utilisés dans de nombreux domaines comme les domaines commerciaux, financiers, ou encore pharmaceutiques. Ils ont pour but de décrire de manière organisationnelle les étapes d’un processus : par exemple définir les étapes de validation d’un document ou d’une commande de produit, avec des étapes de validation par certains acteurs de l’entreprise, payements bancaires, génération de factures, transformation d’un document d’un format à un autre et à une heure précise. Notons que dans ce type de workflow, le résultat de l’exécution est connu à l’avance et le workflow ne sert donc qu’à traduire de manière explicite le processus qu’il implémente : on parle alors de chaîne de planification de travail. Dans un business workflow, les étapes (nécessitant parfois l’intervention humaine) sont reliées par des arcs qui représentent le flot de contrôle : on passe d’une étape à l’autre parce que des évènements déclenchent le passage. Ces évènements sont de type « une personne a cliqué sur un bouton « , « il est midi », « la banque a donné son accord pour le paiement par carte bancaire » etc. D’autre part, les workflows scientifiques sont des workflows utilisés dans les protocoles expérimentaux dans des domaines comme la biologie ou la bioinformatique. Ils ont pour but d’analyser les données scientifiques. Ils sont donc représentés par un ensemble de tâches qui sont en fait des appels à outils (logiciels, scripts, programme etc) reliées entre elles par des arcs qui représentent le flot de données, c’est-à-dire l’ensemble des données qui transiteront dans le workflow lors de son exécution. Un workflow scientifique est donc un cadre présentant l’ensemble des tâches et l’ordre dans lequel elles pourront être exécutées. Chaque tâche, lors de l’exécution, consomme des données prises en entrée et génère des données consommées par la tâche suivante. Ainsi, l’exécution d’une tâche ne dépendra uniquement que des données prises en entrée par celle-ci : dès qu’elle aura en entrée toutes les données qu’elle attend, celle-ci pourra démarrer. Les workflows scientifiques sont donc complètement automatiques (il n’y a pas d’intervention nécessaire des utilisateurs durant toute l’exécution du workflow) et les résultats de leurs exécutions serviront à valider une hypothèse scientifique [13]. Ils offrent la possibilité aux utilisateurs de pouvoir traiter de grandes quantités de données hétérogènes, d’effectuer des calculs intensifs. La figure 1 donne un exemple de workflow scientifique. Les workflows scientifiques font l’objet des travaux de mon stage académique. Notons que dans la suite de ce rapport un noeud correspondra à une tâches qui est en fait un processeur dans Taverna ; un arc correspond au flot de données. Aide à la conception de workflows.

La phase de conception du workflow consiste à le définir. Durant cette phase, les utilisateurs peuvent se baser sur des workflows préexistants qu’ils modifient pour construire leur modèle ou alors ils peuvent simplement réutiliser les workflows existants [13]. Une autre façon est de choisir dans des librairies des processeurs à enchaîner les uns aux autres. Cette phase se fait grâce à des systèmes de gestion de workflows tels que Kepler [4],Triana [19], ou Taverna [12], qui offrent une interface conviviale aux utilisateurs pour pouvoir construire le workflow en ajoutant ou enlevant des boîtes correspondants aux tâches du workflow.

Permettre la réutilisation du workflow consiste à le rendre moins complexe à la lecture, et ainsi plus facile à exploiter par l’utilisateur. [6] propose une méthode pour distiller des sous-structures dites mauvaises (appelées « anti-patterns ») dans les workflows scientifiques, présentant des répétitions. Ces sous-structures sont considérées comme directement associée à une mauvaise conception du workflow. La méthode présentée en [6] consiste donc à retirer ces sous-structures, à les modifier puis les réintégrer dans le workflow initial. Cette étape de transformation ne modifiera pas le comportement du workflow à l’exécution (le workflow original et le workflow réécrit produiront les mêmes données). DistillFlow est la première méthode se basant sur des méthode de réécriture pour réduire la redondance dans les Workflows scientiques. Il existe d’autres travaux portant sur l’aide àla conception des workflows. Parmis les travaux d’aide à la conception des workflows, on retrouve aussi [9], dans lequel l’auteur extrait des motifs des spécifications des workflows, qui résument les fonctionnalités des étapes dans ceux-ci. On peut aussi citer les travaux en [15] dans lesquels l’auteur propose des méthodes orientées graphes, pour aider à la conception des workflows, en créant de manière automatique le pipeline associé à partir d’un ensemble d’outils.

Il existe de nos jours de nombreux entrepôts de workflows. Ces entrepôts stockent des workflows pour permettre leur réutilisation. Parmi ces bases de données on peut citer CrowdLabs qui comporte des workflows utilisés pour la visualisation. On peut entre autres citer Kepler ou InforSense, ou enfin et surtout MyExperiment (http ://www.myexperiment.org/) qui est un grand projet sur les sciences de la vie, regroupant plus de 2000 workflows dont la majorité provient du système Taverna. Ce dernier constitue la source des données sur lesquelles nous avons travaillé pendant le stage. Cette partie nous a permis de pouvoir faire un état de l’art sur les techniques existantes d’aide à la conception des workflows scientifiques. La section suivante présentera les objectifs de nos travaux de même que les différentes missions à remplir. Ces approches n’ont pas utilisé les techniques classiques de fouilles de données dans les graphes.

Extraction de motifs fréquents

L’extraction de motifs fréquents a été proposée pour la première fois par Agrawal et al [2] dans le cas de l’analyse du panier de la ménagère sous forme de règles d’association, pour analyser les habitudes d’achat des clients d’un supermarché. De manière formelle une règle d’association se définit ainsi :

Soit I = i1, i2, · · · , in un ensemble d’items et T = t1, t2, · · · , tn un ensemble de transactions telle que ti ⊆ I , une règle d’association est une implication de la forme X → Y où X ∈ T et Y ∈ T et X ∪ Y = ∅.

Cette idée a été adaptée et entendue à différents domaines d’application en prenant en compte non plus en compte les informations de type transactions classiques mais en considérant des données structurées sous forme de graphes ou d’arbres. Les transactions sont alors qualifiées de motifs ou patterns. Nous allons particulièrement nous intéresser à l’extraction de patterns fréquents dans les graphes. L’idée dans la fouille de patterns dans les graphes est donc, à partir d’un ensemble de graphes D, d’extraire des sous-graphes gi , tel que freq(gi) ≥ θ où freq(gi) est le support qui correspond la fraction de graphe de D contenant gi. Cependant, on peut noter que ce problème implique la recherche d’un sous graphe dans un graphe. Or ce problème implique le problème d’isomorphisme de sous-graphe. L’isomorphisme de sous-graphes tel que présenté dans [20], s’énnonce ainsi : étant donné deux graphes G1 = (V1, E1, f1) et G2 = (V2, E2, f2) où fi est une application de Ei dans Vi ×Vi , le problème revient à trouver deux sous-graphes Gs1 = (Vs1, Es1, fs1) et Gs2 = (Vs2, Es2, fs2) respectivement de G1 et G2 et une bijection I12 permettant de mettre en correspondance les sommets de Gs1 et Gs2 de sorte que ceuxci soient identiques. C’est-à-dire que : f1(e1h) = (u1, v1) ∈ Es1 si et seulement si f2(e2h) = (u2, v2) ∈ Es2, où u2 = I12(u1) et v2 = I12(v1).

En étendant le problème à plusieurs graphes, on peut le définir ainsi : étant donné un ensemble de graphes {Gk = (Vk, Ek, fk), k = 1, · · · , n}, le problème d’isomorphisme entre les graphes Gk revient à trouver un sous graphe Gs = (Vs, Es, fs), un ensemble de sous-graphes Gsk = (Vsk, Esk, fsk) et une bijection I pour faire correspondre les sommets des sous-graphes Gsk, k = 1, · · · , n. Le problème de déterminer l’existence d’un isomorphisme entre deux sous-graphes est NPcomplet [20]. Par conséquent, déterminer si deux sous-graphes sont identiques est un problème difficile.

Table des matières

1 Introduction
2 Etat de l’art
2.1 Conception des workflows scientifiques
2.2 Extraction de motifs fréquents
2.2.1 Méthodes et leurs applications
2.2.2 Mesures de qualité
3 Identification des modules
3.1 Le problème de l’identification des modules
3.2 Propositions de stratégies d’étiquetage
3.2.1 Similarité de noms des processeurs
3.2.2 Exploitation du contenu des processeurs
3.2.3 Prise en compte des différences dans le contenu des processeurs
3.2.4 Exploitation conjointe des noms et des contenus
4 Évaluation d’algorithmes d’extraction de motifs fréquents dans les workflows scientifiques
4.1 Contexte
4.2 Analyse en tenant compte des critères structurels : Taille des motifs et taille de l’ensemble résultat
4.3 Comparaison en tenant compte de l’intérêt des motifs
4.3.1 Comparaison en utilisant l’indice de Shannon
4.3.2 Comparaison en utilisant la mesure du cosinus
4.4 Analyse de l’intérêt des motifs pour l’utilisateur
4.5 Particularité des workflows scientifiques
5 Conclusion

Lire le rapport complet