David Gilbert^*,*** — David Westhead^**,*** —

Janet Thornton^{***,****,*****} — Karine Yvon^*

RESUME. Nous décrivons ici une méthode permettant un filtrage rapide de motifs à partir de descriptions topologiques de structures de protéines. Cette méthode a été implémentée en programmation logique par contraintes sur des domaines finis, et forme la base d’une technique de filtrage de structures de protéines [GWVT00]. Le système est accessible sur le site web de l’Institut Européen de Bio-informatique (http://tops.ebi.ac.uk/tops).

ABSTRACT. We describe a constraint-based method to perform fast matching of motifs with topological descriptions of protein structures. This method has been implemented using finite domain logic programming, and forms the basis of a protein structure comparison technique which we have described elsewhere [GWVT00]. The system is accessible at the web-site of the European Bioinformatics Institute (http://tops.ebi.ac.uk/tops)

1. Motivation 

L’étude des structures atomiques tri-dimensionnelles ou du repliement des molécules de protéines globulaires a toujours été un aspect très important de la biologie moléculaire depuis la détermination expérimentale des premières structures, il y a plus de 30 ans. Ces molécules sont responsables de l’exécution et de la régulation de la plupart des processus essentiels à la vie. Pour ne mentionner que quelques uns de ces processus: les protéines de type enzyme catalysent d’importantes réactions biochimiques, les facteurs de transcription régulent l’utilisation de l’ADN par la cellule, les anticorps du sytème immunitaire reconnaissent les molécules étrangères, etc. La connaissance de ces structures de protéines a permis aux biologistes de, premièrement, mieux comprendre la fonction d’une protéine et comment cette fonction est accomplie, et, deuxièmement, de comprendre en détail les relations évolutives entre les différentes protéines.

Une protéine est composée d’une chaîne ou séquence d’acides aminés. Vingt différents types d’acides aminés sont produit naturellement. Dans les protéines globulaires, cette chaîne d’acides aminés se replie sur elle-même produisant une forme globulaire (la structure ou repliement). Certaines chaînes se replient en 2 unités globulaires compactes ou davantage. Ces unités sont appelées domaines et sont souvent associées aux différentes activités partielles de la protéine. Les sections de la chaîne protéinique, composées d'hélices-α (H) ou de brins-β (B), ont typiquement une structure locale rιgulière. Ces sections sont appelées les éléments de structure secondaire (ESS). Elles sont, la plupart du temps, connectées par des régions de structure irrégulière appelées des boucles. Ce type de structure décrit la majorité des protéines, néanmoins il faut savoir que les éléments de structure secondaire diffèrent en nombre, en type, en connectivité séquentielle et en arrangement spatial pour finalement former une grande diversité de repliements de protéines. Le lecteur est invité a consulter [BT91], introduction à la structure de protéine.

La figure 1 ci-dessous illustre bien ce modèle de structure: exemple de la chaîne A de la protéine 2bop [HGLS92]. Noter que les ESS de type étendu (brin) sont représentés par des rubans gris clairs, les hélices par des rubans gris foncés et les boucles les reliant, par de minces cordons. La structure est à tri-dimensionnelle. Pour bien se rendre compte, il faudrait visualiser cette structure sur écran en utilisant un programme comme Rasmol [SMW95], celui-ci permettant d'observer un objet sous différents angles de rotation.



Figure 1. diagramme rasmol de la protéine 2bop

 

Actuellement, les structures de protéines sont déterminées de façon expérimentale par la radiocristallographie et la RMN (Résonance Magnétique Nucléaire), deux techniques très longue à effectuer. Lorsque les coordonnées atomiques sont déterminées, les biologistes cherchent à établir le lien entre la protéine sous étude et d’autres protéines dont les structures et fonctions ont déjà été identifiées. Une parfaite compréhension des similarités et des différences entre les structures de protéines est essentielle à l’étude des relations entre séquences, structures et fonctions, et à l’analyse des relations possibles d’évolution. Ceci est à l'origine du développement de méthodes computationnelles de comparaison de structures et d’algorithmes de recherche de bases de données structurelles telle que la banque de données Brookhaven Protein Data Bank (PDB) [BKW⁺77, ABB⁺87]. Ce domaine de recherche est beaucoup trop vaste pour rapporter ici son contenu, le lecteur est invité a consulté Orengo [Ore94] et Gibrat et al [GMB96] pour une excellente étude du sujet.

Les structures de protéines peuvent être représentées à différents niveaux de détails, allant de la description des coordonnées atomiques, en passant par l’approximation des vecteurs, aux ESS, et ce en terminant par des méthodes de description basées sur des modèles de structures hautement simplifiés. Ces méthodes de description, plus précisément de description topologique, considèrent une séquence d' ESS, en prenant compte de certaines relations comme la juxtaposition spatiale au sein du repliement et l'orientation approximative, et en négligeant certains détails comme la longueur et la structure des boucles et la longueur des éléments de structure secondaire.

La description topologique a l’avantage d’être simple, ce qui rend possible l’implémentation d’algorithmes très rapides de recherche de motifs et de comparaison de structures. Ces descriptions peuvent également être utilisées dans des applications comme l’apprentissage automatique. Sans elles, il serait bien difficile d'appliquer de telles applications aux structures de protéines. Négliger certains détails qui généralement varient entre structures apparentées, par exemple la longueur et la structure des boucles, la longueur exacte des ESS, la position spatiale et l’orientation des SSE, offre la possibilité de détecter des relations structurales beaucoup plus distantes, plus que ne permettaient les méthodes traditionnelles de description geométriques. Mais d’un autre côté, quelques inconvénients peuvent faire surface: des exemples de structures, qui, certes, sont apparentés au niveau topologique, sont détectés alors qu’ils sont en fait très différents d’un point de vue géométrique et n’ont aucune relation biologique significative.

Dans cet article, nous présentons de façon formelle les descriptions topologiques de structures et motifs de protéines. Nous présentons également un algorithme rapide de retour-arrière, fonctionnant à partir de contraintes, qui filtre un motif dans une description de structure donnée. Nous décrivons l'implémentation des descriptions topologiques en base de données déclarative et l'algorithme de filtrage en un programme logique par contraintes sur domaines finis. Nous incluons dans ce document quelques résultats illustrant l'utilité de notre programme dans sa recherche de motifs dans une base de données de protéines.

 

2. Diagramme TOPS et motifs

Les structures de protéines sont représentées dans notre système sous forme topologique, utilisant le modèle TOPS qui est une abstraction schématique en 2 dimensions de structures de protéines tri-dimensionnelles. Créé à l’origine pour une comparaison manuelle et pour la compréhension des repliements de protéines, les croquis TOPS étaient dessinés à la main [ST77]. Il existe maintenant un algorithme informatisé qui produit ces croquis automatiquement à partir d'une structure de protéine [FMT94,WSFT99,WHT98]. Nous avons basé cette technique sur la version formelle du langage TOPS que nous avons conçu. Celle-ci contient des contraintes sur domaines finis, et utilise aussi bien les diagrammes (descriptions des exemples) que les caractérisations plus générales des structures de protéines (motifs).

 

1. Diagrammes TOPS

Un diagramme TOPS est une formalisation d’un croquis, basé sur les informations topologiques sous-jacentes des ESS (liaisons hydrogènes et chiralités) à partir desquelles le croquis est généré. Un tel diagramme est une séquence de structure secondaire et deux ensembles correspondants qui définissent les relations, ou contraintes, des éléments de la séquence. Ces relations sont sous forme de liaisons hydrogènes ou de chiralités.

De façon plus formelle, un diagramme TOPS est un triplet T = (E,H,C) où E = S₁,…,S_k est une séquence d’éléments de structure secondaire de longueur k et H et C sont des relations sur SSE, appelés respectivement liaisons hydrogènes et chiralités. Dans cette description, une contrainte de liaison hydrogène fait référence à une échelle de liaisons hydrogènes individuelles entre brins adjacents du feuillet. Nous caractérisons un diagramme TOPS tel un graphe-chaîne, car une séquence E peut être considérée comme une chaîne, avec 2 relations H et C sur les éléments de la chaîne, ou comme une trajectoire le long du graphe ayant pour sommets {S₁, …, S_k} et pour flèches {S₁ → S₂, S₂ → S₃, …, S_K-1 → S_K}, et 2 ensembles H et C d’arêtes sur un sous-ensemble des sommets. C'est pourquoi nous utilisons indiffèremment, ci-dessous, les termes 'longueur du diagramme' et 'longueur de la séquence E'.

Dans notre formalisme, un SSE est une lettre de l’alphabet {α,β}, reprιsentant respectivement une hélice et un brin. Puisque à chaque SSE du diagramme TOPS est associée une direction pointant vers le haut ou vers le bas, nous avons attribué un symbole de direction, + ou -, à chaque lettre de notre alphabet, ce qui donne {α+, α-, β+, β-}.

Les liaisons hydrogènes et chiralités sont toutes deux des relations symétriques (les arêtes du graphe). Les deux ESS contenus dans une liaison hydrogène doivent obligatoirement être des brins. A chaque liaison est associée une direction relative d Î {P, A}, indiquant si la liaison s’est accomplie entre brins parallèles ou anti-parallèles. A chaque chiralité est associée une variété optique, variété ne pouvant être que l'inverse l'une de l'autre, χ Î {G,D} (respectivement gauche et droite). Une chiralité ne se forme qu'entre pair d'ESS de même type. La relation de liaison hydrogène entre deux ESS S_i et S_j est dénotée par (S_i, d , S_j) et celle de chiralité par (S_i, χ, S_j).

La définition formelle d’un diagramme TOPS est la suivante:

Diagramme = (S,Hd, Cd), soit S = {a +, a -, b +, b -} où

S = (S₁,..., S_k), 1£ i£ k, S_i Î S

H_d = {(S_i,d ,S_j), | S_i,S_j, Î {b +, b -} d = P ↔ S_i=S_{j, d} = A ↔ S_i¹ S_j}

C_d = {(S₁, χ,S_j) | S_i,S_j, Î S , , χ Î {G,D}

Exemple: considérons le diagramme TOPS représentant la protéine 2bop (figure 2). Le diagramme peut être en quelque sorte 'allongé' de façon linéaire, voir figure 3. La protéine est ainsi définie :

2bop = (S,H,C) où

S=(b ₁+, a ₂-, a ₃-, b ₄+, b ₅+,b ₆-, a ₇+, b ₈-)

H = { (b ₁+, A, b ₆-), (b ₁+, A, b ₈-), (b ₄+, A, b ₆-),(b ₅+, A, b ₆-)}

C= {(b ₁+,R, b ₄+),(b ₆-,R, b ₈-)}

 

Figure 2. Diagramme TOPS de la protéine 2bop



Figure 3. Diagramme linéaire TOPS de la protéine 2bop

 

La définition de ce diagramme, sous forme de clause en languge de programmation logique, est donnée ci-dessous. La clause est constituée de 3 arguments, représentant dans l'ordre la séquence des ESS, l’ensemble des liaisons hydrogènes et l’ensemble des chiralités, tous représentés sous forme de listes. Chaque SSE est defini dans le corps de la clause en triplet (N,T,D) où N représente le nombre associé a l'élément SSE de la séquence, T le type (b ou h) et D la direction (1 ou 0).

'2bopA0'([S1,S2,S3,S4,S5,S6,S7,S8],

[(S1,a,S6),(S1,a,S8),(S4,a,S6),(S5,a,S6)],

[(S1,r,S4),(S6,r,S8)] ):-

S1=(1,b,1), S2=(2,b,0), S3=(3,h,0), S4=(4,b,1),

S5=(5,b,1), S6=(6,b,0), S7=(7,h,1), S8=(8,b,0).

 

2. Motifs TOPS

Un motif TOPS est comparable a un diagramme TOPS. C'est une généralisation de plusieurs diagrammes , se conformant aux caractéristiques topologiques communes de ceux-ci. Cette généralisation est obtenue grâce à l’insertion d'ESS (ainsi que leurs liaisons hydrogènes et chiralités) dans la séquence des éléments de structure secondaire. En somme, un diagramme est tout simplement un motif où aucune insertion n’est permise. La longueur d'une insertion doit être contenue dans la plage des longueurs de séquences autorisées pouvant être insérées. Un motif TOPS forme ainsi un triplet, similaire à celui du diagramme TOPS. Cette séquence d'ESS où les insertions sont permises est notée motif-T.

De façon formelle, un motif TOPS est un triplet P = (T,H,C) où T (dénoté motif-T) est une séquence V₁ ¾ I₁→ V₂ ¾ I₂→ … ¾ I_k-1→ V_k comprenant les ESS symbolisés par V_i et entre chacun de ces éléments, une description d’insertion. Chaque description d’insertion I_j représente une contrainte sur le nombre d'ESS pouvant être insérés à cette position. La plage potentielle de I_j varie, allant de zéro au nombre maximum d'ESS contenus dans un diagramme TOPS (environ 60). Nous utiliserons N ci-dessous pour représenter ce nombre maximum, et comme pour les diagrammes, H et C pour représenter respectivement une liaison hydrogène et une chiralité.

Prenons l’exemple d’un motif TOPS décrivant la tresse (la protéine 2bop est un exemplaire de tresse), illustré dans la figure 4.



Figure 4. Diagramme TOPS du motif de tresse



Figure 5. Diagramme linéaire TOPS du motif de tresse

 

En principe, comme dans les diagrammes TOPS, à chaque élément SSE d’un motif TOPS est associée une direction pointant vers le bas ou vert le haut (respectivement + ou -), et chaque élément est composé d’une lettre de l’alphabet {α, β}. Cependant, ιtant donné qu’un diagramme TOPS présente une invariance rotationnelle de 180^o autour des axes x et y, il est nécessaire d’associer à chaque SSE du motif, une variable de direction, ⊕ ou ⊖ , de façon à satisfaire la contrainte suivante :

" ⊕, ⊖ є P : opp (⊕, ⊖)↔ (⊕ = +∧⊖ = -) V (⊕ = -∧⊖ = +)

La clause du motif de tresse ci-dessous a été écrite dans un langage de programmation logique par contrainte. Cette clause ressemble beaucoup en forme à celle du diagramme. Toutefois les nombres des ESS ne sont plus ici des exemples. Ces nombres sont contraints à être en ordre, les intervalles vides étant permis. Pour rester général, nous avons explicitement précisé chaque contrainte, plutôt que de les coder de façon récursive (dans certain motif, chaque intervalle vide peut être de différente taille). Nous définissons également opposite/2, contraignant chacun de ses arguments d’être +1 ou 0, et de ne pas être égal.

 

 

 

plait( [S1,S2,S3,S4,S5,S6],

[(S1,a,S4),(S1,a,S6),(S3,a,S4)],

[(S1,r,S3),(S4,r,S6)] ):-

S1=(N1,e,Haut), S2=(N2,h,Bas), S3=(N3,e,Haut),

S4=(N4,e,Bas), S5=(N5,h,Haut), S6=(N6,e,Bas),

N1 #> 0, N2 #> N1, N3 #> N2, N4 #> N3, N5 #> N4,

N6 #> N5, 60 #>= N6,

opposite(Bas,Haut).

opposite(X,Y) :- X in 0..1, Y in 0..1, X #\= Y.

3. Comparaison de motifs

1. Algorithme

Nous étudions actuellement la possibilité d'utiliser un modèle relationnel de base de donnée, connecté a notre système de recherche de motifs, ceci afin de prévenir des problèmes de stockage (quantité énorme de données générée régulièrement) et de leurs mises à jours. Une base de données Oracle (version 7.3) contenant les diagrammes TOPS a été développée. Ces diagrammes proviennent de notre base de données en programmation logique, et sont traduits grâce à un script Prolog. Des tests initiaux montrent que des requêtes simples peuvent etre construites en SQL, équivalentes à celles de notre système de programmation logique par contraintes, par exemple la recherche des tournures gauchères αβα (left-handed αβα turn). Sur les 3567 domaines de l'Atlas, nous avons identifiι 151 tournures gauchères αβα, soit 4.23%. La base de donnιes N-Rep CATH en contient 3.28% et la base SCOP PDB90 en contient 5.54%. Ces types de domaines sont importants en biologie car ils sont thermodynamiquement instables.

Le programme de filtrage de motifs, tout comme les programmes de comparaison de structures et de découverte de motifs qui ne sont pas décrits dans ce document, ont été développés sous programmation logique par contraintes sur domaines finis. Ces programmes s'exécutent sous gprolog (http://pauillac.inria.fr/diaz/gnu-prolog) et également sous SICStus Prolog, faisant usage de la bibliothèque clpfd (http://www.sics.se/sicstus.html). Le système de production s'execute sur le serveur web DEC Alpah de l'Institut Européen de Bio-informatique, utilisant un code executable produit par clp(FD), ceci étant du à l'absence de port gprolog sur cette plateforme pour le moment. La version de l'Atlas TOPS en programmation logique contient plus de 3000 définitions de domaines. Rappelons que la base PDB contient plus de 24 000 définitions. Le temps de chargement est d'environ 3 secondes par mega-octet, soit approximativement 75 secondes pour le chargement complet de toute la base de donnée PDB. L'atlas peut être chargé en mémoire sur le serveur, cependant un mécanisme simple de paging pour base de données a été développé dans le but de surmonter les restrictions mémoire lorsque des requêtes interrogant tout le contenu de la base de données PDB sont composées. L'interface web du programme de recherche de motifs a été crée avec une version de PiLLoW, que nous avons branché au clp(FD).