Etude comparée des performances de SVM multi-classes en prédiction de la structure secondaire des protéines

Description
Etude comparée des performances de SVM multi-classes en prédiction de la structure secondaire des protéines Y. Guermeur LORIA-CNRS, équipe ABC Campus Scientifique, BP Vandœuvre-lès-Nancy cedex

Please download to get full document.

View again

of 18
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Career

Publish on:

Views: 10 | Pages: 18

Extension: PDF | Download: 0

Share
Transcript
Etude comparée des performances de SVM multi-classes en prédiction de la structure secondaire des protéines Y. Guermeur LORIA-CNRS, équipe ABC Campus Scientifique, BP Vandœuvre-lès-Nancy cedex Résumé. Les SVM bi-classes, introduites en bioinformatique à la fin des années 90, font aujourd hui référence pour de nombreux problèmes de traitement de séquences biologiques. Les SVM multi-classes, de conception plus récente, sont progressivement appliquées à ces problèmes, singulièrement en biologie structurale prédictive. Dans cet article, nous proposons une étude comparée des performances de trois SVM multi-classes en prédiction de la structure secondaire des protéines. Les modèles impliqués sont celui de Weston et Watkins, celui de Lee et co-auteurs ainsi qu une nouvelle machine nommée M-SVM 2. Cette étude se conçoit comme une étape dans la mise au point d une méthode de prédiction hybride, intégrant systèmes discriminants et génératifs et s appuyant sur une approche hiérarchique du problème. 1 Introduction La biologie moléculaire est un domaine d application de choix pour les modèles de l apprentissage artificiel. Si les problèmes de discrimination qu elle propose font intervenir des données de natures très diverses, un grand nombre d entre eux, souvent parmi les plus importants, relèvent du traitement de séquences. C est en particulier le cas des problèmes de biologie structurale prédictive. L un des plus anciens, qui a résisté à quarante années de recherches intensives, est la prédiction ab initio du repliement des protéines globulaires. Il est ordinairement abordé par le biais d une approche du type diviser pour régner faisant intervenir une sous-tâche nommée prédiction de la structure secondaire. Du point de vue de l apprentissage artificiel, cette tâche de discrimination à catégories multiples est d un intérêt majeur, ceci à plus d un titre. Pour nous restreindre à ce qui fera l objet de cet article, il convient d illustrer cet intérêt en précisant que les principaux modèles connexionnistes discriminants ont été appliqués en prédiction de la structure secondaire, de même que les machines à vecteurs support (SVM). Dans ce domaine, les perceptrons multi-couches (PMC) et leurs variantes récurrentes constituent l état de l art depuis environ vingt ans. Ils ont été rejoints récemment par les SVM. Le choix de ce problème est donc particulièrement indiqué pour réaliser une étude comparative de SVM multi-classes (M-SVM). C est précisément ce que propose cet article. Les trois machines considérées sont la M-SVM de Weston et Watkins (1998), celle de Lee et al. (2004) Comparaison de M-SVM en prédiction de la structure secondaire et une nouvelle machine nommée M-SVM 2 (Monfrini et Guermeur, 2008). L objectif final est la mise au point d une méthode de prédiction hybride, intégrant systèmes discriminants et génératifs et s appuyant sur une approche hiérarchique du problème. Le plan de l article est le suivant. La section 2 présente le problème de la prédiction de la structure secondaire des protéines, ainsi que les méthodes constituant l état de l art. La description des trois M-SVM impliquées dans l étude comparative fait l objet de la section 3. Le noyau à fonction radiale de base (RBF) qu elles utilisent toutes est présenté dans la section 4. La question de la sélection de modèle est étudiée dans la section 5. La section 6 est dédiée à l étude comparative proprement dite. Enfin, la section 7 expose nos conclusions et nos perspectives de recherche. 2 Prédiction de la structure secondaire des protéines Dans cette section, nous présentons le problème de traitement de séquences biologiques sur lequel porte cette étude comparative. 2.1 Présentation du problème Connaître la structure d une protéine est un prérequis pour comprendre précisément sa fonction. Les projets de séquençage à grande échelle qui se sont multipliés ces dernières années ont permis d obtenir les séquences d un très grand nombre de gènes et par suite celles d un très grand nombre de protéines. Le phénomène a été accéléré par l apparition de nouvelles techniques de séquençage à la fois rapides et à bas coût. Malheureusement, le nombre de structures connues n a pas suivi la même progression. En effet, les méthodes expérimentales disponibles pour déterminer la structure tridimensionnelle (tertiaire), la cristallographie par rayons X ou radiocristallographie et la spectroscopie par résonance magnétique nucléaire (RMN) demandent beaucoup d efforts ou sont tout simplement inutilisables. Ainsi, certaines protéines ne cristallisant pas ne peuvent relever de la radiocristallographie. De ce fait, prédire la structure tertiaire des protéines ab initio, c est-à-dire à partir de la seule séquence (structure primaire), est devenu l un des problèmes centraux de la biologie structurale. Au début des années 60, Anfinsen proposa son hypothèse thermodynamique (Epstein et al., 1963), impliquant que la séquence protéique contient suffisamment d information pour garantir un repliement correct à partir d un vaste ensemble d états dépliés. Cette hypothèse s appuyait en particulier sur des expériences de dénaturation-renaturation (Anfinsen et al., 1961). Si le problème considéré peut donc théoriquement être résolu, les difficultés pratiques, mises en évidence par exemple par Karplus et Petsko (1990), sont telles qu il est rarement abordé de manière directe, mais plutôt au travers d une approche du type diviser pour régner. Dans ce contexte, une étape intermédiaire utile est la prédiction de la structure secondaire, qui représente un moyen de simplifier le problème en projetant la structure 3D très complexe sur une dimension, c est-à-dire sur une succession d états conformationnels associés à chaque résidu (acide aminé) de la séquence. La structure secondaire d une protéine est constituée par les motifs réguliers (périodiques) et répétés du repliement de son épine dorsale. Les deux éléments structuraux de base sont l hélice alpha et le brin bêta, auxquels s ajoute une transition apériodique, le coil. La figure 1 propose une représentation schématique de la structure secondaire de Y. Guermeur la protéine G (Derrick et Wigley, 1994), représentation obtenue avec le logiciel RasMol (Sayle et Milner-White, 1995). FIG. 1 Représentation schématique des éléments structuraux de la protéine G. Cette structure est composée de deux parties principales : une hélice alpha, matérialisée en rouge, et un feuillet bêta constitué de quatre brins, en jaune. Si la prédiction de la structure secondaire peut être utilisée pour fournir des contraintes aux méthodes de prédiction ab initio de la structure tertiaire, elle peut également jouer un rôle dans la mise en œuvre des deux autres grandes stratégies de prédiction de la structure tertiaire que sont la reconnaissance de repliement (threading) (voir par exemple Russell et al., 1996; Rost et al., 1997) et la modélisation par homologie/analogie (voir par exemple Boscott et al., 1993; Combet et al., 2002). Considérée comme une tâche de reconnaissance des formes, elle se présente sous la forme d un problème de discrimination à trois catégories consistant à affecter à chaque résidu de la séquence son état conformationnel, en hélice α, brin β ou structure apériodique (coil). 2.2 Etat de l art Les premiers travaux en prédiction de la structure secondaire datent de la fin des années 60. Depuis lors, ce problème a fait l objet de recherches intensives. Il est possible de classer en trois grandes familles les méthodes qui ont été mises en œuvre pour le traiter. Historiquement, les méthodes les plus anciennes sont celles fondées sur l exploitation de propriétés physico-chimiques (Lim, 1974b,a) et celles dites statistiques (Chou et Fasman, 1978; Gibrat et al., 1987), reposant principalement sur l estimation des probabilités conditionnelles des états conformationnels à partir de statistiques d ordres un ou deux calculées sur de petits peptides. Elles ont progressé lentement au cours des années (Gaboriaud et al., 1987; Solovyev et Comparaison de M-SVM en prédiction de la structure secondaire Salamov, 1994; Geourjon et Deléage, 1995), jusqu au moment où elles ont été pratiquement supplantées par des méthodes issues de l apprentissage numérique. Les progrès les plus spectaculaires ont résulté de l introduction dans le domaine de PMC. Dans un premier temps, une transposition relativement simple du système NETtalk a permis à Qian et Sejnowski (1988) de faire passer le taux de reconnaissance (taux de résidus correctement classés) d environ 60% à plus de 64%. Leur architecture doit être évoquée, car elle a été pratiquement systématiquement reprise dans les travaux ultérieurs. Deux PMC sont utilisés en cascade. Le premier, dit séquence-structure , effectue la prédiction de la structure à partir de la séquence, le second, dit structure-structure , lissant la prédiction initiale, en prenant en compte le fait que les états conformationnels des résidus consécutifs sont fortement corrélés. Le remplacement, en entrée du PMC séquence-structure , de la simple structure primaire par un profil d alignement, a eu pour conséquence un accroissement supplémentaire du taux de reconnaissance de plus de 6%, permettant de dépasser pour la première fois la frontière des 70% de résidus correctement classés. Ainsi, la méthode PHD de Rost et Sander (1993), à travers ses développements successifs (Rost et Sander, 1994), a constitué l état de l art pendant la plus grande partie des années 90. Les alignements qu elle utilise sont issus de la base HSSP (Sander et Schneider, 1991; Dodge et al., 1998). Pour un alignement donné, le profil est obtenu en calculant à chaque position les fréquences d apparition des vingt acides aminés. Parallèlement, les systèmes mettant en œuvre des modèles de Markov cachés (HMM), introduits par Asai et al. (1993), ont tiré profit, comme les autres, de l accroissement de la taille de la protein data bank (PDB) (Bernstein et al., 1977; Berman et al., 2000) pour prendre en compte de manière de plus en plus fine les règles syntaxiques régissant l agencement des éléments structuraux. En la matière, la contribution la plus aboutie est probablement constituée par les travaux de Martin et al. (2005); Martin (2005). Actuellement, les meilleurs systèmes de prédiction sont des modèles connexionnistes complexes, intégrant jusqu à plusieurs centaines de réseaux, à propagation avant ou récurrents (Jones, 1999; Baldi et al., 1999; Cuff et Barton, 2000; Petersen et al., 2000; Pollastri et al., 2002). Si la combinaison de modèles permet d améliorer significativement les performances (voir aussi Cuff et Barton, 1999), celles-ci dépendent principalement de la qualité des alignements exploités. Depuis son introduction par Jones (1999) dans le cadre de la méthode de prédiction PSIPRED, l emploi de profils d alignements issus de l algorithme PSI-BLAST (Altschul et al., 1997; Altschul et Koonin, 1998) et s appuyant sur une matrice de scores dépendant de la position (PSSM), est quasi-exclusif. A l inverse, l importance de la nature des réseaux neuronaux apparaît secondaire. On n explique pas le fait que ceux-ci soient souvent largement sur-paramétrés, sans que cela n entraîne pour autant de phénomène de sur-apprentissage (Riis et Krogh, 1996; Guermeur, 1997). Depuis plusieurs années, les taux de reconnaissance les plus élevés rapportés saturent aux environs des 80% de résidus bien classés. De ce fait, le dernier grand article de synthèse que Rost a écrit sur la prédiction de la structure secondaire, (Rost, 2001), demeure aujourd hui encore d actualité. La communauté de la biologie structurale prédictive est en attente d un progrès du même ordre que celui ayant résulté de l emploi de PMC ou d alignements multiples. Un autre phénomène vient expliquer le ralentissement des progrès effectués. Nous avons vu dans la section 2.1 qu il existe trois grandes approches pour réaliser la prédiction de la structure tertiaire : la modélisation par homologie (Sali, 1995), le threading (Lemer et al., 1995; Marin et al., 2002) et l approche ab initio (Jones, 1997; Hardin et al., 2002). Ce sont principalement les méthodes de prédiction ab initio qui utilisent la prédiction de la structure secondaire. Or, on ne fait appel Y. Guermeur à elles que lorsque la modélisation par homologie et le threading ont échoué. La conjugaison de deux facteurs positifs : les progrès méthodologiques et l accroissement continuel des tailles des bases de référence, diminue sensiblement la fréquence de cette situation. De plus, la méthode de prédiction ab initio actuellement la plus performante, ROSETTA (Simons et al., 1999), n est pas fondée sur la prédiction de la structure secondaire. Au contraire, elle a été utilisée par Meiler et Baker (2003) afin d améliorer cette prédiction. La tâche qui nous intéresse a donc perdu, au cours des années, un peu de son importance. Elle pourrait revenir au devant de la scène si une avancée significative avait de nouveau lieu. Naturellement, il est plaisant d imaginer qu une telle avancée puisse résulter de l emploi de méthodes à noyau, et plus particulièrement de M-SVM. A notre connaissance, la première application d une SVM, en l occurence multi-classe, en prédiction de la structure secondaire, était une combinaison de modèles (Guermeur, 2000) (voir aussi Guermeur, 2002). Ces travaux, qui ont produit un gain de performance statistiquement significatif par rapport aux méthodes d ensemble habituellement utilisées dans ce contexte, ont été poursuivis dans (Guermeur et al., 2004), avec le même succès. Parallèlement, Hua et Sun (2001) ont été les premiers à aborder directement le problème. Pour ce faire, ils ont appliqué à des profils d alignements multiples des SVM bi-classes à noyau gaussien sphérique, combinées au moyen de la méthode de décomposition un contre tous (Rifkin et Klautau, 2004) ainsi que d autres méthodes élémentaires fondées sur un graphe de décision. Comme dans le cas de la méthode PHD, leurs alignements multiples étaient issus de la base HSSP, les profils résultant du calcul en chaque position des fréquences des différents acides aminés. Leur conclusion est que leur approche permet d obtenir une très bonne valeur du coefficient Sov (Rost et al., 1994; Zemla et al., 1999) global : 76.2%. La première étude décrivant l application de SVM bi-classes à des profils d alignements issus de PSI-BLAST (toujours dans le cadre de la mise en œuvre de méthodes de décomposition) est due à Kim et Park (2003). Des travaux similaires ont été effectués par Wang et al. (2004). La principale différence par rapport aux précédents réside dans l utilisation d un codage physico-chimique des acides aminés. Le noyau, à l inverse, demeure le même. Le taux de reconnaissance annoncé, 78.4%, est comparable à celui des meilleurs systèmes connexionnistes. Suivant l usage commun, adopté par exemple par le challenge critical assessment of techniques for protein structure prediction (CASP), nous avons considéré jusqu à présent que la prédiction de la structure secondaire était un problème de discrimination à trois catégories. En fait, les programmes d assignation déterminant la structure secondaire à partir de la structure 3D considèrent plus d états conformationnels. Ainsi, le programme DSSP (Kabsch et Sander, 1983), le plus utilisé en pratique, en considère huit, parmi lesquels celui correspondant aux coudes β, désigné par le symbole T, qu une classification en seulement trois catégories associe à la structure apériodique (voir par exemple Cuff et Barton, 1999). Ces coudes β sont prédits au moyen d une SVM par Zhang et al. (2005). Les prédicteurs utilisés sont à nouveau ceux correspondant au profil d alignement obtenu par application de PSI-BLAST plus la structure secondaire prédite par PSIPRED. Une fois de plus, les performances sont encourageantes, alors même que le noyau utilisé repose sur une simple gaussienne sphérique. On trouve plusieurs autres applications des SVM en prédiction de la structure secondaire utilisant des SVM bi-classes et le noyau gaussien standard (voir par exemple Ward et al., 2003; Guo et al., 2004). A l inverse, à notre connaissance, une seule autre équipe a appliqué une M-SVM à ce problème. Nguyen et Rajapakse (2003, 2005) reprennent l architecture introduite par Qian et Sejnowski, consistant à mettre en œuvre en cascade deux Comparaison de M-SVM en prédiction de la structure secondaire systèmes discriminants, l un séquence-structure et l autre structure-structure . Les PMC de la méthode originale sont remplacés par des M-SVM de Crammer et Singer (2001). Ici encore, le noyau utilisé est le noyau gaussien standard. La section suivante présente les M-SVM que nous avons mises en œuvre. 3 Trois modèles de SVM multi-classes Une introduction générale aux M-SVM est un préalable à la caractérisation des trois machines d intérêt dans cet article. 3.1 Présentation générale Il convient en premier lieu de définir les familles de fonctions sur lesquelles s appuient toutes les M-SVM Familles de fonctions H Soit X un espace quelconque et κ un noyau continu, symétrique, semi-défini positif ou noyau de Mercer (1909) sur X. Soit ( H κ,, Hκ ) l espace de Hilbert à noyau reproduisant (RKHS) (Berlinet et Thomas-Agnan, 2004) correspondant. L existence et l unicité de ( Hκ,, Hκ ) sont assurées par le théorème de Moore-Aronszajn (Aronszajn, 1950) (voir aussi Berlinet et Thomas-Agnan, 2004, théorème 3). Le théorème de Mercer nous apprend qu il existe une application Φ de X dans un espace de Hilbert ( E Φ(X ),, ) satisfaisant : (x, x ) X 2, κ (x, x ) = Φ (x), Φ (x ). (1) Par abus de langage, on parlera de l espace de représentation (feature space) pour évoquer l un quelconque des espaces de Hilbert ( E Φ(X ),, ) ainsi définis. Q étant un entier supérieur ou égal à deux, du fait même de la définition d un RKHS, H = (( H κ,, Hκ ) + {1} ) Q est la famille des fonctions à valeurs vectorielles h = (h k ) 1 k Q dont les fonctions composantes sont les combinaisons affines de tailles finies m k de la forme : m k h k ( ) = β ik κ (x ik, ) + b k, i=1 où les x ik sont des éléments de X (les β ik et b k sont des scalaires), ainsi que les limites de ces fonctions lorsque les ensembles {x ik : 1 i m k } deviennent denses dans X au sens de la norme induite par le produit scalaire. Il résulte de l équation 1 que la famille H peut également être considérée comme un modèle affine multivarié sur Φ (X ). Les fonctions h prennent alors la forme suivante : h( ) = ( w k, + b k ) 1 k Q, où les vecteurs w k sont des éléments de E Φ(X ). Ainsi, H κ apparaît comme l espace dual de E Φ(X ) (l espace des formes linéaires sur E Φ(X ) ). Compte tenu de la définition de, Hκ, il s agit même de l espace de Hilbert dual de E Φ(X ). Dans la suite, pour une fonction h donnée, w désignera le vecteur (w k ) 1 k Q de E Q Φ(X ) et b le vecteur (b k) 1 k Q de R Q. On notera H Y. Guermeur l espace produit H Q κ, h = ( w k, ) 1 k Q ses fonctions (considérées comme des fonctions sur Φ (X )) et H sa norme. On prendra h H = Q hk 2 k=1 H κ = Q w k 2, où désigne la norme associée au produit scalaire de E Φ(X ). Pour établir le lien entre une famille de fonctions H pour Q = 2 et la famille de fonctions univariées sur laquelle s appuie la SVM bi-classe de même noyau, il faut considérer l hyperplan affine défini par l équation Q k=1 h k = 0. En notant H la famille des fonctions h réalisables par la SVM, on définit entre H ) et l hyperplan la bijection suivante : h = ( h, h. Ainsi, pour plonger une SVM bi-classe dans le cadre plus général considéré ici, il suffit de réécrire ses paramètres sous la forme w 1 = w = w 2 et b 1 = b = b 2. k= Algorithme d apprentissage Dans ce qui suit, Q étant supposé être supérieur ou égal à trois, nous considérons des problèmes de discrimination multi-classe à Q catégories dont X est l espace de description et Y = [[ 1, Q ]] est l ensemble des catégories. A chaque fonction h de H est associée une règle de décision f de X dans
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks