Recherche de motifs par méthodes exploratoires:

Comparaisons de performances et statistiques sur le score

Définitions:• Un motif est un ensemble d’occurrences dans les

séquences (taille contrainte)

• La répartition des occurrences est contrainte à une par séquence.

• La fonction objectif est l’entropie relative (ou ratio des vraisemblances)

Définitions• P: espace des motifs (~lmoyN)

• M: espace des mots (KW)

• Deux opérateurs permettent d’établir une correspondance entre les deux espaces.

Définitions• Q: espace des motifs représentables par un mot (selon

l’opérateur de projection)

• Q est inclu dans P

• Q a au plus la taille de M M

P

Q

Les déplacements dans P (hill climbing)

1) Voisinage par séquence (Lawrence et al., Science, 1993)• Un point de P (un motif) est représenté par un vecteur d’entiers à N

dimensions, chaque dimension représentant une position sur la séquence correspondante.

• On ne modifie qu’une dimension à la fois.

• Les dimensions sont prises dans un ordre prédéfini, ou aléatoirement, sans remise.

• On choisit la position qui maximise la fonction objectif (entropie relative)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

Les déplacements dans P (hill climbing)

1) Voisinage par séquence (Lawrence et al., Science, 1993)• Un point de P (un motif) est représenté par un vecteur d’entiers à N

dimensions, chaque dimension représentant une position sur la séquence correspondante.

• On ne modifie qu’une dimension à la fois.

• Les dimensions sont prises dans un ordre prédéfini, ou aléatoirement, sans remise.

• On choisit la position qui maximise la fonction objectif (entropie relative)

Les déplacements dans P (hill climbing)

1) Voisinage par séquence (Lawrence et al., Science, 1993)• Un point de P (un motif) est représenté par un vecteur d’entiers à N

dimensions, chaque dimension représentant une position sur la séquence correspondante.

• On ne modifie qu’une dimension à la fois.

• Les dimensions sont prises dans un ordre prédéfini, ou aléatoirement, sans remise.

• On choisit la position qui maximise la fonction objectif (entropie relative)

Les déplacements dans P (hill climbing)

2) Phase shift (Lawrence et al., Science, 1993)• Le voisinage comprend l’ensemble des vecteurs de position relatifs.

• Opérateur destiné à corriger les motifs ‘mal calés’

Les déplacements dans P (hill climbing)

2) Phase shift (Lawrence et al., Science, 1993)• Le voisinage comprend l’ensemble des vecteurs de position relatifs.

• Opérateur destiné à corriger les motifs ‘mal calés’

Performance de l'exploration:• On mesure la capacité à trouver le

meilleur point possible en un temps donné.

Stratégies d'exploration:• Recherche locale à partir de points

aléatoires de P

• Gibbs sampler (hill-climbing stochastique), à partir de points aléatoires de P

• Recherche locale à partir de points aléatoires de Q

• Recherche locale à partir de points de Q choisis par un algorithme génétique (MoDEL).

• Utilisation d’un set de 16 protéines qui contiennent un domaine HTH.

• Ensemble de séquences construit à partir d’information phylogénétique issue de: Rosinski & Atchley: 1999, molecular evolution of helix-turn-helix proteins

• Protéines distantes: faible conservation entre les sites, quasiment aucune conservation hors des sites.

• Un 'succès' signifie que le maximum supposé a été atteint.

• le taux de succès est estimé sur 100 instances

• CPU: AMD athlon 1.5 GHz

Statistique sur le score

• L’entropie relative (ou log likelihood ratio) mesure une 'distance' entre les fréquences observées dans l'alignement, avec celles du background (=celles qu'on s'attend à trouver pour des alignements aléatoires).

• Cette mesure nous permet de comparer des alignements qui ont les mêmes paramètres libres, à savoir:

• le cardinal de l’alphabet

• le background (paramètres d’une distribution multinomiale)

• la longueur des sites

• le nombre de sites

• le nombre de libertés des sites (~longueur moyenne des séquences si on contraint le modèle à une occurrence par séquence)

• On ne peut donc pas comparer des alignements qui n’ont pas les mêmes paramètres (de longueurs différentes par ex.)

• Une solution est d’utiliser une statistique comme la p-value ou le z-score, (le ‘score du score’ en fonction des paramètres libres).

• Z-score: nombre d’écart-types à la moyenne.

• P-value: probabilité de l’observation quand l’hypothèse nulle est vraie.

• Pval(x) = probabilité d’obtenir un score supérieur ou égal à x par hasard.

• Hypothèse nulle: « Il n’y a pas de motif »

• Randomisation des séquences (on garde les mêmes paramètres libres, mais on détruit les motifs potentiels).

Statistique d’alignement multiple local dans la littérature:

Consensus: (Hertz & Stormo 1999)

P-value: probabilité d’obtenir un score supérieur ou égal, dans un ensemble aléatoire de même nombre de séquences et composition, mais de longueur infinie.

MEME: (Bailey & Elkan 1995)

E-value: nombre d’alignements avec un score supérieur ou égal, que l’on peut s’attendre à trouver dans les séquences randomisées.

HTHs: Résultat de MEME (serveur de l’institut pasteur)

HTHs: Résultats de Consensus: • Capacité exploratoire limitée, ne trouve pas les sites.

HTHs: Statistique de Consensus: (score optimisé par MoDEL)

• Estime une p-value de 1.84E-37 pour le score optimal:

• Estime une p-value de 1.7E-33 pour un score optimisé, avec des séquences randomisées.

• Avantage: rapide (peut être effectuée ‘on the fly’ et permet de détecter la longueur optimale (en tout cas sur les HTHs)

• Désavantage: La valeur ne nous indique pas si on peut 'croire' à l'alignement produit.

Si on veut une signification statistique, une méthode est d’estimer la probabilité d’observer un score optimisé sur les séquences randomisées, qui soit supérieur ou égal au score obtenu sur les séquences originales.

On ne sait pas le faire analytiquement, donc:

• Génération d’échantillons: On optimise un alignement sur un grand nombre de séquences randomisées (~200)

• Fitting de la distribution des scores avec une fonction de densité

• Calcul de la p-value à partir de la fonction de densité

dxexpvalx

baxs s

1)(1

)(

Comparaison d'alignements de différentes longueurs, par rapport à la p-value

Temps de calcul trop important pour une estimation ‘on the fly’

~1 à 3 heures de temps-cpu pour estimer la p-value d’une longueur donnée

Projet: Déterminer les valeurs des paramètres de l'EVD (loc, scale et shape), en fonction des paramètres libres (sans échantillonnage):

• Nombre de sites (nombre de séquences)

• Nombre de libertés des sites (longueur moyenne des séquences)

• Background (entropie des paramètres)

• Longueur de l’alignement

~10 points par dimension:

10’000 * 3 = 30’000h temps-cpu pour échantillonner l’espace.

Comportement de loc, scale et shape en fonction de la longueur: