Matrices poids-position : principes et algorithmes

Master Bioinformatique et Biostatistiques

2ème année recherche

Université Paris Sud XI

Matrices poids-position : principes et

algorithmes

Rapport de stage

Mars 2006 � Septembre 2006

Bruno Besson

Tutrice : Mireille Régnier

INRIA Rocquencourt, projet ALGO

Résumé

Les signaux sur l'ADN ou l'ARN sont généralement représentés soit par un motif consen-sus, soit par une matrice poids-position. Le premier modèle a été largement étudié tantdu point de vue algorithmique que de l'évaluation de la signi�cativité statistique. Trèspeu de résultats sont disponibles sur modèle matriciel (Huang et al., 2004, résultatsen cours de publication de Uri Keich), bien que ce soit le modèle le plus courammentutilisé par les biologistes.

Parmi les problèmes ouverts pouvant permettre la dé�nition rigoureuse d'un seuil depertinence des données, on peut citer : (a) une évaluation �able du taux de faux positifsou de faux négatifs, (b) le liens entre le nombre de données expérimentales disponibleset la précision de la matrice, notamment le nombre de chi�res signi�catifs dans un score,(c) l'évaluation a priori de la queue de distribution d'une matrice poids-position.

Nous adressons ici certains problèmes algorithmiques rencontrés lors de la mani-pulation mathématique des matrices poids-position, puis nous proposons une premièreapproche vers une solution au problème (b).

Remerciements

Je souhaiterais tout d'abord remercier Mireille Régnier, ma tutrice à l'INRIA pen-dant ces six mois de stage. Elle m'a donné l'opportunité de participer à son travail etde béné�cier de son expérience et de ses connaissances.

Toute ma gratitude va à l'équipe du projet ALGO et en particulier à André Balsaqui ont été présents tout au long de ce stage et m'ont toujours aidé avec plaisir.

Merci en�n à Valya Boeva, Julien Clément et Zara Kirakossian pour les dis-cussions stimulantes que nous avons partagées.

5

Table des matières

1 Introduction 11

2 Régulation de l'expression des gènes 13

2.1 Mécanismes de régulation et interactions . . . . . . . . . . . . . . . . . . 13

2.1.1 Cas des organismes procaryotes . . . . . . . . . . . . . . . . . . . 13

2.1.2 La régulation chez les eucaryotes . . . . . . . . . . . . . . . . . . 14

2.1.3 Recherche de signaux . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2 Représentation mathématique des signaux de régulation . . . . . . . . . . 15

2.2.1 Représentation séquentielle ou matricielle . . . . . . . . . . . . . . 15

2.2.2 Modèle de Markov et réseaux de neurones . . . . . . . . . . . . . 15

3 Matrices poids-position 17

3.1 Représentation de signaux à l'aide de PSSM . . . . . . . . . . . . . . . . 17

3.1.1 Construction d'un alignement de séquences . . . . . . . . . . . . 17

3.1.2 De l'alignement à la PSSM . . . . . . . . . . . . . . . . . . . . . 18

3.2 Propriétés des matrices poids-position . . . . . . . . . . . . . . . . . . . 19

3.2.1 Moyenne et variance . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2.2 Fonction génératrice des scores . . . . . . . . . . . . . . . . . . . 20

3.2.3 Signi�cativité statistique des scores . . . . . . . . . . . . . . . . . 21

4 Algorithmique 23

4.1 Distribution des scores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.1.1 Calcul de la fonction génératrice des scores . . . . . . . . . . . . . 23

4.1.2 Optimisation dans le cadre tronqué du calcul de p-valeur . . . . . 26

7

8 Matrices poids-position : principes et algorithmes

4.2 Ensemble Hs des mots . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.2.1 Une première approche . . . . . . . . . . . . . . . . . . . . . . . . 27

4.2.2 Représentation de Hs dans une structure compacte . . . . . . . . 29

4.3 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5 Comparaison des algorithmes pour Hs 33

5.1 Tests e�ectués . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5.1.1 La banque de données TRANSFAC . . . . . . . . . . . . . . . . 33

5.1.2 Un critère commun aux di�érentes matrices . . . . . . . . . . . . 34

5.2 Domaine d'utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.3 Apports et limites des di�érents algorithmes . . . . . . . . . . . . . . . . 37

6 Robustesse et chi�res signi�catifs 41

6.1 Distribution des scores en fonction du nombre de chi�res signi�catifs . . 41

6.1.1 Comportement global . . . . . . . . . . . . . . . . . . . . . . . . . 42

6.1.2 Précision et coût de calcul . . . . . . . . . . . . . . . . . . . . . . 42

6.2 Robustesse d'une matrice . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.2.1 Comparaison des ensembles expérimentaux . . . . . . . . . . . . 45

6.2.2 Positionnement des séquences ôtées . . . . . . . . . . . . . . . . . 47

6.2.3 Validation expérimentale . . . . . . . . . . . . . . . . . . . . . . . 49

6.2.4 Stabilité des p-valeurs . . . . . . . . . . . . . . . . . . . . . . . . 50

7 Conclusion 53

7.1 In�uence de la précision du calcul et des sources . . . . . . . . . . . . . . 53

7.2 Extensions du travail sur Hs . . . . . . . . . . . . . . . . . . . . . . . . . 53

8

Table des �gures

2.1 Mécanismes de régulation transcriptionnelle chez les eucaryotes . . . . . 14

2.2 Représentation par une séquence consensus et code IUPAC . . . . . . . . 16

3.1 Alignement de séquences . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.2 Construction d'une PSSM à partir d'un alignement de séquence . . . . . 19

4.1 Détermination de H0.9 selon l'approche de Hertzberg et al. . . . . . . . 28

4.2 Structure en trie contenant H0.9 . . . . . . . . . . . . . . . . . . . . . . . 29

4.3 Structure condensée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5.1 Répartition des matrices de TRANSFAC . . . . . . . . . . . . . . . . . . 35

5.2 Temps moyen de calcul des algorithmes . . . . . . . . . . . . . . . . . . . 38

5.3 Limitations de la structure de données utilisée . . . . . . . . . . . . . . . 39

6.1 Courbes de distribution des scores . . . . . . . . . . . . . . . . . . . . . . 43

6.2 Précision du calcul et dimension de la fonction génératrice des score . . . 44

6.3 Procédure de simulation pour évaluer la robustesse . . . . . . . . . . . . 46

6.4 Positionnement des mots éliminés dans la matrice perturbée . . . . . . . 48

6.5 Rapport de taille nécessaire pour retrouver les motifs expérimentaux . . . 49

6.6 Évolution du taux de faux positifs et faux négatifs en fonction de la tailledu motif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

9

Liste des tableaux

4.1 Mots deM appartenant à H0.9 . . . . . . . . . . . . . . . . . . . . . . . 27

5.1 Taux de réussite des di�érents algorithmes . . . . . . . . . . . . . . . . . 37

6.1 P-valeur et taille estimée des ensembles expérimentaux . . . . . . . . . . 47

6.2 Taille des ensembles expérimentaux et comparaison des ensemble . . . . . 47

10

Chapitre 1

Introduction

Les signaux sur l'ADN ou l'ARN sont généralement représentés soit par un motifconsensus, soit par une matrice poids-position. Le premier modèle a été largement étudiétant du point de vue algorithmique que de l'évaluation de la signi�cativité statistique.Très peu de résultats sont disponibles sur modèle matriciel, bien que ce soit le modèlele plus couramment utilisé par les biologistes.

Les calculs e�ectués sur les matrices poids-position sont complexes, particulièrementlorsqu'il s'agit d'évaluer la signi�cativité des scores. Nous proposons dans une premièrepartie des algorithmes e�caces pour accéder à la fonction génératrice des scores. Nousétendons ensuite ce travail à l'énumération de l'ensemble des mots de score supérieur àun seuil donné.

Dans une deuxième partie, nous nous intéressons au lien entre données expérimen-tales disponibles, nombre de chi�res signi�catifs dans un score et robustesse des résul-tats. Notre travail est une première approche vers le développement d'un outil à mêmed'évaluer la qualité d'une matrice poids-position.

11

Chapitre 2

Régulation de l'expression des gènes

2.1 Mécanismes de régulation et interactions

Le dogme central de la biologie cellulaire établit la liaison qui existe entre l'informa-tion génétique de la cellule contenue dans l'ADN et les protéines qui sont synthétisées :le matériel génétique de l'ADN est dans un premier temps transcrit en ARN à l'aidedes bases complémentaires, puis traduit en un assemblage d'acides aminés qui forme lesprotéines. Chaque cellule d'un organisme donné n'est pas composée des mêmes consti-tuants et une cellule musculaire n'a pas la même fonction qu'une cellule de l'épiderme.Les gènes sont exprimés di�éremment pour chaque cellule de l'organisme, et ce proces-sus fait intervenir divers mécanismes de régulation à tous les niveaux (transcription,traduction, maturation, etc).

2.1.1 Cas des organismes procaryotes

Les procaryotes sont des organismes unicellulaires au génome simple. Ils vivent dansdes milieux très variables et de ce fait doivent être capables de s'adapter rapidementaux conditions changeantes. La régulation des gènes intervient a�n d'exploiter au mieuxles molécules disponibles, synthétiser celles qui manquent ou encore économiser les res-sources disponibles.

Chez les procaryotes, les gènes sont souvent groupés en opérons, et la régulationse fait essentiellement au niveau de la transcription. Celle-ci est contrôlée par deuxséquences situées en amont du site de transcription, respectivement aux positions −35et −10, qui sont reconnues par l'ARN polymérase (région promotrice). L'activité de lapolymérase est à son tour régulée par l'interaction avec des protéines dites activatricesou inhibitrices selon qu'elles ont un e�et positif ou négatif sur la reconnaissance du sitede �xation. Ces protéines se �xent à des éléments de la séquence ADN situés à proximitédu site de �xation de l'ARN polymérase, ceux-ci pouvant parfois se superposer et être encompétition. Les opérons lactose et tryptophane chez E. coli sont des exemples classiquesde tels mécanismes de régulation.

13


Fig. 2.1 � Mécanismes de régulation transcriptionnelle chez les eucaryotes.

2.1.2 La régulation chez les eucaryotes

Les eucaryotes sont des organismes en général plus complexes que les bactéries,souvent pluricellulaires. Ils disposent de compartiments cellulaires (l'ADN est situé dansle noyau) et les cellules évoluent dans un environnement stable. La régulation des gènessert alors à la di�érentiation cellulaire et à répondre aux sollicitations de l'organisme.

La régulation est un phénomène plus complexe que chez les procaryotes et peutintervenir à di�érents niveaux :

� Structure de la chromatine : la structure physique de l'ADN, présent sous formecompactée, peut a�ecter l'accessibilité de la molécule pour les protéines de régula-tion (facteurs de transcription) et les ARN polymérases. Ceci se fait principalementà l'aide de protéines histones ou de méthylations.

� Initiation de la transcription : c'est le principal mécanisme de régulation, à l'instardes procaryotes. Il est néanmoins d'une complexité accrue, en particulier pour cequi concerne les ARNm : on distingue à la fois des promoteurs proches du sited'initiation de la transcription et des séquences qui peuvent être beaucoup pluséloignées en aval ou en amont du gène, et parfois même se situer à l'intérieurmême de celui-ci. En plus des éléments cis-régulateurs qui se �xent sur de tellesséquences, on distingue également des éléments trans-régulateurs qui vont interagirdirectement avec les éléments cis-régulateurs.

� Traitement et modi�cation de la transcription : les ARN messagers doivent êtreprotégés par une coi�e et polyadénylisés ; les introns sont éliminés (phénomèned'épissage alternatif).

� Stabilité du transcrit : La durée de demie-vie des transcrits eucaryotes est trèsvariable alors que celles des transcrits procaryotes est de 1 à 5 minutes.

� Initiation de la traduction : de nombreux ARNm disposent de plusieurs codons mé-thionine, et la capacité des ribosomes à distinguer le bon codon a�ecte l'expressiondu produit d'un gène.

� Modi�cations post-traductionnelles : des modi�cations classiques impliquent desglycosylations, acétylations, formation de ponts disul�des, etc.

14

15 CHAPITRE 2. RÉGULATION DE L'EXPRESSION DES GÈNES

2.1.3 Recherche de signaux

Un des enjeux de la biologie cellulaire et de la bioinformatique est donc de parvenirà identi�er les séquences de régulations sur l'ADN, aussi appelées sites de �xation desfacteurs de transcription (Transcription Factor Binding Sites, TFBS). Le plus souvent,cette recherche ne peut se faire sans l'assistance d'outils informatiques et d'un modèlemathématique.

2.2 Représentation mathématique des signaux de ré-

gulation

2.2.1 Représentation séquentielle ou matricielle

Il existe diverses manières pour représenter des signaux sur une séquence, allantdu modèle simpliste à des modèles plutôt complexes. La méthode la plus simple pourreprésenter un site de �xation est certainement la séquence consensus : il s'agit defaire correspondre au signal une chaîne de caractères avec à chaque position la based'occurrence la plus fréquente. Cette méthode est adéquate par exemple pour représenterdes sites de reconnaissance pour des enzymes de restriction. Si deux caractères ou plusapparaissent avec une fréquence identique ou proche, la séquence consensus n'est plusvraiment adaptée car on ne peut plus décider quel caractère doit �gurer. On préférerautiliser le code IUPAC donné en �gure 2.2 qui autorise di�érents caractères en une mêmeposition. Par exemple, dans le cas de l'ADN, la lettre W correspond à un A ou un T. Ilfaut noter néanmoins que le seuil (ou la fréquence) au-dessus duquel on décide qu'uncaractère est autorisé n'est pas bien dé�ni. Dans l'exemple présenté, une lettre duale aété utilisée lorsque une base est présente à plus de 25%, mais ce choix n'est bien sûr pasuniversel. Il doit être fait en fonction du nombre de séquences disponibles ainsi que dutype de motif étudié : le motif peut être fortement dégénéré ou au contraire très bienconservé, comme dans les enzymes de restriction.

Pour dépasser cette limitation, on peut alors choisir de représenter numériquementcette répartition. Si l'on se place dans le cadre d'un modèle de Bernoulli, où les di�é-rentes positions sont indépendantes entres elles, une matrice poids-position permet dereprésenter l'information : en chaque position, on calcule la fréquence d'apparition dechacun des caractères en prenant en compte la distribution globale des bases. Pour pou-voir disposer d'un score additif, on utilise généralement le logarithme. La constructionde telles matrices sera étudiée dans le chapitre suivant.

2.2.2 Modèle de Markov et réseaux de neurones

Pour compenser la perte d'information due à l'hypothèse d'indépendance des co-lonnes, on peut utiliser une chaîne de Markov cachée (Durbin et al., 1998). Cela cor-respond à un automate stochastique ; cela apporte aussi une plus grande souplesse dans

15


A T T T T G C A A T

A T T T T G A A T T

C T T T A G C A A T

A T T T T C C A A T

A T T T A C C A T C

consensus A T T T T G C A A T

IUPAC A T T T W S C A W T

Code IUPAC Base

A AdénineC CytosineG GuanineT ThymineR A ou G

Y C ou T

S G ou C

W A ou T

K G ou T

M A ou C

B C, G ou T

D A, G ou T

H A, C ou T

V A, C ou G

N toute base

Fig. 2.2 � Représentation par une séquence consensus et code IUPAC.

la structure du motif puisqu'on peut prendre en compte des trous dans le motif. Lesmodèles de Markov partagent de nombreuses caractéristiques communes avec la repré-sentation matricielle, notamment par le grand nombre de faux-positifs générés.

Une autre approche populaire sont les réseaux de neurones. Ils permettent en généralde générer moins de bruit, mais nécessitent un grand ensemble d'entraînement pourfonctionner e�cacement. Pour une revue plus complète des di�érents outils utilisés, onpourra se référer à Sagot ou bien Deonier et al. (2005).

16

Chapitre 3

Matrices poids-position

3.1 Représentation de signaux à l'aide de PSSM

Les matrices poids-position (Position Speci�c Scoring Matrix, PSSM) sont une re-présentation condensée, position par position, du contenu informationnel d'un motifparticulier. Elles sont particulièrement populaires pour représenter des sites de �xationà l'ADN de facteurs de transcription, et sont utilisées pour la recherche de tels motifspour répondre à des besoins d'annotation de génomes.

3.1.1 Construction d'un alignement de séquences

Pour constituer une matrice poids-position, il faut disposer d'un ensemble de Nséquences identi�ées comme représentatives d'un motif donné, sur lesquelles se basera lemodèle. L'idée sous-jacente au modèle est que les di�érentes séquences de l'alignementpartagent des caractéristiques communes, que l'on cherche à représenter de manièrenumérique. Cette sélection peut se faire par exemple en récupérant les séquences enamont de gènes connus pour être co-régulés (van Helden et al., 2002), ou bien à l'aided'une approche non supervisée pour sélectionner un ensemble de mots surreprésentés.Une approche stochastique de type Gibbs sampling permet aussi de sélectionner lesmotifs à partir d'un ensemble de séquences.

Di�érentes techniques s'appliquent ensuite pour aligner les di�érents éléments : uti-lisation de matrices d'alignement ou bien encore une fois une approche de type Gibbssampling qui va chercher à optimiser le placement des résidus (Lawrence et al., 1993).

Une di�culté qui se pose ensuite consiste à déterminer quel fragment de l'aligne-ment doit être conservé pour construire la matrice. En e�et, celle-ci ne peut notammentcontenir ni insertions ni suppressions. Il faut aussi s'assurer de ne garder que la partiede l'alignement porteuse de l'information. On choisit généralement de ne garder que lec÷ur de l'alignement ; on se base sur le contenu en information des résidus, c'est-à-direque l'on évalue numériquement l'information apportée par chacun. Une position trèsdégénérée n'apporte que peu d'information, au contraire d'une autre où il n'y a par

17


Gène Site SéquencePHO5 UASp2 ��ACTCACACACGTGGGACTAGC�

PHO84 Site D ��TTTCCAGCACGTGGGGCGGA��

PHO81 UAS ��TTATGGCACGTGCGAATAA��

PHO8 Proximal GTGATCGCTGCACGTGGCCCGA��

PHO5 UASp3 ��TAATTTGGCATGTGCGATCTC��

PHO84 Site C ��ACGTCCACGTGGAACTAT��

PHO84 Site A ��TTTATCACGTGACACTTTTT

Consensus ��gCACGTGggac��

Alignement retenu ************

Fig. 3.1 � Alignement de séquences. Exemple du facteur de transcription Pho4p de lalevure (source : Oshima et al., 1996).

exemple que des résidus guanine.

3.1.2 De l'alignement à la PSSM

Détaillons maintenant comment une PSSM M est constituée à partir d'un aligne-ment de longueur L. Cette matrice possède L colonnes et V lignes, où V est la cardinalitéde l'alphabet. Pour chaque position i, on note nai le nombre d'occurrences du caractèrea. Une hypothèse forte du modèle est l'indépendance des résidus : chaque colonne de lamatrice se comporte indépendamment des autres. Notons pai la fréquence observée dela lettre a :

pai =nai

N.

C'est une approximation de la probabilité mesurée en une position i. On note qai lafréquence attendue dans le cas d'un modèle aléatoire, basée sur la fréquence théoriquedes caractères. Cela peut être la répartition globale en nucléotides d'un organisme ouune information plus précise relative aux séquences sélectionnées.

Le rapport pai

qaimesure l'écart de la distribution observée à celle attendue aléatoire-

ment. Pour que le score soit aisé à calculer, c'est à dire mette en jeu des additions plutôtque des multiplications, on prend généralement le logarithme du rapport. Ainsi :

Mai = log2

pai

qai

et pour un mot H tel que hi représente le ième caractère de H dans l'alphabet (onidenti�era par la suite un caractère par sa position dans l'alphabet) :

score(H) =L∑

i=1

Mhii =L∑

i=1

log2

phii

qhii

.

Il peut arriver qu'un caractère ne soit jamais présent en une position donnée dansles séquences (voir par exemple l'ensemble de séquences choisi dans la �gure 2.2). Ce cas

18

19 CHAPITRE 3. MATRICES POIDS-POSITION

pos (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12)A 1 3 2 0 8 0 0 0 0 0 1 2C 2 2 3 8 0 8 0 0 0 2 0 2G 1 2 3 0 0 0 0 0 5 4 5 2T 4 1 0 0 0 0 0 8 3 2 2 2

(a) Matrice d'alignement

(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12)-0.79 0.13 -0.23 -2.20 1.05 -2.20 -2.20 -2.20 -2.20 -2.20 -0.79 -0.230.32 0.32 0.70 1.65 -2.20 1.65 -2.20 -2.20 -2.20 0.32 -2.20 0.32-0.29 0.32 0.70 -2.20 -2.20 -2.20 1.65 -2.20 1.19 0.97 1.19 0.320.39 -0.79 -2.20 -2.20 -2.20 -2.20 -2.20 1.05 0.13 -0.23 -0.23 -0.23

(b) Matrice poids-position

Fig. 3.2 � Construction d'une PSSM à partir d'un alignement de séquence. Exemplede Pho4 chez la levure (source : TRANSFAC, matrice F$PG04_01). La matrice poids-position a été construite avec des pseudo-comptes de 1 et les fréquences de {A, C, G, T} à{0.33, 0.18, 0.18, 0.33}. Le mot ATTCGCGATCAT a par exemple un score de −0.79− 0.79−2.20 + 1.65− 2.20 + 1.65 + 1.65− 2.20 + 0.13 + 0.32− 0.79− 0.23 = −3.80.

peut se présenter parce que l'échantillon est petit (il ne représente qu'une estimation dela population) ou très peu dégénéré en certaines positions. Dans ce cas, le score n'estplus dé�ni car log2(0) = −∞ ; on corrige alors pai à l'aide de pseudo-comptes :

pai =nai + 1

N + V.

Le modèle de score permet de classer les mots selon leur ressemblance ou non avecles caractéristiques partagées par la PSSM. Plus le score est élevé, plus le mot est prochede ces caractéristiques ; il est donc une cible potentielle. Mais le score d'un mot n'estvalable que pour une matrice donnée et il n'aura pas la même signi�cation pour uneautre : un score de 15 peut être exceptionnel et commun à la fois. Il est donc importantnon seulement de savoir choisir un seuil en connaissance de cause mais aussi de disposerd'outils pour évaluer la signi�cativité statistique de tels scores.

3.2 Propriétés des matrices poids-position

Très peu de résultats sont disponibles sur le modèle matriciel, bien qu'il soit le pluscouramment utilisé par les biologistes. Parmi les problèmes ouverts, pouvant permettrela dé�nition rigoureuse d'un seuil de pertinence des données, on peut citer :

1. une évaluation �able du taux de faux positifs ou de faux négatifs,

2. le lien entre le nombre de données expérimentales disponibles et la précision de lamatrice, notamment le nombre de chi�res signi�catifs dans un score,

3. le traitement de signaux mélangés, et en particulier les corrélations entre les partiesvariables du signal,

19


4. l'évaluation a priori de la queue de distribution d'une matrice poids-position.

Nous disposons tout de même de quelques propriétés dans le cadre du modèle de Ber-noulli, facilement généralisables au cas markovien. De nouveaux résultats permettentune estimation de la signi�cativité statistique pour un ensemble de mots de score supé-rieur à un seuil donné.

3.2.1 Moyenne et variance

Les colonnes de la matrice étant indépendantes, la moyenne des scores de la matriceest égale à la somme des espérances de chacune d'entre elles.

E(M) = E(C1) + · · ·+ E(CL) =L∑

i=1

V∑a=1

paMai avec Ci =

M1i...MV i

où pa est la probabilité résiduelle de a. Selon la formule classique qui relie l'espérance àla variance, on dispose également de cette dernière, car :

E(M2) = E[(C1 + · · ·+ CL)2] =L∑

i=1

E(Ci)2 + 2

∑i<j<L

E(Ci, Cj) .

Finalement, on a :

V (M) = E(M2)− E(M)2 =L∑

i=1

V∑a=1

paM2ai − (paMai)

2 .

On a accès en temps linéaire LV à certaines valeurs qui peuvent nous être utiles pourd'autres calculs, par exemple les scores minimaux et maximaux de la matrice. Pour cela,il su�t de prendre pour chaque colonne le résidu de plus faible (resp. meilleur) score. Lecalcul de l'espérance se fait en temps linéaire et espace constant ; le calcul de la variancese fait en temps quadratique et espace constant.

3.2.2 Fonction génératrice des scores

Les fonctions génératrices sont un concept introduit initialement par Laplace ; c'estaujourd'hui un outil classique pour des problèmes d'énumération. Soit A une classed'objets combinatoires, dans notre cas les mots. An est le sous-ensemble de A contenantles mots de score n, et An sa cardinalité. On écrit la fonction génératrice de la manièresuivante :

A(z) =∑n≥0

Anzn .

Dans le contexte qui nous intéresse, A(z) est un polynôme dont chaque terme Aizi

représente la probabilité Ai qu'un mot de taille L ait un score égal à i si le score est entier.Sinon, Ai est la probabilité du ième score d'une liste ordonnée. Pour pouvoir réaliser les

20

21 CHAPITRE 3. MATRICES POIDS-POSITION

calculs d'un point de vue informatique, on réalise en pratique une transformation desvaleurs décimales en valeur entière avec un seuil de précision choisi. Connaître la fonctiongénératrice des scores revient donc à connaître la distribution des scores de la matrice.En e�et, si le polynome est ordonné, on peut calculer (entre autres) la probabilité qu'unmot quelconque ait un score supérieur à un seuil donné : c'est la somme des coe�cientsdes termes de degré supérieur à s. La fonction génératrice des scores est également à labase du calcul de p-valeurs sur des textes et des ensembles de mots.

Comme précédemment, nous nous plaçons dans le cadre d'un modèle simple de Ber-noulli où les positions sont indépendantes entre elles. Si l'on considère les résidus de laPSSM de gauche à droite, et si l'on note Ci(z) la fonction génératrice de la ième colonnealors A(z) se dé�nit également comme le produit de l'ensemble des colonnes :

A(z) =∏

1≤i≤L

Ci(z) .

Il est ainsi aisé de calculer la fonction génératrice des scores à l'aide de simples produitsde polynômes. Comme nous le décrivons dans le chapitre suivant, la di�culté d'un telcalcul vient de la taille des polynômes à manipuler. La borne triviale sur cette taille estV L.

3.2.3 Signi�cativité statistique des scores

Nous avons dans la section précédente présenté des outils pour analyser la distribu-tion des V L score possibles. Un problème connexe est le suivant : quelle est la probabilitéd'un mot de Hs dans un texte ou une séquence de longueur n ? Une première approxi-mation est souvent utilisée :

P (Hs)n = 1− (1− P (Hs))n ,

mais il a été montré (Vandenbogaert, 2004) que ce résultat n'est pas satisfaisant caril ne prend pas en compte les recouvrements qui peuvent avoir lieu entre les motifs.Beaucoups de travaux actuels se concentrent sur ce problème (Robin et al., 2001, Van-denbogaert, 2004, Régnier et Vandenbogaert, à paraître, Nuel, 2005, Hertz-berg et al., 2005, Boeva et al., 2005), mais il reste complexe, voire exponentiel. Lestravaux de CPM'05 ont conduit à l'écriture d'un algorithme e�cace (communicationsprivées).

L'un de nos projets est également d'intégrer les travaux réalisés au cours de ce stageet d'utiliser la structure de donnée condensée dé�nie au chapitre 4 en tant qu'entrée del'algorithme.

21

Chapitre 4

Algorithmique

Dans cette partie, nous nous intéressons plus en détail au calcul de la fonction généra-trice des scores et à ses applications. D'un grand intérêt pour les matrices poids-position� il permet notamment de travailler sur les ensembles de mots dé�nis pour un seuildonné � son calcul est un aspect critique car il peut être di�cile à obtenir dans certainesconditions.

4.1 Distribution des scores

4.1.1 Calcul de la fonction génératrice des scores

Nous avons vu que le calcul de la fonction génératrice des scores ne pose pas dedi�cultés théoriques, car il est composé uniquement de produits et sommes sur despolynômes. Nous détaillons ci-dessous la manière dont ces opérations sont e�ectuées.La di�culté ne provient pas du calcul lui-même mais du nombre potentiellement trèsimportant d'opérations à réaliser a�n d'obtenir le résultat.

