apprentissage multi-instances, séquences protéiques, prédiction de la résistance aux rayonnements ionisants chez les bactéries In Multiple Instance Learning (MIL) problem for sequence data, the learning data consist of a set of bags where each bag contains a set of instances/sequences. In some real world applications such as bioinformatics comparing a random couple of sequences makes no sense. In fact, each instance of each bag may have structural and/or functional relationship with other instances in other bags. Thus, the classification task should take into account the relation between semantically related instances across bags. In this paper, we present ABClass, a novel MIL approach for sequence data classification. Each sequence is represented by one vector of attributes extracted from the set of related instances. For each sequence of the unknown bag, a discriminative classifier is applied in order to compute a partial classification result. Then, an aggregation method is applied in order to generate the final result. We applied ABClass to solve the problem of bacterial Ionizing Radiation Resistance (IRR) prediction. The experimental results were satisfactory. multiple instance learning, protein sequences, prediction of bacterial ionizing radiation resistance 1

Une séquence est une liste ordonnée d’évènements. Un évènement peut être représenté comme une valeur symbolique, une valeur numérique, un vecteur de valeurs ou un type de données complexe [ 19 ]. Il existe de nombreux types de séquences comme les séquences symboliques, les séries temporelles simples et les séries temporelles multivariées [ 19 ]. Dans notre travail, nous nous intéressons aux séquences symboliques puisque les séquences protéiques sont décrites à l’aide de symboles (acides aminés). On note l’alphabet défini par un ensemble fini de caractères ou de symboles. Une séquence symbolique simple est donc définie comme une liste ordonnée de symboles de . Soit BD une base de données d’apprentissage qui contient un ensemble de n sacs étiquetés : BD = f(Bi; Yi); i = 1; 2 : : : ; ng où Yi = f 1; 1g est l’étiquette du sac Bi. Les instances de Bi sont des séquences et sont notées Bij . Formellement Bi = fBij ; j = 1; 2 : : : ; mBig, où mBi est le nombre total d’instances dans le sac Bi. Nous notons que les sacs ne contiennent pas nécessairement le même nombre d’instances. Le problème étudié dans ce travail consiste à apprendre un classifieur MI à partir de BD. Étant donné un sac inconnu Q = fQk; k = 1; 2 : : : ; qg, où q est le nombre total d’instances dans Q, le classifieur doit utiliser les séquences dans ce sac et celles dans chaque sac de BD afin de prédire l’étiquette de Q.

Nous notons qu’il existe une relation notée < qui relie les instances à travers les différents sacs. Elle est définie en fonction du domaine d’application. Pour représenter cette relation, nous optons pour une représentation à base d’indice. Nous notons que cette notation ne signifie pas que les instances sont ordonnées. En fait, une étape de prétraitement attribue un indice aux instances de chaque sac selon la façon suivante : chaque instance Bij d’un sac Bi est reliée par < à l’instance Bhj d’un autre sac Bh dans BD. Une instance peut ne pas avoir d’instances correspondantes dans certains sacs, c’est-à-dire qu’une séquence est liée à zéro ou une séquence par sac. La relation < pourrait être généralisée pour traiter les problèmes où chaque instance a plus d’une instance cible par sac. La notation d’indice telle que décrite précédemment ne sera pas appropriée dans ce cas. Plusieurs algorithmes d’apprentissage MI ont été proposés incluant Diverse Density (DD) [ 15 ], MI-SVM [ 3 ], Citation-kNN [ 18 ] et MILKDE [ 8 ]. Un état de l’art des approches d’apprentissage MI avec une étude comparative pourrait être trouvé dans [1] et [2].

L’idée principale de l’approche DD [ 15 ] est de trouver les points qui sont proches d’au moins une instance de chaque sac positif et qui sont loin des instances des sacs négatifs. On cherche ensuite le point optimal selon une mesure définie par les auteurs et qui porte le même nom que l’algorithme. Cette mesure prend en considération le nombre de sacs positifs ayant des instances proches du point en question et la distance entre ce point et les instances négatives. L’approche MI-SVM [ 3 ] est une adaptation des machines à vecteurs de support au problème d’apprentissage MI. Elle reformule la maximisation de la marge des sacs en prenant en considération les contraintes du MI. Pour un sac positif, seule l’instance ayant la plus grande marge a un impact sur l’apprentissage. Les autres instances sont ignorées. MISMO utilise l’algorithme SMO [ 16 ] basé sur l’apprentissage par machines à vecteurs de support en conjonction avec un noyau MI [ 11 ]. L’algorithme Citation-kNN [ 18 ] est basé sur la règle des plus proches voisins et sur le concept de citation et de référence. Un sac est étiqueté non seulement selon ses voisins (les références), mais aussi selon les sacs qui le reconnaissent comme leur voisin (les citeurs). Dans [ 8 ], les auteurs présentent l’algorithme MILKDE qui se base sur l’identification des instances les plus représentatives dans chaque sac positif en utilisant un calcul de vraisemblance. Dans [ 20 ], les auteurs traitent l’apprentissage MI sur des données structurées. Ils décrivent trois scénarios des relations existantes entre les données : I-MILSD où les relations sont disponibles au niveau des instances, B-MILSD où les relations sont au niveau des sacs et BIMILSD où les relations sont disponibles au niveau des instances et des sacs.

L’application des algorithmes MI présentés ci-dessus sur des sacs de séquences entraîne deux problèmes. Le premier problème réside dans la représentation des données à traiter. Elles sont représentées dans un format attributvaleur. Dans le cas des séquences, la technique la plus utilisée pour transformer les données en un format attributvaleur consiste à extraire des motifs qui servent comme attributs. Nous notons que trouver une description uniforme de toutes les instances en utilisant un ensemble de motifs n’est pas toujours une tâche facile. En apprentissage MI, cela pourrait conduire à une matrice énorme et creuse. Par exemple, dans [ 3 ], l’évaluation empirique est effectuée sur la base de données TREC9 pour la catégorisation des documents. Les termes sont utilisés pour présenter le texte. On obtient alors une matrice creuse et de grande dimension . Dans [ 17 ] et [ 20 ], un ensemble de séquences protéiques a été utilisé dans l’évaluation empirique. L’objectif est d’identifier les protéines dites Trx-fold. Chaque séquence est considérée comme un sac et certaines de ses sous-séquences sont considérées comme des instances. Ces sous-séquences sont alignées et représentées en utilsant 8 attributs numériques [ 13 ] [ 17 ]. Le deuxième problème avec les algorithmes présentés est qu’ils ne traitent pas les relations inter-sacs qui peuvent exister entre les instances, à l’exception des algorithmes dans [ 20 ]. Dans [ 20 ], le score d’alignement est utilisé pour identifier les relations entre les protéines : si le score entre une paire de protéines dépasse 25, alors les auteurs considèrent qu’il existe un lien entre elles. Seul l’algorithme B-MILSD qui traite l’information au niveau du sac a été utilisé dans l’étude expérimentale. Dans un travail antérieur, nous avons proposé l’algorithme MIL-ALIGN [ 4 ] qui traite le problème de la prédiction de la RRI chez les bactéries. Il utilise une technique d’alignement pour discriminer les séquences puis applique une méthode d’agrégation pour générer le résultat de prédiction final. Dans ABClass, nous représentons les séquences en utilisant un format attribut-valeur qui prend en compte les dépendances entre les instances liées à travers les sacs.

La méthode la plus simple qu’on peut utiliser pour résoudre le problème de l’apprentissage MI pour les séquences est d’utiliser des classifieurs MI standards. Cependant, les algorithmes MI couramment utilisés nécessitent une description en format attribut-valeur uniforme pour toutes les instances des différents sacs. L’approche naïve contient deux étapes. La première est une étape de prétraitement qui transforme l’ensemble des séquences en une matrice attribut-valeur où chaque ligne correspond à une séquence et chaque colonne correspond à un attribut. La deuxième étape consiste à appliquer un classifieur MI existant. La Figure 1 illustre l’approche naïve pour l’apprentissage MI pour les séquences. La technique la plus utilisée pour transformer les séquences en un format attribut-valeur consiste à extraire des motifs qui seront utilisés comme attributs. Nous notons que trouver une description uniforme de toutes les instances utilisant un ensemble de motifs n’est pas toujours une tâche facile. Puisque notre approche naïve prend en compte les relations entre les instances à travers les sacs, l’étape de prétraitement extrait les motifs à partir de chaque ensemble d’instances reliées. L’union de ces motifs est ensuite utilisée comme attributs pour construire une matrice attribut-valeur où chaque ligne correspond à une séquence. La présence ou l’absence d’un attribut dans une séquence est notée respectivement par 1 ou 0. Il est utile de mentionner que seul un sous-ensemble des attributs utilisés est représentatif pour chaque séquence. Par conséquent, nous pouvons avoir une grande matrice creuse.

