Résumé. L'avènement des biotechnologies nouvelles a permis, au cours des dernières années, d'accumuler des données sur les génomes des agents pathogènes épidémiologiques. Par contre l'exploitation des données génomiques n'as pas suivi le rythme des découvertes, alors la fouille de données biologiques, particulièrement à caractère épidémiologique s'est imposée d'elle-même afin d'aider à trouver des éléments de réponse aux questions que se pose l'épidémiologiste concernant des pathologies particulières. D'où, la problématique abordée par cette étude qui est la fouille de données biologiques du Mycobacterium Tuberculosis responsable de la tuberculose. Nous proposons un processus de fouille de données assez novateur pour générer des connaissances qui vont êtres profitables et exploitables à deux niveaux : • Profitables au spécialiste du domaine, à travers l'extraction de motifs en particulier les règles d'association qui aident à mieux comprendre la pathologie. • Ensuite, ces règles d'association extraites sont modélisées par le principe booléen adopté par la machine cellulaire CASI (Cellular Automaton for Symbolic Induction). Le but de cette modélisation par le principe booléen étant de réduire la complexité de stockage et le temps de réponse.
La biotechnologie a permis, au cours des dernières années, d'améliorer les
connaissances sur le génome des agents pathogènes épidémiologiques, et de
développer des moyens de lutte efficace contre ces épidémies. Actuellement, des
dizaines de génomes ont été révélés et ont permis de constituer des banques de données
biologiques énormes. De ce fait, les quantités de données brutes disponibles sont déjà
trop importantes pour pouvoir être analysées manuellement par les méthodes
épidémiologiques de surveillance et d’analyse. Du fait de l’inefficacité de ces méthodes
due à la variété des données biologiques, et à la nature même des épidémies, une
nouvelle approche est utilisée : c’est la fouille de données biologiques relatives aux
épidémies [
Sur un terrain, purement épidémiologique, il y a une pathologie qui continue à faire
des ravages et se trouve classée deuxième en mortalité après le sida : c’est la
Tuberculose. Elle est l’un des plus grands fléaux de l'humanité qui entraîna en l'an
2000 près de 10 millions de nouveaux cas et plus de trois millions de morts chaque
année dans le monde [
En effet, cette maladie infectieuse est provoquée par la pénétration dans l’organisme
d’une bactérie appelée Mycobacterium Tuberculosis. Dans la pratique, il existe un
Complexe Tuberculosis dont le Mycobacterium Tuberculosis est l’agent typique
responsable de la tuberculose humaine [
M. M.
Tuberculosis Africanum
M.
Bovis
M. M.
Bovis BCG Canetti
M.
Microti
En 1998, la première séquence complète du génome de Mt H37RV a été réalisée et a
permis de dégager des caractéristiques propres aux mycobactéries dont les plus
importantes sont les suivantes [
Tous ces éléments descriptifs de ce génome sont autant chacun un gisement qu’on
exploite en fouille de données [
3
Donc, la problématique abordée dans ce papier, est la fouille de données biologiques se rapportant au Mycobactérium Tuberculosis à l’aide de tous les éléments d’informations cités auparavant à savoir : les gènes, les protéines, les RD, et les MIRU. Cette fouille se veut d’être une fouille de données hétérogènes.
Cette étude prendra en compte toutes les souches de la bactérie dont l’annotation a été complètement finie ou en projet de séquençage. Ce gisement de données sera plus conséquent s’il renfermera d’avantage de souches annotées, ce qui supposera par la suite, que toute souche nouvellement annotée, alimentera le processus de fouille de données envisagé.
Depuis les premiers projets de séquençage des bactéries, les dispositifs
expérimentaux tels que les séquenceurs automatiques, puces à ADN et autres, ont
permis de constituer des bases de données de séquences de génomes complets. Il fallait
donc exploiter ces données, identifier les gènes, les protéines qu’ils produisent, et
identifier leurs fonctions, pour comprendre les mécanismes de la bactérie. De plus, la
variété et la disponibilité des données biologiques (séquences ADN, Protéines, Puce
ADN, ….) et par la même des banques de données biologiques (NCBI, EMBL,
GenBank….), ont incité à les valoriser. Différents travaux promoteurs et novateurs, en
fouilles de données biologiques ont été faits en se basant essentiellement sur les
génomes et les cohortes [
En génomique : Pour identifier des gènes, comparer des séquences (rechercher des
similarités) [
En fouille de cohortes : Les cohortes ont souvent été utilisées dans le cas des
épidémies [
Nous nous proposons d’étudier les aspects physiologiques fondamentaux liés à la génomique de cette bactérie modèle, le Mycobacterium Tuberculosis. Ensuite étudier les outils de fouille de données pour l’extraction des connaissances et d’en dégager une approches expérimentable.
En premier, nous avons établi un état de l’art de la fouille des données avec certains détails d’une technique à une autre et qui ne sont pas forcement en rapport direct avec notre étude. Ensuite, une étude comparative des différents outils et méthodes existants a été faite afin d’utiliser la plus adaptée à l’objet de notre étude.
Deuxièmement, nous avons abordé l’étude de l’agent pathogène, afin de cerner la nature et le type de données biologiques qui nous intéressent et ainsi pouvoir localiser nos sources de données expérimentales.
Troisièmement, nous avons établi notre propre démarche expérimentale par un
processus de fouille de données pour la génération des connaissances à partir de
données biologiques. Ces connaissances vont êtres profitables et exploitables à deux
niveaux :
1. En premier, profitables au spécialiste du domaine pour la compréhension de
la pathologie.
2. En second, exploitables par la machine cellulaire CASI [
Ce processus informatique ainsi établi procède en deux étapes, une fouille de données
est faite dans un premier temps en utilisant l’algorithme Apriori et donnera des règles
d’association, ensuite et dans un deuxième temps produire des règles booléennes
inductives qui vont alimenter la base de connaissances de la machine cellulaire CASI,
cette machine développée pour l’acquisition automatique incrémentale de
connaissances par induction et la prédiction par déduction [
Ainsi, notre contribution a adopté la démarche suivante : 1. Etude et sélection des données biologiques relatives au Mycobactérium
Tuberculosis ; 2. Extraction des motifs fréquents et des règles d’association respectives ; 3. Production des règles booléennes inductives pour la machine cellulaire
CASI.
Notre système est composé de deux grands modules, le premier produit des règles d’association et les transmet au deuxième module (BRI) pour générer des règles booléennes basées sur le principe de la machine cellulaire CASI.
d’association. 5
NCBI SANGER ……
Gènes associés Protéines associées RD MIRU
Données structurées
Règles d’association
Règles.
Transitoires
Graphe d’induction
Boolean Rules Induction
FAITS CELFACT REGLES CELRULE
CASI Knowledge
Base PSrééletrcatiitoenm, ent .Transformation PErvoadluuacttiioonn. Transformation dPG’rrioandpduhucecttiioonn Représentation Intégration Cellulaire
Les règles d’association produites sont transformées selon le principe suivant : Les items de Antécédent vont servir à constituer la Prémisse de la règle ; Les items de Conséquent vont servir à créer la Conclusion de la règle.
Cette transformation sert à produire des règles transitoires nécessaires à la production d’un graphe d’induction selon le principe suivant : Un sommet désigne un noeud sur lequel on fait un test, avec les résultats possibles binaires ou à valeurs multiples. Ainsi le graphe d’induction permettra de produire les règles cellulaires sous la forme :
Ri : Si Prémissei Alors Conclusioni Avec une représentation cellulaire selon le principe suivant : les items de Prémissei et Conclusioni vont constituer les faits : FAITS. les Ri vont constituer les règles : REGLES.
Ces règles produites seront intégrées dans la base de connaissances de CASI pour exploitation en inférence.
CASI (Induction Symbolique par Automate Cellulaire) est un automate cellulaire qui simule le principe de fonctionnement de base d’un Moteur d’Inférence en utilisant deux couches finies d’automates finis. La première couche, CELFACT, pour la base des faits et, la deuxième couche, CELRULE, pour la base de règles. Chaque cellule au temps t+1 ne dépend que de l’état des ses voisines et du sien au temps t. Dans chaque couche, le contenu d’une cellule détermine si et comment elle participe à chaque étape d’inférence : à chaque étape, une cellule peut être active (1) ou passive (0), c’est-à-dire participe ou non à l’inférence. Le principe adopté est simple :
Toute cellule i de la première couche CELFACT est considérée comme fait établi si sa valeur est 1, sinon, elle est considérée comme fait à établir. Elle se présente sous trois états : état d’entrée (EF), état interne (IF) et état de sortie (SF).
Toute cellule j de la deuxième couche CELRULE est considérée comme une règle candidate si sa valeur est 1, sinon, elle est considérée comme une règle qui ne doit pas participer à l’inférence. Elle se présente sous trois états : état d’entrée (ER), état interne (IR) et état de sortie (SR). Les matrices d’incidence RE et RS représentent la relation entrée/sortie des Faits et sont utilisées en chaînage avant et en chaînage arrière en inversant leur ordre.
La dynamique de l’automate cellulaire, pour simuler le fonctionnement d’un Moteur d’Inférence, utilise deux fonctions de transitions δfact et δrule, où δfact correspond à la phase d’évaluation, de sélection et de filtrage, et δrule correspond à la phase d’exécution.
La fonction de transition δfact :
δfact (EF, IF, SF, ER, IR, SR) = (EF, IF, EF, ER+(RET.EF), IR, SR) La fonction de transition δrule : δrule (EF, IF, SF, ER, IR, SR) = (EF+(RS.ER), IF, SF, ER, IR,^ER), où la matrice RET désigne la transposée de RE et ^ER désigne la négation du vecteur booléen ER.
Le processus de fouille de données adopté par notre système est composé de 6 étapes majeures :
A partir des banques de données (NCBI, ...), il y’a récupération des informations
biologiques relatives aux souches mentionnées ci-dessous, sous leurs formats
originaux. Les agents pathogènes (souches) ciblés par cette étude sont ceux dont
l’annotation a été finie à savoir : Mt H37Rv, Mt CDC1551, Mt F11, Mt H37Ra [
La transformation des données du format original vers un formalisme base de données (attribut, valeur), est faite. De plus à partir des informations relatives aux RD et MIRU des séquences en question, il est défini d’autres caractéristiques calculables ou non, s’en suivra alors une «binarisation».
La recherche des Items, des Itemsets et des règles d’association, est faite par
l’algorithme Apriori [
7
Les règles trouvées sont transformées puis représentées selon un formalisme transitoire aidant à la production d’un graphe d’induction. Ainsi la règle d’association Ri se verra traduite en une règle booléenne transitoire selon le principe suivant : (Ri, Antécédent, Conséquent, support, confiance, note) (Ri , Prémissei (Antécédent ) , Conclusioni ( Conséquent ))
Un graphe d’induction est construit selon le principe suivant : Un sommet désigne un noeud sur lequel on fait un test, avec les résultats possibles binaires ou à valeur multiple.
Génération des règles cellulaires à partir du graphe d’induction sous la forme :
Ri : Si Prémisse (Antécédent) alors Conclusion (Conséquent) où Prémisse est composée des items (Itemset) de l’Antécédent de la règle d’association et la conclusion est composée des items (Itemset) de Conséquent de la règle d’association.
Représentation cellulaire : Les règles générées auparavant (6.1) sont représentées en couches cellulaires. Schématiquement nous aurons : {Ri} REGLES et {Prémissei , Conclusioni } FAITS
Ainsi, la machine cellulaire intégrera et exploitera la représentation cellulaire et les matrices d’E/S à travers une inférence en chaînage avant pour enrichir la base de connaissances.
La dynamique de la machine cellulaire utilise les deux fonctions de transition citées auparavant (4.2).
Le processus général que notre système d’apprentissage applique à un échantillon est illustré par un exemple à partir de la 3ème étape. Nous supposons avoir obtenu les 4 règles d’association suivantes, avec les gènes (aceA, pstS, rpsG, aroK,…..etc) : 3eme étape : Production des règles d’associations (R1,{aceA-2=1}, {pstS-3=0}, 45%,77%) (R2,{aceA-2=0}, {rpsG=1, aroK=1}, 80%,95%) (R3,{aceA-2=0, phhB=1}, {argK=1}, 80%,70%)
(R4,{aceA-2=0, phhB=0}, {argK=0}, 45%,77%) 4eme étape : Transformation
R1,{aceA-2=1}, {pstS-3=0} R2,{aceA-2=0}, {rpsG=1, aroK=1} R3,{aceA-2=0, phhB=1}, {argK=1}
R4,{aceA-2=0, phhB=0}, {argK=0} 5eme étape : Production du graphe d’induction s0
aceA-2 s1 pstS-3=0 ahpC s2 rpsG=1 aroK=1 phhB s3 argk=1 s4 argk=0 folC 6eme étape : Représentation Cellulaire
Génération des règles cellulaires R1: Si {s0} Alors {pstS-3=0, s1} R2: Si {s0} Alors {rpsG=1, aroK=1, s2} R3: Si {s2} Alors {argK=1, s3}
R4: Si {s2} Alors {argK=0, s4} Représentation des règles cellulaires
Les couches CELFACT et CELRULE.
CELFACT
Pour CELRULE : Toute cellule de CELRULE est considérée règle candidate, c'est-à-dire participe à l’inférence si sa valeur=1, sinon, si sa valeur=0.
Les matrices d’E/S RE s0 pstS-3=0 s1 rpsG=1 aroK=1 s2 argK=1 s3 argK=0 s4
R1 1
R2 1
R3
R4 1 1
RS s0 pstS-3=0 s1 rpsG=1 aroK=1 s2 argK=1 s3 argK=0 s4
R1
R2
R3
R4 Pour les matrices d’E/S :
La matrice d’entrée RE : si le fait i∈ à Prémisse de Rj alors RE(i,j) =1
La matrice de sortie RS : si le fait i∈ à Conclusion de Rj alors RS(i,j) =1
Le schéma illustré par la figure 3, montre le système en termes de fonctionnalités sans pour autant fixer une quelconque chronologie pour les opérations.
BIODM
Frame.One Explore_ Biological_Data
Experiment Cellular_Rules_ Production
Find_Association_ Rules
Save_ Experimentation Boolean_Rules_ Graph_Induction_ Cellular_Rules_ Induction Creation Generation
Data_Base_ Procedures
Association_
Rules_Procedures
Fig. 3 : Architecture du système
C’est la classe qui lance toute l’application. Elle ne contient qu’une instance de la classe FRAME_ONE.
C’est la fenêtre principale de l’application. C’est la classe la plus importante car elle gère toutes les opérations que l’on peut effectuer.
Visualise les données expérimentales pour une possible vérification visuelle avant de lancer l’expérimentation.
Démarre l’expérimentation en demandant à l’utilisateur de sélectionner les fichiers nécessaires. Elle fait appel à des méthodes stockées telles que LECTURE_FICHIER_SEQUENCE, et CALCUL_FREQUENCE, pour le calcul des évaluations des règles.
Recherche les règles d’associations. Elle fait appel à des méthodes stockées dans la classe DATA_BASE_PROCEDURES, et la classe ASSOCIATION_RULES _PROCEDURES. Elle présente les résultats sous la forme textuelle, et permet de sauvegarder l’expérimentation par le biais de la classe SAVE_EXPERIMENT.
Sauvegarde les résultats de l’expérimentation.
Regroupe toutes les méthodes de gestion de la base de données, telles que la création d’une connexion, l’écriture dans une table, les requêtes sur les différentes tables, etc.
Recherche les itemsets, calcule les supports et les fréquences, et produit les règles d’association.
Produit les règles cellulaires et utilisant au besoin les méthodes de stockage des classes GRAPHE_INDUCTION_CREATION et CELLULAR_RULES_GENERATION.
10. Classe BOOLEAN_RULES_INDUCTION Produit les règles booléennes inductives, en utilisant au préalable des méthodes pour la transformation des règles d’association trouvées.
11. Classe GRAPHE_INDUCTION_CREATION Crée le graphe d’induction à l’aide d’un algorithme approprié et des règles d’associations produites à l’étape 9. Ce graphe sera le paramètre d’entrée de la classe CELLULAR_RULES_GENERATION.
12. Classe CELLULAR_RULES_GENERATION Produit les règles cellulaires et les intègre dans la base de connaissances de la machine cellulaire CASI. Cette classe regroupe toutes les méthodes de création des couches CELFACT et CELRULE.
En se basant sur les données expérimentales des souches citées auparavant (4.3 1iere étape), les différentes expériences nous donnent des résultats intéressants qui resterons à consolider avec de nouvelles souches en cours de séquençage et qui seront prises en considération par notre système au fur et mesure de leur publication définitive sur leurs sites d’origines (NCBI, …). Pour le reste, c’est à dire la représentation booléenne (CASI), elle va certainement changer ou plus tôt « évoluer » en fonction des résultats (i.e. règles d’association produites).
Notre étude se voulait être assez novatrice, dans la mesure où nous avons été incités à
utiliser des techniques prouvées de la machine cellulaire CASI [
Un prétraitement simple et minimal de la base de règles d’association, pour sa transformation en matrice binaire selon le principe de couches cellulaires. La facilité d’implémentation des fonctions de transitions δfact et δrule qui sont de basses complexités, efficaces et robustes et concernent des valeurs extrêmes, et bien adaptées aux situations avec beaucoup d’attributs.
La possibilité de description de l’état initial mais aussi de classifier en vu de produire des résultats simples à être insérés et utilisés à nouveau par un système expert classique, grâce notamment au système de prédiction de CASI, composé d’un ensemble de fonctions de transitions et de règles de production simples, et aussi à une facilité de transformation et de simplification des règles à travers la matrice d’incidence RE.