Les matrices usuelles pour l'ADN sont généralement d'une taille comprise entre 5et 30 nucléotides. À chaque colonne insérée pour le calcul de la fonction génératrice lenombre d'éléments est multiplié par 4, la taille de l'alphabet. Si au �nal ce nombre estraisonnable avec les ordinateurs actuels pour par exemple une matrice de taille 9 (il ya alors environ 2, 6 · 104 scores potentiellement di�érents), on atteint vite les limites decalcul pour une taille supérieure (jusqu'à 1018 pour une matrice de 30 éléments). Biensûr, et nous y reviendrons plus tard, certains mots peuvent avoir un score identique. Pourautant, cela n'est pas su�sant pour compenser la croissance exponentielle du nombrede scores avec la taille de la matrice.

Le produit classique de deux polynômes se base sur la distributivité ; il existe parailleurs di�érentes méthodes astucieuses développées pour e�ectuer ce calcul avec unecomplexité moindre (Knuth, 1978, chap. 4.3.3). La méthode proposée par Karatsuba en1962 permet par exemple de réaliser le calcul avec une complexité en O(n

ln 3ln 2 ). D'autres

méthodes encore (Tom-Cook, FFT) étendent ce travail et autorisent des complexités

23


plus faibles.

Mais ces divers algorithmes ne sont pas bien adaptés à notre problème, car tousconsidèrent des polynômes complets, c'est-à-dire que tous les termes � mêmes ceux decoe�cient nul � sont pris en compte. Or les scores d'une PSSM sont creux : pour unensemble de scores se situant entre Smin et Smax, un grand nombre de positions ontune probabilité nulle, le score n'étant jamais atteint. La taille des polynômes étantpotentiellement très grande, nous devons nous assurer de limiter le coût en mémoire detels objets. Pour cela, nous allons modéliser un polynôme comme une liste chaînée determes ordonnés ; seuls les termes à coe�cient non nul sont présents.

Les algorithmes tels que Karatsuba ne peuvent être employés dans ce contexte ; nousprésentons ici un calcul basé sur la distributivité. Dans la section suivante, nous verronscomment il peut être adapté et amélioré dans le cadre du calcul de p-valeurs.

Soient deux polynômes P (z) =∑n

i=1 aizbi et Q(z) =

∑mi=1 ciz

di . Nous e�ectuons leproduit en décomposant l'un des deux polynômes en ses di�érents termes :

P (z)×Q(z) =m∑

i=1

P (z)× cizdi =

m∑i=1

P (i)(z) .

La multiplication de P (z) par Q(z) peut donc se limiter à une succession de deuxopérations simples : (1) produit d'un polynôme par un terme et (2) somme de deuxpolynômes.

Pour un polynôme P (z) comprenant n éléments et un terme bzc, le produit se faiten temps linéaire :

P (i)(z) = P (z)× cizdi =

n∑j=1

(aj × ci)zbj+di .

Faire la somme de deux polynômes revient à concaténer les termes des deux objets, touten fusionnant ceux de degré identique. La di�culté est justement de s'assurer, lorsque unterme est inséré, s'il existe déjà ou non un terme de même degré. L'usage de dictionnairesest habituellement la technique la plus rapide pour cela, mais est di�cilement applicabledans notre cas car le dictionnaire devrait être mis à jour très souvent, et on ne peut pasprédire sa taille à l'avance. Une solution e�cace consiste à s'assurer de l'ordonnancementdes termes des polynômes en fonction de leur degré. Le produit d'un polynôme par unterme ne change pas l'ordre des constituants et l'on ne doit alors gérer celui-ci que dansle cas de la somme (la première opération décrite pour la multiplication par un termeconstant reste donc valable). Comme chacun des polynômes est déjà ordonné, insérerle second polynôme dans le premier nécessite au plus le parcours de ce dernier, soit ncomparaisons en prenant en compte les degrés égaux. L'algorithme 1 est une illustrationde la procédure que l'on peut appliquer.

De manière triviale, le produit de P (z) par un terme de Q(z) coûte n opérationset ceci est réalisé m fois, pour chaque terme de Q(z). Quand on e�ectue la somme dupremier sous-produit avec le second (c'est-à-dire P (1)(z) + P (2)(z)), il y a au plus nopérations, résultant en un polynôme de taille au plus 2n lorsque aucun score n'est égal.

24

25 CHAPITRE 4. ALGORITHMIQUE

Algorithme 1 Somme(P (z), Q(z))

1: u← premier terme de P (z) //u = auzbu

2: pour tout cizdi ∈ Q(z) faire

3: tant que u 6= ∅ ∧ di < bu faire

4: u← TermeSuivant(u)5: si u 6= ∅ ∧ di > bu alors //n'a lieu qu'une seule fois si min(P (z)) > min(Q(z))6: insérer ciz

di en première position7: sinon si u 6= ∅ and di = bu alors

8: au = au × ci //un terme de même degré existe déjà9: sinon //u = ∅ ou di < bu

10: insérer cizdi après u

11: u← cizdi

12: retourner P (z)

En répétant cette opération successivement pour chacun des sous-produits, on réalisen + 2n + . . . + mn opérations et donc on a une complexité de O(nm2). Le calcul duproduit de deux polynômes P (z) et Q(z) se fait donc en O(nm2).

On notera au passage l'asymétrie qui apparaît dans le calcul : il est préférable dechoisir de distribuer le polynôme possédant le moins de termes pour limiter le nombred'opérations à e�ectuer. Cette asymétrie est liée à l'ordonnancement des polynômesutilisé a�n de s'assurer d'avoir des termes de degré unique.

Intéressons nous maintenant à ce qu'il se passe lorsque nous souhaitons calculer lafonction génératrice des scores, c'est-à-dire lorsque nous réalisons les produits successifsdes di�érentes colonnes de la matrice. Ci(z) est le polynôme associé à la ième colonne.Alors :

A(z) =∏

1≤i≤L

Ci(z) = (((

1er produit︷︸︸︷C1(z)× C2(z))× C3(z)︸︷︷︸

2eme produit

)× . . . )× CL(z) .

Le calcul consiste donc en une suite de produit de polynômes. En partant de C1, onréalise successivement le produit du résultat avec la colonne suivante. Dans ce cas, lacomplexité de chaque opération est quadratique telle que décrite dans le paragrapheprécédent, mais la taille du polynôme dont on réalise le produit augmente à chaqueétape. Pour une PSSM de taille V ×L, on a potentiellement au �nal V L scores di�érentset donc V L termes. Ce nombre ne peut d'ailleurs être abaissé que lorsque au cours ducalcul des termes de même degré sont calculés.

Classiquement, les matrices sont calculées sur l'ADN et donc un alphabet de taillequatre (A, T, G et C). On va donc choisir de distribuer le polynôme de la colonne in-troduite, Q(z), plutôt que le résultat calculé jusqu'à présent, P (z), a�n de limiter lacomplexité du calcul (liée à l'asymétrie évoquée ci-dessus) : au fur et à mesure que l'onintègre les di�érents colonnes de la PSSM, P (z) devient un polynôme de taille de plusen plus importante tandis que |Q(z)| reste constant à 4. Le coût d'un produit est alorsO(n), de la complexité du calcul e�ectué. Si l'opération était e�ectuée dans l'autre sens,la complexité serait au contraire quadratique et le coût beaucoup plus important. Il

25


s'ensuit que connaître la distribution des scores de manière exhaustive est intéressant,mais souvent très coûteux et inaccessible pour bon nombre de matrices.

4.1.2 Optimisation dans le cadre tronqué du calcul de p-valeur

Pour beaucoup d'applications, il est possible de se contenter d'une fraction de lafonction génératrice. C'est le cas du calcul de P (S > s), la probabilité pour qu'un motde taille L ait un score supérieur à un seuil s donné. Cette valeur � toujours sous unmodèle de Bernoulli � est la somme des probabilités des scores supérieurs à s ; on nes'intéresse pas explicitement aux termes de degré inférieur.

Le calcul de la fonction génératrice tronquée de ses premiers termes évite ainsi denombreuses opérations inutiles. Le théorème 4.1.1 montre que l'on peut savoir à chaqueétape si le terme à calculer engendrera ou non au moins un terme de degré supérieurà s dans le polynôme �nal. Nous sommes donc capables d'éliminer du calcul les termesinutiles aussi tôt que possible.

Théorème 4.1.1 Soit u un pré�xe candidat de score S(u), et soit min|u| (resp. max|u|),le score minimal (resp. maximal) qui s'ajoutera par la suite. Soit s le seuil �xé.

1. Si S(u) + max|u| < s alors aucun mot construit à partir de u n'atteindra le scoredésiré.

2. Si S(u) + min|u| > s tout mot construit à partir de u aura le score désiré.

3. Soit v un second pré�xe candidat tel que |u| = |v|. Si S(u) = S(v), alors les su�xespermettant de construire des mots valides à partir de u sont les même pour v.

Le calcul de minu et maxu est trivial et se fait en temps linéaire, de manière analogueau calcul des scores extrêmes. Le théorème 4.1.1 dé�nit une deuxième propriété dualede la première. De cette manière, on pourra d'une part ignorer le calcul de certainstermes (utilisation de maxu), et d'autre part regrouper en un seul terme (noté a+z+) lestermes qui ne génèrent que des termes de degré supérieur à s (utilisation de minu). Ceterme est considéré comme ayant un degré in�ni et est donc toujours le dernier termedu polynôme ; seul son coe�cient nous intéresse.

4.2 Ensemble Hs des mots

Nous nous intéressons maintenant au problème évoqué en 3.2.3 : déterminer l'en-semble Hs des mots de taille L de score supérieur à un seuil s donné. Ce calcul est uneétape importante du calcul de p-valeur sur un texte de longueur n sur lequel travaillentactuellement Mireille Régnier, Julien Clément et Valya Boeva, puisqu'il est uti-lisé en entrée de l'algorithme. Lorsque le seuil utilisé est bas, l'ensemble de mots ainsiconstruit peut être très grand ; il est important de disposer d'algorithmes e�caces pourle générer.

26


Algorithme 2 ProduitContraint(P (z), czd, sinf , ssup)

1: //sinf ← s - ScoreMax(Ck) par prétraitement2: //ssup ← s - ScoreMin(Ck)3: pour tout aiz

bi ∈ P (z) faire4: si bi + d > ssup alors //le terme est regroupé au bout5: a+ ← a+ × c6: sinon si bi + d > sinf alors //le terme est calculé normalement7: ai ← ai × c8: bi ← bi + d9: sinon //le terme ne sera pas conservé10: supprimer aiz

bi

11: retourner P (z)

Mot Score Mot Score Mot Score Mot Score

ABB 1 CCC 1.4 ACC 2.6 ACA 4.1BBA 1.1 BCB 1.6 ACB 2.8CBA 1.1 CCB 1.6 BCA 2.9BCC 1.4 ABA 2.3 CCA 2.9

Tab. 4.1 � Mots deM appartenant à H0.9.

Dans la suite de cette section, nous allons illustrer nos propos sur un exemple simplemettant en jeu une PSSM de longueur 3, avec un alphabet factice de 3 caractères : V ={A, B, C}. Cette matriceM est dé�nie de la manière suivante (les di�érentes positionsétant représentées en colonne, chaque ligne renvoie à un caractère de l'alphabet) :

M =

1.0 −1.6 1.1−0.2 0.2 −0.2−0.2 2.0 −0.4

ABC

Considérons H0.9 l'ensemble des mots de score supérieur à 0.9 :

H0.9 = {H ∈ W , score(H) > 0.9} .

Treize mots sur les vingt-sept possibles répondent à ce critère, regroupés dans le tableau4.1. Par exemple, on calcule le score du mot ABC de la manière suivante :

score(ABC) =M11 +M22 +M33 = 1.0 + 0.2− 0.4 = 0.8

Le score est inférieur au seuil que nous nous sommes �xé et par conséquence le motABC n'apparaît pas dans le tableau 4.1. Voyons maintenant comment nous pouvonsdéterminer e�cacement cet ensemble de 13 mots.

4.2.1 Une première approche

Une première idée pour énumérer un tel ensemble est de partir du mot de meilleurscore possible (en ayant par exemple ordonné les lettres de chaque colonne), et ensuite

27


A C A

B C A A B A A C B

C C A B B A B C B B B A A A A A B B B C B A B B A C C

C B A C C B C B A B A A B B B C C B B B B B C C B B B A A B A B C B C C A B C

C A A C B B C B B C C C C C C B B C

C B C

Fig. 4.1 � Détermination de H0.9 selon l'approche de Hertzberg et al.. En partantdu mot de meilleur score ACA, on dégénère successivement les di�érentes positionsjusqu'à ce que les scores soient trop faibles (noeuds en pointillés). Les cellules griséesreprésentent des mots générés de manière redondante ; ils apparaissent dans les travauxde Hertzberg et al., mais pas dans l'amélioration que nous proposons.

de dégrader le mot initial en ses di�érentes positions a�n de générer de nouveaux mots,de score inférieur mais le plus proche possible du score optimum. On continue ainsijusqu'à atteindre la limite qui est le seuil en entrée de l'algorithme.

Dans l'exemple que nous utilisons, on partirait ainsi du mot ACA de score 4.1, quidonnerait naissance à 3 mots : CCA (2.9), ABA (2.3) et ACC (2.6). Chacun d'eux seraitensuite repris et dégénéré à sa suite.

L'approche de Hertzberg et al.

L'approche que nous venons de décrire succinctement a été retenue par Hertzberget al. (2005), et se déroule en 3 étapes :

1. Partir de la séquence consensus de meilleur score en prenant dans chaque colonnele meilleur nucléotide : H0.

2. Pour i allant de 1 à 3L, on calcule l'ensemble des séquences dégénérées à partirde l'ensemble des séquences de Hi−1 qui satisfont le critère de score. On poseHi = Hi−1 ∪H′i−1(s).

3. Retourner H ≡ H(V−1)L.

Les mots ne sont générés qu'à partir des mots de Hi−1 ajoutés à l'étape précédente,c'est-à-dire Hi−1 \ Hi−2. Le processus est arrêté dès qu'aucun nouveau mot généré nesatisfait le critère de score.

Une première optimisation simple

Cette approche n'est pas optimale, car le parcours des mots selon cette procédurepeut générer plusieurs fois un même mot. Sur la �gure 4.1 qui reprend l'exemple de laPSSM donné au début de la partie 4.2, les cellules grisées représentent des mots générésinutilement car ils ont été déjà considérés et inclus (ou rejetés) auparavant. Les auteurs

28


A B C

A

B

B

C

A B C A

B C

A B C A

B C

A B C

PSfrag repla ements

⊥

Fig. 4.2 � Structure en trie contenant H0.9. Les mots se lisent de la racine ⊥ qui est uncaractère factice à chacune des feuilles de la structure.

utilisent une table de hachage pour stocker les données et éviter ainsi d'avoir des motsredondants en mémoire. Il serait assez simple et logique de faire en sorte que le parcoursne puisse générer chaque mot qu'une seule fois. Nous suggérons que pour un mot donnéon ne dégénère que les positions situées après celles déjà modi�ées auparavant (dernièremodi�cation comprise). Par exemple sur la �gure 4.1 le mot ABA a été généré à partirdu mot de meilleur score ACA en modi�ant le deuxième résidu. On refuse donc deconsidérer BBA où le premier résidu est modi�é. Ce mot est de toutes manières pris encompte à partir de BCA (modi�cation de la première base). Cela revient e�ectivementsur la �gure à supprimer les cellules grises et donc assure un parcours optimal.

4.2.2 Représentation de Hs dans une structure compacte

La complexité de l'approche précédente est optimale au sens de l'énumération. Chaquemot en sortie n'est considéré qu'une seule fois et au plus L mots dégénérés ne satisfai-sant pas le critère de score sont étudiés pour chaque mot retenu. La complexité estdonc en O(|H|L). Cette complexité peut être améliorée si on peut contenir l'ensemblesolution dans une structure qui pourra ensuite être réutilisée directement, sans passerpar l'énumération de Hs.

Une approche duale

De manière duale, on peut voir l'énumération des mots non pas comme un arbreque l'on déroule à partir du mot de meilleur score comme dans l'approche Hertzberget al., mais comme un pré�xe que l'on agrandit au fur et à mesure en ajoutant les diversrésidus autorisés. On crée un trie contenant les mots qui véri�ent le critère de score(�gure 4.2). On peut là aussi s'assurer qu'on ne crée un n÷ud � c'est-à-dire ajouter unelettre a au pré�xe u � que si l'on est certain qu'il existe au moins un su�xe w tel queauw appartient à l'ensemble recherché. La complexité est alors identique.

29


Cette approche du problème est très voisine du calcul de la fonction génératricetronquée (section 4.1.2). La question n'est pas la même mais les moyens, eux, sontproches. Dans le premier cas, on parcourt l'ensemble des mots de score supérieur auseuil a�n de déterminer la probabilité de chacun et donc la p-valeur ; dans le secondon parcourt également les mots en s'intéressant cette fois-ci à leur composition. Cettedeuxième tâche est plus compliquée car deux pré�xes de même score ne donnent pas demots identiques, tandis que l'on peut regrouper les probabilités.

Cette équivalence se retrouve d'ores et déjà avec l'approche plutôt naïve que nousvenons d'évoquer qui exploite la première propriété du théorème 4.1.1 selon laquelle unpré�xe ne peut conduire à un mot de Hs que si son score ajouté au score maximal dispo-nible est supérieur à s. Ainsi, le résultat obtenu pour notre exemple, �gure 4.2, permetde retrouver les 13 mots de la �gure 4.1. On peut noter au passage que de cette manièreles mots sont représentés de manière compacte (ce qui est le principe des structuresde type trie). Ceci est plus e�cace qu'un stockage de chaque mot indépendamment enmémoire.

Il est possible de tirer parti des deuxième et troisièmes énoncés du théorème 4.1.1.Nous obtenons une représentation de l'ensemble plus compacte et moins coûteuse, décriteci-dessous.

Autres améliorations possibles pour une structure compacte

Nous n'avons jusqu'à présent exploité qu'une partie du théorème 4.1.1. Or noussavons également que pour certains pré�xes, n'importe quel su�xe convient, car le scorede chacun des mots générés sera toujours supérieur au seuil s. Il est donc inutile decalculer les propriétés des noeuds ainsi que chacun d'entre eux. Un noeud particulierayant pour caractère F � un joker � permet d'avoir une structure compacte sans perted'information. La �gure 4.3(a) illustre le gain obtenu sur notre exemple simple.

Il existe en�n une dernière propriété que nous n'avons pas encore exploitée : lesscores égaux. En e�et, lors du calcul de la fonction génératrice (tronquée ou non), nousavons montré que l'on peut regrouper ensemble les termes de degré identique. Il n'estpas possible d'appliquer directement ce principe à notre nouveau problème, puisque l'onsouhaite avoir connaissance des mots dans notre structure, mais nous pouvons néanmoinscondenser l'information et partager certains sous-arbres entres les di�érentes branchesde la structure.

Théorème 4.2.1 Si deux pré�xes u et v tels que |u| = |v| partagent un même score,alors l'ensemble des su�xes construits à partir de v sera identique à celui de u.Dans la structure en trie, u et v partagent un même sous-arbre.

Ainsi que le montre la �gure 4.3(b), on peut alors utiliser des pointeurs pour fairecorrespondre un sous-arbre à un noeud donné et améliorer encore la taille de la structurequi stocke Hs.

30


A B C

B C

A B

B C

A

B C

A

PSfrag repla ements

⊥

⋆⋆⋆

(a) avec jokers

BC A

B C B C

A B A

PSfrag repla ements

⊥

⋆⋆

(b) utilisation des scores égaux

Fig. 4.3 � Structure condensée avec utilisation de jokers F puis des scores égaux. (a)Le nombre de noeuds est maintenant de 17 au lieu de 23 précédemment. Le pré�xe AC aun score de 3.0 ; tout mot construit à partir de lui aura un score d'une valeur au moins2.6 et donc sera retenu dans H0.9. (b) Structure optimisée avec l'utilisation de liensinternes. La �èche grise représente un lien de C vers B : le pré�xe C est de même scoreque le pré�xe B de même taille, ils partagent un sous-arbre commun qu'il est inutile dereprésenter 2 fois. Le nombre de noeuds est abaissé à 13.

4.3 Implémentation

Les algorithmes décrits dans ce chapitre, ainsi que certains utilitaires en rapport avecles PSSMs, ont été implémentés en C++, et devraient pouvoir compiler sur la plupartdes plates-formes actuelles, bien que le code actuel ait été écrit sous Linux, et testéuniquement sur cet environnement (compilateur GCC version 3.4.3 et 4.0).

Le code est entièrement documenté, et une documentation au format HTML estdisponible grâce à l'outil Doxygen (van Heesch). Elle comprend à la fois la documen-tation des programmes fournis et le détail de l'API. Les programmes sont au nombre decinq :

gfunc calcule la fonction génératrice des scores ;

wenum détermines les mots de score supérieur à un seuil donné ;

pvalue calcule la probabilité qu'un mot ait un score supérieur à un seuil s ;

convert-matrix, matrix-info sont des utilitaire liés aux matrices poids-position.

En parallèle, les algorithmes présentés ont été développé de manière modulaire et peuventêtre utilisés en tant que bibliothèque. Cela concerne aussi bien le calcul de la fonctiongénératrice que la manipulation des matrice et la structure de donnée développée.

31

Chapitre 5

Comparaison des algorithmes de

construction de Hs

Dans ce chapitre, nous nous intéressons à l'étude de la complexité des di�érentsalgorithmes que nous avons présentés dans le chapitre 4, et à leur utilisation concrètepour des matrices poids-position utilisées par les biologistes. Nous avons étudié plusparticulièrement la construction de la structure contenant Hs, puisque les algorithmesmettent en jeu des techniques identiques à la fonction génératrice, tout en introduisantune complexité supplémentaire. Il est important de savoir dans quel cadre de tels outilspeuvent être utilisés et quelles sont leurs limites.

5.1 Tests e�ectués

Nous avons voulu tout d'abord évaluer l'apport des di�érents algorithmes. Pour cela,nous avons comparé leur comportement respectifs � aussi bien du point de vue tempsde calcul que structure des données � en incluant les diverses optimisations discutées.Nous avons aussi observé les limites du domaine d'utilisation : quelles sont les tailleset les p-valeurs pour lesquels ces algorithmes peuvent être utilisés sans faillir ? Quel estl'apport des di�érentes optimisations proposées ? Les comportements observés étant trèsdi�érents selon les matrices, nous avons choisi d'appliquer les calculs à un ensemble leplus représentatif possible de PSSM rencontrées par les biologistes ; cela nécessite éga-lement d'utiliser un critère �able pour comparer équitablement les résultats en fonctionde la taille des matrices.

5.1.1 La banque de données TRANSFAC

Il nous a fallu dans un premier temps disposer de nombreuses matrices a�n de pouvoirétudier le comportement global des algorithmes. Le jeu de données doit être le plusimportant possible, car des matrices de même taille, construites à partir d'un mêmenombre de sites identi�és, peuvent avoir des comportements très di�érents. La banque

33


de données TRANSFAC (Matys et al., 2003) est certainement une des sources les plusconnues pour les sites de �xation de facteurs de transcription. Elle regroupe des donnéesissues de la littérature. Nous avons récupéré les 393 matrices disponibles publiquement 1

pour nos tests, disposant ainsi d'un échantillon assez large et représentatif des matricesutilisées en pratique par les biologistes. JASPAR (Sandelin et al., 2004) est aussi assezcomplète, et dispose de l'avantage d'être libre de droits, mais dispose de moins de motifs(une centaine). Pour ne pas créer d'artefact en incorporant des motifs dupliqués, nousavons choisi de nous limiter à TRANSFAC.

Les 400 matrices sont contruites à partir de motifs de tailles très variables, allant de5 à 30 nucléotides ; la longueur moyenne est proche de 14 résidus (�gure 5.1). Si on s'in-téresse aux séquences sources utilisées pour la dé�nition des matrices, on remarque unegrande hétérogénéité parmi les di�érents motifs. Si certaines matrices ont été construitesavec des données en très grand nombre (jusqu'à 389 séquences), la moitié l'ont été avecmoins de 20 séquences, et le quart avec moins de 12.

Il est donc important de savoir dans quel domaine les algorithmes peuvent être utili-sés. Si l'on peut penser que les petites matrices ne posent que peu de di�cultés, ce n'estplus le cas dès lors que le nombre de nucléotides devient important. La con�ance dans lesrésultats obtenus avec de telles matrices, étant données les informations expérimentalessur lesquelles elles sont construites, sera étudié dans le chapitre 6.

5.1.2 Un critère commun aux di�érentes matrices

Disposant de ce nombre important de matrices, il nous faut ensuite être capables deles comparer. Le z-score est une mesure populaire pour estimer la signi�cativité d'unscore en temps qu'écart à la distribution attendue ; il est facile à calculer, de manièregénérale, et tout spécialement dans notre cas. Il existe plusieurs dé�nitions de cettemesure. La plus classique est la suivante : pour un mot H dans une matrice donnée, ona :

Z(H) =S(H)− E(M)√

V (M)

où S(H) représente le score du mot, et E(M) et V (M) respectivement l'espérance etla variance de la matrice. Le calcul est immédiat, car nous disposons en temps linéairedes mesures de l'espérance et de la variance d'une matrice. De plus, le z-score maximumest donné par le mot de meilleur score dans la matrice, qui ne pose aucune di�culté(section 3.2) :

Zmax =Smax − E(M)√

V (M)

L'idée initiale que nous avons développée était donc de choisir un seuil qui soit unefraction choisie du z-score maximum de chaque matrice (par exemple 95 ou 98%). Il acependant été montré (Régnier et Vandenbogaert, à paraître, Vandenbogaert,2004) que cette mesure sou�re de défauts important en termes de sensibilité et de spé-ci�cité. Nous avons pu véri�er cette di�culté sur nos données.

1TRANSFAC est accessible à l'adresse suivante : http://www.gene-regulation.com/pub/

databases.html et peut être utilisée librement dans le cadre académique.

34

35 CHAPITRE 5. COMPARAISON DES ALGORITHMES POUR HS

Longueur (nuc.)

Fré

quen

ce

0 5 10 15 20 25 30

010

2030

40

Nombre de séquences sources

Fré

quen

ce

0 100 200 300 400

020

4060

8010

012

0

Longueur Nombre de séquences sourcesQuantile 0% 25% 50% 75% 100% 20% 30% 50% 60% 80% 100%Valeur 5 10 13 16 30 10 14 20 24 39 398

Fig. 5.1 � Répartition des matrices de TRANSFAC en fonction de leur taille et dunombre de séquences sources.

Pour e�ectuer des comparaisons plus �ables, nous avons donc dû choisir le critère plusapproprié de la p-valeur. Cette valeur ne peut être déterminée de manière immédiate :on ne dispose pas d'outils autres que la fonction génératrice pour calculer la p-valeurassociée à un seuil s. Or la fonction génératrice complète est souvent inaccessible aucalcul et l'on doit procéder par étapes avec la fonction génératrice tronquée. Nous avonsdonc avant notre simulation calculé la p-valeur associée aux scores pour chacune des392 matrices, dont nous nous sommes ensuite servis. Ce calcul peut se faire de manièreitérative selon la méthode décrite en 3.2.3. En pratique nous n'avons pas connu dedi�cultés, au moins jusqu'à une p-valeur de 10-3 qui permet de couvrir des cas de �gurepratiques. Une p-valeur plus grande n'est généralement pas assez signi�cative : un grandnombre de mots est généré même pour des p-valeurs faibles, et il n'est pas intéressant dechercher des mots qui pourraient être présents de manière aléatoire dans les séquencesétudiées.

Pour une p-valeur �xée (nous avons choisi une valeur de 10-6) et un nombre de chi�ressigni�catifs de 3 (un bon compromis entre précision du calcul et e�cacité d'après l'étudeplus détaillée du chapitre 6), nous avons calculé dans un premier temps la durée néces-

35


saire à la construction de la structure de Hs. Ce temps inclue le calcul de la structure dedonnées, mais pas l'énumération des mots qu'elle contient. Il faut noter que les p-valeursminimales pouvant être générées par les matrices vont de 10-4 pour les plus courtes jus-qu'à 10-19 pour le motif le plus long de 30 résidus. On voit ici aisément que pour unemême signi�cativité statistique, le nombre de mots construits va considérablement va-rier en fonction de la taille du motif. C'est cette variation de la taille de Hs qui reste laprincipale limite des calculs e�ectués sur les grandes matrices.

Nous avons aussi étudié la structure elle-même. Nous ne disposons pas d'une mesurepour calculer l'écart ou la di�érence entre les di�érentes structures construites. Étantdonnée la taille des ensembles obtenus, même condensés dans les structures, il est éga-lement impossible d'observer directement cet écart. Nous avons donc dû nous contenterpour chaque algorithme de la mesure du nombre de noeuds créés, du nombre d'arrêtspréventifs e�ectués, du nombre de jokers utilisés ou bien encore du nombre de scoreségaux rencontrés.

5.2 Domaine d'utilisation

La p-valeur de 10-6 utilisée pour les simulations in�ue bien sûr sur les résultats,puisque toutes les simulations n'ont pas pu se terminer sur la machine que nous avonsutilisée (un Pentium 4 avec 512 Mo de RAM). Néanmoins c'est un seuil qui est déjàsigni�catif et représentatif des limites d'utilisation des algorithmes. En e�et, les mêmessimulations réalisées avec des p-valeurs de 10-4 et 10-8 ont montré des résultats trèssimilaires.

Comme nous nous y attendions, le temps de calcul est exponentiel en la taille dela matrice. Si les petites matrices ne posent aucune di�culté, il n'en est pas de mêmedès que la taille devient conséquente. Aucun des algorithmes n'a pu réaliser la struc-ture de Hs pour l'ensemble des matrices (tableau 5.1). L'algorithme naïf � c'est à diren'utilisant que la première propriété du théorème 4.1.1 � atteint très vite ses limiteset devient parfois ine�cace dès 14 résidus. Les di�érentes optimisations apportées per-mettent d'étendre le domaine d'étude (certaines des plus grandes matrices sont mêmeaccessibles), mais il reste toujours un grand nombre de cas di�ciles. La réussite del'algorithme est aléatoire dès que le nombre de résidus est supérieur à 18, ce qui n'est�nalement qu'un gain limité. Il peut néanmoins aussi s'expliquer par la croissance dela complexité : gagner un résidu coûte à chaque fois 3 à 4 fois plus que précédemmenten moyenne. Nous avons repoussé les limites du domaine d'études mais pas obtenu desrésultats su�sants pour avoir accès à toute l'information recherchée. Il reste donc en-core beaucoup de travail avant d'obtenir des algorithmes e�caces pour l'ensemble descas biologiques.

36


Taille 0 à 13 14 15 16 17 18 à 21 22 à 30

Taux deréussite

naïf

avec jokerscores égaux

100 88.6 88.2 72.7 9.1 0 0100 90.9 91.2 84.8 18.2 0 0100 100 100 97.0 81.8 54.0 14.3

Nombre de motifs 204 44 34 33 11 46 35

Tab. 5.1 � Taux de réussite des di�érents algorithmes en fonction de la taille du motif.Les données ont été parfois regroupées car trop peu de matrices étaient disponibles.

5.3 Apports et limites des di�érents algorithmes

L'ajout des jokers à l'algorithme naïf � prise en compte de la 2ème propriété duthéorème 4.1.1 � est un gain �nalement minime puisque très peu d'algorithmes ayantéchoué avec la technique naïve ont pu être menés au bout. Ce résultat était attendu,car en se plaçant à des seuils de p-valeur petits, on s'attend à avoir peu de cas où tousles pré�xes sont valides : il y a d'autant plus de jokers que le nombre de mots générésest grand, ce qui s'oppose à l'idée de ne sélectionner que les mots les plus signi�catifset donc exceptionnels. Plus on souhaite travailler sur des p-valeurs signi�catives, plusl'apport est négligeable.

Par contre, l'apport des scores égaux est beaucoup plus intéressant. Il permet ainside construire des ensemble pour des matrices de taille bien plus importante, et a mêmeété e�cace pour certaines des plus grande matrices (taille 28). Pour les motifs pourlesquels tous les algorithmes réussissent, nous avons représenté le temps de calcul moyen(�gure 5.2). Les temps relatifs montrent bien le gain signi�catif de l'utilisation des scoreségaux, à partir d'une taille de 10 résidus environ. On peu supposer que cette tendancese con�rme pour des tailles supérieures (non représentées car les autres algorithmes neréussissent pas).

Notons au passage la grande variabilité des résultats malgré l'utilisation de la p-valeurcomme critère, qui illustre la particularité de chaque matrice : il y a souvent plusieursordres de grandeur pour le temps de calcul entre deux matrices de même taille (nonillustré dans le rapport). On peut supposer que cette variabilité est liée également enpartie au moment où les scores égaux interviennent dans la structure, mais les résultatsde nos simulations n'ont pas permis de le mettre en évidence. En e�et, si les scores égauxapparaissent tôt, le gain sera beaucoup plus important pour la taille de la structureque s'ils se présentent tardivement, car ils évitent la répétition de sous-arbres (�gure5.3(a)). De même, le résultat est aussi dépendant de la variabilité interne des mots : siun di�érence de score � même minime � se fait tôt dans les premiers résidus, alors denombreuses branches, parfois très semblables vont être créées, ce qui n'est pas le cas plustardivement (�gure 5.3(b)). De la sorte, il peut y avoir une di�culté à la condensationde l'information. Ces deux problèmes sont liés à notre choix de parcours des mots, de lagauche vers la droite.

On pourrait choisir pour améliorer la situation d'utiliser non pas l'ordre de lecturedes lettres du motifs, mais un ordre lié d'abord aux scores : on considère en premier

37


1

0 6 8 10 12 14 16T

emps

rel

atifs

Taille du motif

107

106

105

104

103

Tem

ps m

oyen

(m

s)

naifavec jokers

scores egaux

Fig. 5.2 � Temps moyen de calcul des algorithmes pour les matrices de taille 5 à 16. Àpartir de la taille 14 le gain par rapport à l'algorithme naïf est sous-estimé car toutesles simulations n'ont pas pu se �nir pour ce dernier. Au delà de 16, trop peu de résultatssont disponibles pour comparer les algorithmes.

38


••

•••• ••

(a) Égalité précoce ou tardive

A

T

T

C

C

G

G

T

C

C

G

C

T

C

C

G

(b) Structure en gri�e

Fig. 5.3 � Limitations de la structure de donnée utilisée. (a) Selon que l'égalité desscore à lieu tôt ou tard dans le mot, la structure pourra être condensée e�cacement oubien au contraire mener à une grande redondance. (b) Des scores très proches mais nonidentiques peuvent conduire à des su�xes identiques qui seront répétés dans la structure.Ces limitations peuvent expliquer la grande variabilité observée dans le comportementdes di�érentes matrices.

les colonnes qui créent le plus de score égaux puisque ce critère semble déterminant. Ladi�culté serait alors de réussir à reconstituer les mots à partir de la structure désordon-née. Pour que cela soit intéressant, il faut que cette opération soit e�cace, ce qui n'estpas trivial.

Une autre piste pour améliorer l'e�cacité de l'algorithme concerne les scores proches,égaux à un ε près. En e�et, de tels noeuds possèdent des sous-arbres très proches, souventidentiques (on retrouve le problème évoqué ci-dessus et en �gure 5.3(b)). En s'assurantde quelques propriétés, nous pensons qu'il est possible de partager les sous-arbres demanière plus importante qu'actuellement. Ce travail est en cours (communications pri-vées).

39

Chapitre 6

Robustesse et chi�res signi�catifs

Les PSSM sont construites comme des objets mathématiques, dé�nis très précisé-ment. Par exemple, on utilisera une matrice en dé�nissant un seuil donné en dessousduquel aucun motif ne sera retenu. C'est un critère fort, qui a son importance dans laréalisation des algorithmes et leurs résultats. L'aspect théorique des PSSM est souventnégligé lors de leur utilisation en pratique. Pourtant, il est primordial de connaître la�abilité des résultats obtenus. Deux critères nous semblent particulièrement importants,que nous avons choisi d'étudier plus en détail :

1. le choix du nombre de chi�res signi�catifs utilisés dans les algorithmes,

2. la robustesse de la matrice vis-à-vis des séquences qui ont servi à sa construction.

6.1 Distribution des scores en fonction du nombre de

chi�res signi�catifs

Le choix du nombre de chi�res signi�catifs dans la construction de la matrice peutparaître anodin au premier abord. En e�et, pourquoi ne pas garder toute la précisiondont on dispose lorsque on transforme les comptages de nucléotides en scores ? Il y a deuxraisons essentielles à cela. La première veut que l'on ne doit pas garder une précisionchi�rée supérieure à celle dont on dispose à l'origine avec les sources. Si une matriceest construite avec 10 éléments, il n'est pas concevable de garder des scores avec 6 ou9 chi�res après la virgule. La deuxième est beaucoup plus pragmatique : nous avons vuau chapitre 4 que les calculs sur la distribution des scores mettent en jeu des polynômesparfois de très grande taille. Or justement le nombre de termes est directement reliéà la précision, car deux scores considérés comme identiques sont réunis au cours ducalcul (de par l'indépendance des colonnes, ce qui compte est le score considéré et nonpas la manière dont il s'est construit auparavant). Il est donc préférable de ne garderqu'un minimum de chi�res signi�catifs dans cette optique. La contrepartie est bien sûrla précision que l'on garde sur nos résultats. Quel est alors le choix à faire ? Dans cettepartie, nous nous sommes intéressés à la relation entre gain en précision et coût enfonction du nombre de chi�res signi�catifs utilisés.

41


6.1.1 Comportement global

Nous avons choisi d'étudier ce comportement pour le motif met31 (Gonze et al.,2005) qui est impliqué dans le métabolisme de la méthionine et du phosphate chez lalevure.

Dans un premier temps, la �gure 6.1 illustre visuellement la courbe de distributiondes scores, à un niveau global et au niveau de la queue de distribution qui est le domainequi nous intéresse plus particulièrement puisqu'il est représentatif de scores exception-nels. De manière générale, toutes les courbes sont très proches les unes des autres, mais sion se place au niveau de détail qui nous intéresse, les disparités peuvent être importantes.Cependant, les courbes pour 3 et 6 chi�res signi�catifs sont quasiment indiscernables.Le comportement global de la distribution des scores d'une matrice poids-position aglobalement la forme d'une sigmoïde.

On remarquera au passage qu'un décalage constant semble exister parfois entre 2courbes de précision di�érente. Celui-ci est particulièrement visible pour la courbe avecun seul chi�re signi�catif qui semble être constamment placée à gauche des autres. Enfait, cela n'est plus vrai pour la queue de la distribution (le décalage se fait dans l'autresens). Ce phénomène est justement lié à la précision sur le score : un léger décalage créeau début peut se propager très longtemps ensuite. Prenons par exemple un score exactà un moment donné de 1.45678, on l'arrondit à 1 dans un premier cas, et à 1.46 dans lesecond. Supposons que score suivant est 1.4789, arrondi encore une fois à 1, et à 1.48. Ledécalage semblera très important mais n'est �nalement qu'un artefact dû à la précisiondu calcul.

6.1.2 Précision et coût de calcul

Nous avons poursuivi notre étude et tenté d'évaluer la relation entre nombre dechi�res signi�catifs et précision. En particulier, une question à laquelle il est importantde répondre est celle de la précision à utiliser dans les calculs pour obtenir des résultats�ables et accessibles à la fois. L'étude des courbes peut nous donner certaines indicationsmais il est nécessaire de réaliser une étude plus approfondie du phénomène.

Pour cela, toujours sur met31, nous avons calculé pour di�érentes précisions l'éloi-gnement de la distribution des scores observée à la distribution idéale si les valeursde scores exactes étaient utilisées. Bien entendu, il est impossible numériquement deconnaître les valeurs exactes qui supposent une précision in�nie, et nous sommes éga-lement limité par les capacités de calcul des outils utilisés. Nous avons néanmoins pucalculer la distribution obtenue avec 7 chi�res signi�catifs, que nous avons choisie commecourbe de référence. Il est de toute manière inutile de considérer des résultats plus précisqui n'apportent plus d'information.

Pour estimer cet éloignement, nous avons calculé l'aire absolue qui sépare les 2courbes. Comme il s'agit de deux fonctions en escalier, il est très aisé de calculer l'airequi les sépare. Les résultats ont été comparés à la taille du polynôme nécessaire à lareprésentation des données (�gure 6.2).

42

43 CHAPITRE 6. ROBUSTESSE ET CHIFFRES SIGNIFICATIFS

0

0.2

0.4

0.6

0.8

1

-20 -15 -10 -5 0 5 10 15

p-va

leur

Score

1236

0

2e-08

4e-08

6e-08

8e-08

1e-07

9 10 11

Fig. 6.1 � Courbes de distribution des scores pour le motif met31. Comportement globalet zoom sur la queue de distribution.

Comme on s'y attendait, le coût du calcul augmente exponentiellement avec sa pré-cision. Le gain, lui, est au contraire de plus en plus faible : il coûte de plus en pluscher d'augmenter le nombre de chi�res signi�catifs, et ce pour un résultat de moins enmoins intéressant. D'un point de vue pratique, il semble qu'une précision �nalementassez faible (2 ou 3 chi�res signi�catifs) soit su�sante pour obtenir des résultats cor-rects. Remarquons au passage que la précision du calcul est �nalement d'une importancelimitée :

� si on s'intéresse à la p-valeur, car l'ordre de grandeur su�t pour avoir une idée dela signi�cativité d'un score.

� si on la rapporte à l'ensemble Hs des mots puisque la perte de précision ne peutavoir que des e�ets de bords : quelques mots seront ôtés ou ajoutés à l'ensemble,mais ne peuvent pas changer considérablement l'information qu'il contient.

6.2 Robustesse d'une matrice

Dans cette deuxième partie, nous avons voulu étudier la robustesse d'une matrice,c'est-à-dire la con�ance que l'on peut avoir dans une matrice étant données les informa-tions sur lesquelles elle a été construite. En e�et, le processus décrit en 3.1.2 impliquele choix d'un certain nombre de séquences pour construire la PSSM. Cet outil est en-

43


0

0.001

0.002

0.003

0.004

0.005

6 5 4 3 2 1 0

100000

200000

300000

400000

500000

Eca

rt (

u.a)

Tai

lle d

u po

lyno

me

Nombre de chiffres significatifs

Taille du polynome

Ecart a la reference

Fig. 6.2 � Précision du calcul et dimension de la fonction génératrice des score. Lecoût exponentiel exigé pour construire le polynôme est inversement proportionnel à laprécision gagnée. L'écart �uctuant observé pour 2 et 3 chi�res signi�catifs s'explique parle phénomène de décalage dû aux arrondis.

suite généralement utilisé sans grande attention vis-à-vis de la manière dont il a étéconçu. Nous avons déjà évoqué le problème du choix du nombre de chi�res signi�catifsà conserver, ainsi que celui des bornes de la matrices lors de la construction (3.1.1). Uneautre limitation fondamentale n'est pas à négliger : que se passe t-il si on oublie uneséquence lors du choix initial des motifs ? Quelle in�uence peut avoir l'inclusion malheu-reuse d'une séquence erronée en termes de mots introduits et ôtés de Hs ? En e�et, lenombre de séquences utilisée pour construire la matrice est variable, mais souvent assezfaible : pour la banque de données TRANSFAC, celui-ci s'étale entre 4 et 389, pour unemédiane de 20. Dans ces conditions, peut-on évaluer le risque encouru ? La solution quenous avons choisi consiste à perturber nos PSSM, c'est à dire à construire des matricesà partir d'une fraction des séquences initiales.

Pour ce faire, nous ne pouvons pas utiliser TRANSFAC, car nous n'avons pas accèsaux séquences qui ont servi à construire les matrices. Or c'est un critère important, caron ne peut raisonnablement perturber une matrice en ôtant au hasard un élément danschacune des colonnes. Bien que le modèle retenu suppose des positions indépendantes,sa construction suppose tout de même de choisir des séquences représentatives. Le nonrespect de cette règle peut conduire à l'apparition d'artefacts, et donc nous avons dûrenoncer à e�ectuer nos mesures de perturbation à partie des données de TRANSFAC.

44


Il faut noter par ailleurs que tous nos problèmes ne sont pas résolus quand nousdisposons des séquence ayant servi à la construction des matrices. D'une part, on nepeut de cette manière qu'ôter des séquences, et donc étudier seulement ce qui se passelorsque des séquences sont oubliées dans la construction du modèle ; on peut parler alorsde validation expérimentale. Il est beaucoup plus di�cile d'observer les conséquences del'ajout d'une séquence étrangère : sur quoi pouvons nous nous baser ? L'extrapolationdes résultats obtenus en supprimant certaines séquences à ceux liés à l'ajout d'unesource n'est pas évidente. D'autre part, il se peut que construire une matrice perturbéeoblige à l'introduction de pseudo-comptes, et ce d'autant plus lorsque l'on dispose depeu de séquences expérimentales, ou bien quand certaines positions sont très strictes.Néanmoins, cette di�culté est la même pour l'expérimentateur qui construit sa proprematrice en oubliant une séquence donnée, et on peut considérer que ce processus faitpartie du phénomène de perturbation tel qu'il est rencontré en pratique.

Nous avons donc choisi de travailler sur des matrices de Papatsenko et al. (2002),construites à partir de données sur la drosophile. Neuf sont exploitables. Elles repré-sentent un certaine diversité de par leur taille et le nombre de séquences sur lesquelleselles sont construites et permettent d'avoir une idée du comportement global. La pro-cédure de perturbation est présentée en �gure 6.3. Nous nous sommes alors posé 4questions di�érentes pour évaluer l'impact d'un perturbation de la matrice :

1. En supposant que toutes les séquences introduites sont expérimentalement valides,un seuil raisonnable pour la recherche de motifs est le plus petit seuil obtenu parles séquences dans la matrice qu'elles ont servi à construire. Quel est alors la p-valeur associé à ce seuil ? Comment se di�érencient les ensembles de mots lorsqueune séquence est ôtée ?

2. Une séquence a été ôtée. Où se situait son score auparavant, quel est-il dans lamatrice perturbée ?

3. On suppose que la séquence expérimentale manquante a été oubliée. Les ensemblesainsi construits sont-ils proches ou bien au contraire l'absence ou la présence dela séquence est-il primordial ? Ce test peut être vu comme une validation expéri-mentale de la matrice.

4. Quelle est l'in�uence de la perturbation sur les ensembles pour une même p-valeur ?

En�n, il est aussi intéressant d'évaluer l'importance relative de ce phénomène vis-à-visdu choix du nombre de chi�res signi�catifs.

6.2.1 Comparaison des ensembles expérimentaux

Dans un premier temps, nous nous sommes donc intéressés aux ensembles expéri-mentaux de mots construits pour une matrice. Dans l'optique d'identi�er les mots po-tentiellement intéressants, il peut sembler raisonnable de choisir dans un premier tempsun seuil s tel que l'ensemble de mots Hs ainsi déterminé contienne les motifs validésexpérimentalement, c'est-à-dire ceux qui ont servi à construire la matrice elle-même. Onpeut pour cela choisir par exemple le score le plus faible de l'ensemble de ces motifs dansla PSSM. Nous avons comparé les ensembles produits originellement avec ceux produitsune fois la matrice perturbée.

45


A A C T G C G C T. . .

. . .i M

M′1

. . .

M′N

Simulations

(toutes

séq.)

(suppression séq. 1)

(suppression séq. i)

(suppression séq. N)

Fig. 6.3 � Procédure utilisée pour les simulations de robustesse. Di�érentes matricessont construites à partir des séquences sources : une matrice M qui est la matrice deréférence, et les matrices M′

1 à M′N qui sont calculées après qu'une des séquences ait

été supprimée.

Très rapidement, on se rend compte que les ensembles ne peuvent être énumérés pourla plupart des matrices dont nous disposons. Ils n'ont pu être déterminés que pour les 3motifs les plus courts dont nous disposons : ftz, knirps et tramtrack. Pour des longueurssupérieures, ces ensembles sont très grands, et les ressources nécessaires pour construirela structure de données excèdent la capacité de l'ordinateur que nous avons utilisé pourles simulations. Malgré cela, on dispose tout de même d'un nombre de sources varié,respectivement 22, 16 et 7.

On notera tout d'abord que les p-valeurs associées aux ensembles construits sont del'ordre de 10-2 à 10-4 (tableau 6.1). Cette valeur est faible, parfois très faible, et con�rmel'idée généralement retenue selon laquelle les matrices poids-position sont peu spéci�queset produisent énormément de faux positifs. Elle explique aussi pourquoi nous avons eudes di�cultés à construire les ensembles pour les matrices de taille supérieure, on peutestimer la taille approximative des ensemble construits par la formule suivante :

|Hestime| ≈ 4|M| × pvalexp

Les résultats des simulations sont présentés dans le tableau 6.2. Globalement, bien queftz obtienne des résultats corrects, les ensembles construits sont assez distincts, ce quimontre une forte dépendance à la perturbation. Cette relation semble directement liéeau nombre de séquences à partir desquelles les matrices ont été construites, puisque surles 3 motifs la perturbation est inversement proportionnelle au nombre de sources donton dispose.

Pour le véri�er malgré les données insu�santes dont nous disposions, nous avonsconstruit des matrices factices à partir de knirps, en ôtant aléatoirement un nombre variéde séquences et non plus une seule. Nous avons ainsi disposé de matrices construites àpartir de 6 jusqu'à 16 mots. Ces matrices ont ensuite été perturbées selon la mêmeprocédure que précédemment. Les résultats obtenus con�rment ceux entrevus sur les 3premiers motifs, puisque la fraction de mots communs entre l'ensemble construit à partir

46


Motif ftz knirps tramtrack bicoid pairedHDP-valeur 1.66e-02 1.49e-02 1.62e-04 2.72e-03 2.65e-04|Hestime| 17 400 250 000 10 900 730 150 284 500

Motif kruppel tailless caudal hunchbackP-valeur 1.81e-02 1.22e-02 1.02e-03 8.78e-03|Hestime| 77 738 900 52 398 600 17 523 450 9 427 450

Tab. 6.1 � P-valeur et taille estimée des ensembles expérimentaux. Les estimations de|Hs| correspondent bien avec les valeurs relevées pour les 3 plus petits motifs.

|Hs∩H′s|

|Hs∪H′s|× 100 |H′

s||Hs| × 100

Motif Nb. séq. |Hs| min max moy min max moyftz 22 13293 60.3 91.3 82.8 76.5 165.0 92.0

knirps 16 266680 45.1 85.5 73.9 67.2 221.3 107.5tramtrack 7 19336 13.6 61.3 45.6 13.6 153.8 72.2

Tab. 6.2 � Taille des ensembles expérimentaux et comparaison des ensembles. La per-turbation semble directement liée au nombre de séquences disponibles.

de la séquence initiale et l'ensemble perturbé diminue avec le nombre de sources donton a disposé pour l'élaboration de la PSSM.

Il est dommageable tout de même de ne pas avoir pu obtenir de résultats pourpar exemple bicoid et hunchback qui eux possèdent un plus grand nombre de sources,knirps étant construit sur seulement 16 séquences. On peut donc malgré tout s'interrogerà juste titre sur la con�ance à accorder à de telles matrices, puisque comme nous l'avonsévoqué en 5.1.1, près de la moitié des séquences de TRANSFAC ont justement moinsde 20 sources.

6.2.2 Positionnement des séquences ôtées

Nous avons ensuite voulu étudier la position qu'occupe une séquence dans la nou-velle matrice une fois qu'elle a été ôtée, relativement aux autres matrices qui ont ellesété gardées pour la construction. En e�et, le système sera d'autant plus stable qu'uneséquence ôtée a le moins d'in�uence, c'est-à-dire qu'elle se retrouve à la même positionpar rapport aux autres séquences dans la matrice originale et dans la matrice perturbée.On s'attend donc pour une bonne matrice à retrouver la séquence éliminée incluse ausein des séquences restantes, une séquence �anquante ayant éventuellement tendance àse positionner légèrement à l'extérieur. Nous avons e�ectué cette étude pour chacunede nos neuf matrices. Pour pouvoir comparer les comportements respectifs de celles-ci,nous avons ensuite centré et réduit les données, de telle sorte que les bornes dé�nies parle plus grand et le plus petit des scores des séquences expérimentales (resp. smax et smin)

47


ftz

knirps

tramtrack

bicoid

pairedHD

kruppel

tailless

caudal

hunchback

Fig. 6.4 � Positionnement des mots éliminés dans la matrice perturbée. Les donnéesont été centrées et réduites pour pouvoir comparer les comportements. Les deux barresverticales représentent pour chaque matrice perturbée les scores les plus bas et les plushaut des séquences expérimentales conservées pour construire la matrice poids-position.Les motifs ont été ordonnés selon le nombre de séquences sources disponibles (de 7 pourtramtrack et pairedHD à 43 pour hunchback).

soient alignées (�gure 6.4). La formule suivante a été appliquée :

sreduit =s− smin+smax

2

smax − smin

.

Les motifs ont été ordonnés selon le nombre de séquences ayant servi à leur construc-tion. Visuellement, il apparaît clairement que les matrices sont d'autant plus stables quece nombre est grand. On peut noter le cas particulier de pairedHD pour lequel aucuneséquence ôtée ne se retrouve correctement positionnée : une séquence ôtée a dans lamatrice perturbée un score plus faible que le plus petit score des séquences retenues.

On remarquera également une asymétrie entre les scores situés respectivement àgauche et à droite des bornes dé�nies. Ceci s'explique par l'in�uence que peut avoirla suppression d'un score. Supprimer un score élevé revient à créer un matrice plussouple vis-à-vis des mots acceptés, et de ce fait les scores ont tendance à être écrasés, ladistinction entre 2 mots est moins nette. Au contraire, supprimer une séquence de faiblescore va renforcer la sensibilité de la matrice. Dans ce cas, les écarts entre les mots vontaugmenter.

48


10 15 20 25 30 35 40

010

2030

4050

60

Nombre de sources

Rap

port

Fig. 6.5 � Rapport de taille nécessaire pour retrouver les motifs expérimentaux.

6.2.3 Validation expérimentale

Le troisième test que nous avons réalisé part du principe que les ensembles construits,bien que perturbés, doivent être proches de l'ensemble initial. Plus encore, idéalementtous les mots construits avec la matrice initiale devraient être trouvés à nouveau dansl'ensemble perturbé. C'est cet aspect que nous avons développé ici : quel seuil doit-onchoisir de sorte que l'on retrouve dans l'ensemble perturbé la totalité des mots présentsau départ ? La question qui nous préoccupe est celle de la taille de l'ensemble construitrelativement à l'initial. On s'attend bien entendu à ce que le rapport soit supérieur ouégal à un, mais plus ce rapport est proche de l'unité, plus l'ensemble est stable. Aucontraire, un rapport élevé signi�e que de nombreux mots qui n'étaient pas dans Hs ontdans la nouvelle matrice un score meilleur que certains des mots retenus : la structuredes mots décrite par la matrice n'est plus la même, et on a introduit ou perdu des motifsparticuliers.

La �gure 6.5 montre l'évolution de ce rapport en fonction du nombre de sourcesdisponibles pour les matrices. Si le point correspondant au motif pairedHD, situé enhaut à gauche, écrase quelque peu les données, on observe malgré tout une tendancetrès nette à avoir un rapport de taille d'autant plus petit que le nombre de séquencesest important. Il y a encore une fois une in�uence directe et notable des sources sur lastabilité des résultats.

49


10 20 30 40

0.0

0.1

0.2

0.3

0.4

0.5

0.6

Nombre de sources

Fau

x po

sitif

s

10 20 30 40

0.0

0.1

0.2

0.3

0.4

0.5

0.6

Nombre de sources

Fau

x né

gatif

s

Fig. 6.6 � Évolution du taux de faux positifs et faux négatifs en fonction de la taille dumotif.

6.2.4 Stabilité des p-valeurs

Dans cette dernière partie, nous avons observé la ressemblance des ensembles cons-truits pour une p-valeur donnée. La vision est proche de celle des ensembles expérimen-taux (6.2.1), mais cette fois-ci, pour une p-valeur donnée nous construisons les ensemblesà partir des matrices perturbées et non perturbées et les comparons ensemble. Il est icipossible de faire l'étude pour toutes les matrices dont nous disposons en choisissant unep-valeur raisonnable.

Nous avons regardé 2 critères : les classiques taux de faux positifs et faux négatifs(�gure 6.6). Disposant cette fois-ci d'un nombre de données plus important, il est possibled'avoir une idée visuelle du comportement des matrices sans avoir recours à des artefactsde simulation.

Cette dernière expérience met encore une fois en évidence l'importance du nombre desources pour la robustesse et la �abilité de la matrice, puisque le taux de faux positifscomme de faux négatifs diminue lorsque la taille de l'ensemble de mots déterminésexpérimentalement augmente. Il est di�cile de tirer des conclusions catégoriques étantdonné le peu de matrice analysées, mais il semble tout de même important de disposerd'au moins 20 séquences pour obtenir une stabilité importante quant aux résultats. Àl'opposé, à partir de ce seuil là il semble que l'instabilité se maintienne bien que les

50


sources soient en plus grand nombre.

51

Chapitre 7

Conclusion

7.1 In�uence de la précision du calcul et des sources

Nous avons jusqu'à présent comparé séparément l'in�uence des chi�res signi�catifsutilisés lors des calculs et la robustesse de la matrice vis-à-vis des séquence utilisées enamont. Bien que ces deux critères agissent à des niveaux di�érents sur la matrice, tousdeux peuvent avoir une in�uence importante sur les résultats obtenus. Il nous est di�cilede comparer directement leur in�uence respective.

Pour autant, certains enseignements ressortent des expériences que nous avons me-nées. En ce qui concerne le nombre de chi�re signi�catifs utilisés, il semble inutile deconserver une trop grande précision, et deux ou trois chi�res su�sent. Ces résultats sontcon�rmés dans le cadre d'utilisations concrètes par Valya Boeva (communications pri-vées). En e�et, l'in�uence ce fait essentiellement au niveau des bornes, autour du seuilde sélection. L'imprécision engendrée conduit donc à inclure ou rejeter quelques mots del'ensemble Hs, mais ce n'est �nalement qu'une proportion limité de l'ensemble solution.

Au contraire, l'e�et dû à la perturbation des séquences sources semble beaucoup plusimportant. Le jeu de données limitées sur lequel nous avons travaillé ne nous permetpas d'avoir su�samment de recul ; il aurait été intéressant d'avoir accès aux sources deTRANSFAC par exemple pour con�rmer nos impressions. Pour autant, notre travail estun premier pas vers le développement d'un outil à l'intention des biologistes pour évaluerla qualité intrinsèque des matrices. Nous avons dé�ni un certain nombre de questions,et proposé certaines méthodes pour y répondre. Un de nos projets est de développer cesaspects dans une future collaboration, car c'est un sujet à notre avis d'un grand intérêtpour beaucoup de personnes.

7.2 Extensions du travail sur Hs

Nous avons proposé un algorithme e�cace pour représenterHs de manière condensée.Comme nous l'avons discuté dans le chapitre 5, il reste encore du travail à faire pour op-

53


timiser une telle construction. Une autre évolution intéressante serait l'intégration dansl'algorithme développé actuellement par Mireille Régnier, Julien Clément et ValyaBoeva : pour calculer la p-valeur d'un ensemble de mots sur un texte de longueur n �P (Hs)n � l'entrée est l'ensemble Hs des mots. C'est un facteur limitant car cela supposed'énumérer cet ensemble. Si nous parvenons à utiliser e�cacement notre structure dedonnées condensée et à éviter ce passage, il sera possible d'abaisser la complexité ducalcul.

Une autre piste de recherche étudiée concerne une représentation de l'arbre des motse�cace. Le lien avec la représentation par une séquence de type IUPAC permettrait demieux appréhender la structure de l'ensemble.

54

Bibliographie

V. Boeva, J. Clément, M. Régnier et M. Vandenbogaert : Assessing the signi-�cance of sets of words. In Springer-Verlag, éd. : CPM'05, Jeju Island, Korea,vol. 3537 de Lecture Notes in Computer Science, p. 358�370, 2005.

R. C. Deonier, S. Tavaré et M. S. Waterman : Computational Genome Analysis :An Introduction. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2005. ISBN0387987851.

R. Durbin, S. R. Eddy, A. Krogh et G. Mitchison : Biological Sequence Analysis.Models of Proteins and Nucleic Acids. Cambridge University Press, 1998.

D. Gonze, S. Pinloche, O. Gascuel et J. van Helden : Discrimination of yeastgenes involved in methionine and phosphate metabolism on the basis of upstreammotifs. Bioinformatics, 21(17):3490�3500, 2005.

L. Hertzberg, O. Zuk, G. Getz et E. Domany : Finding motifs in promoter regions.Journal of Computational Biology, 12(3):314�330, 2005.

H. Huang, M.-C. J. Kao, X. Zhou, J. S. Liu et Z. H.Wong : Determination of localstatistical signi�cance of patterns in markov sequences with application to promoterelement identi�cation. Journal of Computational Biology, 11(1):1�14, 2004.

D. E. Knuth : The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series inComputer Science and Information. Addison-Wesley Longman Publishing Co., Inc.,Boston, MA, USA, 1978. ISBN 0201038099.

C. Lawrence, S. Altschul, M. Boguski, J. Liu, A. Neuwald et J. Wootton :Detecting subtle sequence signals : a gibbs sampling strategy for multiple alignment.Science, 262(5131):208�214, 1993.

V.Matys, E. Fricke, R. Geffers, E. Gossling, M. Haubrock, R. Hehl, K. Hor-nischer, D. Karas, A. E. Kel, O. V. Kel-Margoulis, D. U. Kloos, S. Land,B. Lewicki-Potapov, H.Michael, R.Munch, I. Reuter, S. Rotert, H. Saxel,M. Sheer, S. Thiele et E. Wingender : TRANSFAC : transcriptional regulation,from patterns to pro�les. Nucleic Acids Research, 31(1):374�378, 2003.

G. Nuel : S-spatt : simple statistics for patterns on markov chains. Bioinformatics, 21(13):305�3052, 2005.

55


D. A. Papatsenko, V. J. Makeev, A. P. Lifanov, M. Régnier, A. G. Nazina etC. Desplan : Extraction of functional binding sites from unique regulatory regions :the drosophila early developmental enhancers. Genome research, 12(3):470�481, 2002.

S. Robin, J. Daudin, H. Richard, M. Sagot et S. Schbath : Occurrence probabilityof structured motifs in random sequences. Journal of Computational Biology, 9:761�773, 2001.

M. Régnier et M. Vandenbogaert : Comparison of statistical signi�cance criteria.Journal of Bioinformatics and Computational Biology, à paraître. URL http://algo.

inria.fr/regnier/publis/ReVa05.ps. 12 pages.

M.-F. Sagot : On motifs in biological sequences. URL http://citeseer.ist.psu.

edu/473028.html.

A. Sandelin, W. Alkema, P. Engström and Wyeth. Wasserman et B. Len-hard : JASPAR : an open access database for eukaryotic transcription factor bindingpro�les. Nucleic Acids Research, 32(database issue):D91�D94, 2004.

N. Simonis, S. J. Wodak, G. N. Cohen et J. van Helden : Combining patterndiscovery and discriminant analysis to predict gene co-regulation. Bioinformatics, 20(15):2370�2379, 2004.

G. D. Stormo : DNA binding sites : representation and discovery. Bioinformatics, 16(1):16�23, 2000.

M. Vandenbogaert : Algorithmes et Mesures Statistiques pour la Recherche de Si-gnaux Fonctionnels dans les Zones de Régulation. Thèse de doctorat, Université Bor-deaux I, 2004.

D. van Heesch : Doxygen, a documentation system for C++, C, Java, Objective-C,Python and IDL. URL http://www.stack.nl/~dimitri/doxygen/.

J. van Helden, B. Andre et J. Collado-Vides : A web site for the computationalanalysis of yeast regulatory sequences. Yeast, 16(2):177�187, 2002.

56

Documents

Matrices poids-position : principes et algorithmes