Nous appliquons l’approche naïve sur notre exemple illustratif. Nous supposons que les attributs sont des sous-séquences (longueur minimale = 2) qui se trouvent au moins dans deux instances. Soit listeM otif s1 = fAB; CD; Y Zg la liste des motifs extraits à partir des instances fBi1; i = 1; : : : ; 4g. listeM otif s2 = fEF; GHg est la liste des motifs extraits à partir de fBi2; i = 1; : : : ; 5g et listeM otif s3 = fKLg est la liste des motifs extraits à partir de fBi3; i 2 f1; 4; 5gg. L’union de listeM otif s1, listeM otif s2 et listeM otif s3 produit la liste listeM otif s = fAB; CD; Y Z; EF; GH; KLg. Afin de coder les séquences de la base d’apprentissage, nous générons la matrice attribut-valeur suivante notée M : 0 1

B 1 M =B 0

B @ 1 Afin d’éviter l’utilisation d’un grand vecteur d’attributs pour décrire les séquences, nous présentons ABClass (pour Across Bag Sequences Classification), une nouvelle approche qui prend en compte les relations entre les instances à travers les sacs. La Figure 2 illustre le principe de ABClass. Durant la phase d’apprentissage, chaque ensemble d’instances reliées sera représenté par son propre vecteur de motifs. Cela réduit le nombre d’attributs qui ne sont pas représentatifs de la séquence traitée. En appliquant un classifieur classique (mono-instance) sur chaque vecteur d’attributs, un modèle de classification est construit. Durant la phase de prédiction, des résultats de prédiction partiels sont produits pour chaque instance du sac inconnu. Ces résultats sont ensuite agrégés pour avoir le résultat final. Lors de l’exécution de l’algorithme, nous allons utiliser les variables suivantes : — Une matrice M pour stocker les données codées de la base d’apprentissage. — Un vecteur QV pour stocker les données codées du sac à prédire. — Un vecteur P V pour stocker les résultats de prédiction partiels.

ABClass est décrit dans l’Algorithme 1. La fonction SéqLiéesEntreSacs regroupe les instances liées à travers les sacs dans des listes. Informellement, les principales étapes de l’algorithme ABClass sont les suivantes : 1. Pour chaque séquence Qk du sac inconnu Q, les instances reliées à travers les sacs sont regroupées dans une liste (lignes 1 et 2). 2. L’algorithme extrait des motifs de la liste des instances regroupées. Ces motifs sont utilisés pour coder les instances afin de créer un modèle discriminant (lignes 3 à 5). 3. ABClass utilise les motifs extraits pour représenter l’instance Qk du sac inconnu dans un vecteur QVk, puis le compare avec le modèle correspondant. Le résultat de la comparaison est stocké dans le k ime élément du vecteur P V (lignes 6 et 7). 4. Une méthode d’agrégation est appliquée à P V pour calculer le résultat final P (ligne 9) qui consiste en une étiquette positive ou négative.

Algorithm 1 L’algorithme ABClass Entrée: Base d’apprentissage BD = f(Bi; Yi)ji = 1; 2; : : : ; ng , Sac inconnu Q = fQkjk = 1; 2; : : : ; qg Sortie: Résultat de prédiction P 1: Pour chaque Qk 2 Q Faire 2: listeSeqLieesk SeqLieesEntreSacs(k; DB) 3: listeM otif sk

extraireM otif s(listeSeqLieesk) 4: Mk coderDonnees(listeM otif sk; listeSeqLieesk) 5: M odelek genererM odele(Mk) 6: QVk coderDonnees(listeM otif sk; Qk) 7: P Vk appliquerM odele(QVk; M odelek) 8: Fin 9: P Agregation(P V ) 10: Retourner P Nous appliquons l’approche ABClass sur notre exemple illustratif. Puisque le sac à prédire contient 3 instances Q1, Q2 et Q3, nous avons besoin de 3 itérations suivies d’une étape d’agrégation.

Itération 1 : L’algorithme regroupe l’ensemble des instances reliées et extrait les motifs correspondants. listeSeqLiees1 = fB11; B21; B31; B41g

listeM otif s1 = fAB; CD; Y Zg Ensuite, il génère la matrice attribut-valeur M1 décrivant les séquences liées à Q1 .

AB 0 1 M1 =B 1 @ 0 1 Le pourcentage d’éparsité de la matrice M1 est réduit à 33% car il n’est pas nécessaire d’utiliser les motifs extraits des instances fBi2; i = 1; ::; 5g et fBi3; i 2 f1; 4; 5gg pour décrire les instances fBi1; i = 1; ::; 4g. Un modèle est ensuite créé en utilisant les données codées et un vecteur QV1 est généré pour décrire Q1. En appliquant le modèle au vecteur QV1, on obtient le premier résultat de prédiction partiel et on le stocke dans le vecteur P V .

P V1

appliquerM odele(QV1; M odele1) Itération 2 : La deuxième itération concerne la deuxième instance Q2 du sac à prédire. Nous appliquons les mêmes instructions que celles décrites dans la première itération. listeSeqLiees2 = fB21; B22; B32; B42; B52g listeM otif s2 = fEF; GHg L’étape d’agrégation est finalement utilisée pour générer la décision finale de prédiction en utilisant les résultats partiels. Nous optons pour le vote majoritaire. 5

Nous utilisons la technique d’évaluation Leave-One-Out (LOO) dans nos expérimentations. Afin d’évaluer l’approche naïve et l’approche ABClass, nous codons d’abord les séquences protéiques de chaque sac en utilisant un ensemble de motifs générés par une méthode d’extraction de motifs existante. Nous utilisons la méthode DMS [ 14 ] pour l’extraction des motifs. DMS permet de construire des motifs pouvant discriminer une famille de protéines d’une autre. Elle identifie d’abord les motifs dans les séquences protéiques. Ensuite, les motifs extraits sont filtrés afin de ne conserver que les motifs discriminants et minimaux. Une sous-chaîne est considérée comme discriminante entre la famille F et les autres familles si elle apparaît dans F significativement plus que dans les autres familles. DMS extrait des motifs selon deux seuils et où est le taux minimum d’occurrences des motifs dans les séquences d’une La Table 1 représente pour chaque paramètre d’extraction le nombre de motifs (longueur minimale = 3) extraits à partir de chaque ensemble de séquences de protéines orthologues. Pour le paramètre S5 ( = 1 et = 0), aucun motif fréquent et strictement discriminant n’a été trouvé pour la plupart des protéines. C’est pourquoi nous n’allons pas utiliser ces valeurs de et pour le reste des expérimentations. Nous notons que le nombre de motifs extraits augmente pour les valeurs élevées de et les valeurs faibles de . Comme présenté dans la Table 1, le nombre de motifs non fréquents et non discriminants est très élevé. Afin de coder les données dans l’approche naïve, on utilise l’union des motifs comme attributs. Par conséquent, la matrice attribut-valeur est grande et creuse. Nous montrons dans la Table 1 le taux d’éparsité de la matrice qui mesure le pourcentage des éléments nuls par rapport au nombre total des éléments. L’éparsité est généralement proportionnelle au nombre de motifs utilisés. Par exemple, Elle va de 73.9% avec 671 motifs à 91.1% avec 8077 motifs. La Figure 3 montre les taux de bonne classification obtenus en appliquant l’approche naïve et l’approche ABClass. Elle montre l’impact de l’ensemble des motifs utilisés dans l’étape de prétraitement sur les résultats de prédiction. Par exemple, en utilisant le classifieur MISVM, la précision varie de 53.5% à 78.5%. Bien que les motifs extraits en utilisant le paramètre S1 soient discriminants, l’approche naïve ne fournit pas globalement de bons résultats pour ce paramètre. La raison pourrait être que le nombre de motifs discriminants pour certaines protéines est très faible (limité à 10 motifs au maximum). En utilisant l’approche naïve, le meilleur résultat est fourni par le classifieur MISMO.Les résultats des autres classifieurs MI dépendent des motifs utilisés. La plupart d’entre eux fournissent un bon résultat en utilisant le paramètre S3 (motifs non discriminants avec une fréquence moyenne). Le nombre de motifs extraits par protéine en utilisant ce paramètre est compris entre 228 et 1505. Ce nombre de motifs est acceptable pour coder une séquence protéique.

L’approche ABClass fournit globalement de bons résultats puisque le taux de bonne classification le plus faible est 89.2%. Cela montre que notre approche est efficace. Le meilleur résultat est atteint en utilisant le classifieur J48 et les paramètres d’extraction de motifs S3 et S4. En utilisant ces deux paramètres, un grand nombre de motifs non discriminants est extrait. La Table 2 représente le taux des modèles de classification qui contribuent à prédire la bonne classe de chaque bactérie en utilisant l’approche ABClass. Nous présentons ce taux pour les deux paramètres d’extraction de motifs qui fournissent les meilleurs résultats, à savoir S3 et S4. Le taux des modèles réussis pour B1, B11 et B15 est marqué en gras parce que ces trois bactéries génèrent toujours des taux faibles comparés au taux des autres bactéries. Nous notons que les résultats sont similaires à ceux trouvés dans [ 4 ]. Ces résultats peuvent aider à comprendre certaines caractéristiques des bactéries étudiées. En particulier M. radiotolerans (B11) et B. abortus (B15) présentent les taux les plus bas. Une explication biologique possible est fournie dans [ 4 ] et [ 21 ]. 6