Filtrage à laide de graines pour lalignement local Laurent Noé [email protected] noe Université Henri Poincaré Travail commun avec

Filtrage à l’aide de graines pourFiltrage à l’aide de graines pourl’alignement locall’alignement local

Laurent Noé

[email protected] http://www.loria.fr/~noe

Université Henri Poincaré

Travail commun avec Gregory Kucherov

PlanPlan

Introduction : alignement local– Définition– Méthodes exactes

Techniques de filtrage– Définition d’un filtre– Exemples de filtres

Méthodes heuristiques pour l’alignement local– Définition d’une graine (ancres)– Méthodes successivement développées

• BLAST-GAPPEDBLAST-BLAT-PATTERNHUNTER-YASS

– Graines-espacées

Design des graines espacées– Waiting Time– Algorithme de Keich– Algorithme de Bulher– Alignements homogènes

Alignement LocalAlignement Local

Alignement– « Processus par lequel deux séquences sont comparées afin

d'obtenir le plus de correspondances (identités ou substitutions conservatives) possibles entre les lettres qui les composent. » http://www.infobiogen.fr

Alignement Local– « Alignement des deux séquences seulement sur une portion de

leur longueur. » http://www.infobiogen.fr– Deux sous-chaînes sont alignées.

ExempleGCAACATAG|||||||||GCAACATAG

TACATGCG||:|||||TAGATGCG

TGTGC-TTG||||| |||TGTGCCTTG

S1 : TGTGCTTGGCAACATAGATAGATGCG

S2 : TACATGCGCAACATAGCTGTGCCTTG







Qualité d’un alignementQualité d’un alignement

Méthodes d’évaluation– Pourcentage d’identité

• distance d’édition • longueur du fragment

– Score d’un alignement• Fixer un score pour chacune des opérations unitaires lors de la

construction d’un alignement – correspondance/substitution de deux nucléotides– insertion/suppression de deux nucléotides

• Pour un alignement donné, la somme des scores des opérations unitaires associées donne le score de l’alignement

ExempleExemple

Alignement fixé

Fonction de score– Matrice de score

• s(a,b)

– Coût pour l’insertion/la suppression de nucléotides (indels)• g = « s(a,-) »• g = -3

– Score de l’alignement 1*(8 matches) –1 * (1 transition) – 2 * (1 transversion ) – 3 * (1 indel)= 2

ATGTGC-TTGC|||:|| |.||ATGAGCCTCGC

A T G C

A 1 -2 -1 -2

T -2 1 -2 -1

G -1 -2 1 -2

C -2 -1 -2 1

Méthode d’évaluationMéthode d’évaluation

Meilleur Alignement Local– Celui qui maximise le score.

TATGTGCTTGCATGAGCTTCGC

ATGTGCTT|||:||||ATGAGCTT

ATGTGCTT-GC|||:|||| ||ATGAGCTTCGC

ATG-TGCTT-GC||| |||| ||ATGA-GCTTCGC

5 4 0

Méthode d’évaluationMéthode d’évaluation

Gaps– En général coût d’un gap évalué en deux phases

Ouverture/Extension– Exemple : coût d’ouverture -3, coût d’extension -1.

Choix des matrices de scores– PAM/BLOSUM : Log odd ratio.– Théorie développée par Karlin.

• Calcul de l’E-value P-value dans le cadre asymptotique.• Évaluation de la significativité de l’alignement dans le cadre

asymptotique

ATGTGC--CGCAT|||:|| |||||ATGAGCTTCGCAT

CTGTG---CGCAT|||:| |||||CTGAGCTTCGCAT

Recherche des alignements locauxRecherche des alignements locaux

Programmation dynamique – Extension de la méthode de Needleman Wunsch (alignement

global)

Alignement global– Needleman Wunsch (70)

– S(i,j) : score de l’alignement maximal entre S1(0 , i ) et S2(0 , j ) (préfixe de taille i de S1 et préfixe de taille j de S2 )

S(i, j) = maxS(i-1, j-1) + s(S1[i], S2[j] )S(i-1, j) + gS(i, j-1) + g s(a,b) = coût d’une substitution

entre les lettres a et b g = coût d’un gap

Recherche des alignements locauxRecherche des alignements locaux

Alignement local– Recherche des alignements locaux maximaux de score positif.

Algorithme de Smith-Waterman– S(i,j) : score de l’alignement local entre S1(?, i ) et S2(?, j )

Alignement local terminant aux positions i,j.

S(i, j) = max

S(i-1, j-1) + s(S1[i], S2[j] )S(i-1, j) + gS(i, j-1) + g0

s(a,b) = coût d’une substitution entre les lettres a et b g = coût d’un gap

Coût de la méthode exacteCoût de la méthode exacte

Algorithme quadratique.– Adopté sur des séquences relativement courtes (< 100000 b)

Optimisations– Crochemore 2002.

Autre démarche sur séquences chromosomiques– L’algorithme de recherche exhaustive n’est plus applicable en

temps raisonnable.– Utiliser une méthode heuristique– S’inspirer de méthodes déjà existantes dans le domaine du pattern

matching.

)( log

2

nnhO

Filtrage du texteFiltrage du texte

Deux types de Filtrage – Sans perte

Éliminer les régions qui n’ont aucune chance d’être similaires selon un critère donné.

– Avec perteÉliminer les régions qui ont peu de chances d’être similaires selon un

critère donné.

Filtrage – Principe couramment adopté par de nombreuses méthodes de

Pattern-Matching approché.– En général basé sur la connaissance de sous-parties conservées.

Bien que le filtrage avec perte soit notre propos, je donnerai par la suite des exemples de filtrage sans perte (plus facile à appréhender)

Un problème résolu par Filtrage sans PerteUn problème résolu par Filtrage sans Perte

Recherche d’occurrences de fragments de texte de taille fixée m en autorisant au plus k erreurs de substitution.

Applications : oligos spécifiques (uniques à k erreurs)

...GCTACGACTTCGAGCTGC... ||||:|||.||||||:||...GCTATGACCTCGAGCGGC...

m k

Techniques traditionnellesTechniques traditionnelles

PEX[4] – Recherche du plus long fragment conservé.

PEX (avec erreurs)– Recherche du plus long fragment k’-conservé.

• parcours des mots k’-dérivés dans l’index. Efficace si– petites tailles d’alphabets (ADN,ARN)– nombre k’ relativement faible ( <= 2)

m

k

11

km

conservé'1

####

#########(1)

(m,k)

Techniques avancéesTechniques avancées

Technique utilisant une combinaison de deux filtres.Pevzner Waterman[4]

Idée: combiner le filtre PEX avec un filtre utilisant un élément espacé régulier (~PEX espacé).

– PEX :

– PEX espacé : utiliser une élément régulier ayant des espacements de taille k.

####

#...#...#...#

#...#...#...# #...#...#...# #...#...#...# #...#...#...#

#...#...#...# #...#...#...# #...#...#...# #...#...#...#

k+1

Comparaison des différentes TechniquesComparaison des différentes Techniques

Les techniques ont la même sensibilité (=1 car filtrage sans perte)

Sélectivité– VP/(FP+VP)– Si les longueurs des deux séquences sont n et m, le nombre

attendu de Faux Positifs sur des séquences i.i.d est de ~ n.m.δ.• PEX : δ ~ 1/|Σ|w, PEX avec erreurs : δ ~ sum[r:0..a] Cr

w1/|Σ|w-r (1-1/|Σ|)r

Vrai Positifs

Faux Négatifs

FauxPositifs

VraiNégatifs

Filtrage avec perte dans le cas de Filtrage avec perte dans le cas de l’alignementl’alignement

Méthode de filtrage la plus utilisée dans le cadre de l’alignement local.

Deux paramètres à considérer– Sélectivité : δ– Sensibilité : VP/(VP+FN)

Vrai Positifs

Faux Négatifs

FauxPositifs

Vrai Négatifs

GrainesGraines

Analogie avec élément conservé dans le cas du filtrage sans perte.

Une graine = un fragment répété de manière exacte dans un alignement intéressant.– Modéliser ce qu’est un alignement dit intéressant

• son score >= valeur fixée.• Autres modèles d’alignement (%identité + longueur fixée)

– Évaluer la Sensibilité : probabilité de trouver au moins une occurrence de cette graine sur les alignements.

Méthode employée par BLASTMéthode employée par BLAST

Cas de BLASTn:– Recherche basée sur des graines contiguës de taille (poids) 11: si l’alignement contient une fragment de texte conservé de taille

11 alors il est détecté (Hit) et transmit à un algorithme d’alignement.

Cas de Gapped-BLAST:– Plutôt que rechercher un seul fragment (poids 11), critère basé

sur la présence dans l’alignement de deux fragments de texte de poids plus faible ( 9 ) séparé par une distance d < seuil.

########### ########### ###########

##################d

Sensibilité des deux approchesSensibilité des deux approches

Méthode de comparaison proposée– Alignement sans gaps (pas d’indels dans l’alignement)– Utiliser un système de score courant (celui de BLAST par exemple)– Fixer une valeur pour le score des séquences générées (lié à sa

significativité)– Faire varier la longueur de l’alignement.

Probabilité d’un hit – On considère la probabilité de trouver de telles répétitions selon

• le critère de hit de BLAST• le critère de hit de Gapped-BLAST

Sensibilité Sensibilité

Comparaison avec les approches choisies par BLASTn et Gapped-BLAST (score 25)


Comparaison avec les approches choisies par BLASTn et Gapped-BLAST (score 35)

Méthode employée par BLATMéthode employée par BLAT[5][5]

Notion de graine avec erreur– Autoriser dans une graine contiguë pouvant éventuellement

contenir une erreur.– Utiliser des graines de poids plus élevé pour conserver un niveau

de sélectivité suffisant: δ ~ sum[r=0..1] Crw1/|Σ|w-r (1-1/|Σ|)r

– Coût supplémentaire à l’exécution : • index multiple (coût mémoire x poids)• index simple (il est nécessaire de parcourir tous les mots dérivés)

##############(1)

Graines espacéesGraines espacées

Idée proposée par PatternHunter [1] dans le cadre de la recherche heuristique d’alignements

« Redécouverte » d’un principe employé par le logiciel nommé FLASH

Une graine espacée – mot défini sur un alphabet à deux lettres {‘#’,’_’}. – Les éléments ‘_’ sont des caractères jokers.

– Les graines contiguës (type BLAST) sont un cas particulier de graines espacées.

###_#_#__#_###

###_#__#_#__##_###

###_#__#_#__##_###


Poids/Étendue– Poids : nombre d’éléments ‘#’– Etendue : taille de la graine (nombre total d’éléments ‘#’,’_’ )

Modèle pour mesurer l’efficacité des graines– Modèle de Bernoulli générant des alignements sans gaps de taille

fixée (64 avec p=0.70).

Recherche de la meilleure graine espacée.– Parcours de l’espace des graines pour un poids fixé– Calcul de la probabilité d’apparition d’un graine donnée à l’aide

d’un algorithme de programmation dynamique.


Quelques observations d’ordre probabiliste:

Pour des graines espacées, leur apparition sur la séquence à deux positions successives sont des évènements plus indépendants.

Des graines espacées ayant un motif non-régulier (“aléatoire”) sont en général meilleures.

Pour des graines contiguës et espacées du même poids, l’espérance du nombre d’occurrences est approximativement la même. Les probabilités d’obtenir au moins une occurrence sont très différentes.


Comparaison avec les approches choisies par BLASTn et PatternHunter


Comparaison avec les approches choisies par BLASTn et PatternHunter

Graines Espacées autorisant des transitions Graines Espacées autorisant des transitions

Modèle « biologique » Substitutions possibles

– Les transitions sont toujours sur-représentées.

– Phénomènes de régularités dans les séquences codantes

Une graine espacée autorisant des transitions– mot défini sur un alphabet à 3 lettres {‘@’,‘#’,’_’}.– Poids d’un graine = ’#’ +’@’ / 2;

Exemples de graines optimales trouvées – modèle de Markov d’ordre 2 pour générer les alignements.

A T

G Ctransitions

transversions

#@#@@#@__#@@#_@#@####_###_#__####

(0.744003)(0.701099)

|44690 |44680 |44670 |44660 |44650 |44640 |44630 GAAACATCGAAAGTACCACCACCCAAATCGAAAATCAAAACATGTCTTTCCTTTTCGGACTTACCAGCACCTAGACCGT||:|||||.|||||.|||||:|.||..||.||.||:||:||||:||||||::.|.|..:|||:. ...|||..||||GACACATCAAAAGTGCCACCTCTCAGGTCAAAGATAAACACATTTCTTTCAGCTCCAACCTTTT---TGTCTAAGCCGT |443050 |443060 |443070 |443080 |443090 |443100 |443110

|44610 |44600 |44590 |44580 |44570 |44560 |44550 AAGCAATAGCAGCGGCAGTAGGTTCGTTGATGATACGCAAAACGTTCAAACCAGAAATGGCACCGGCATCCTTGGTAGC||||||||:||||.|||:|:||.||.|||||.||:|::|.:||.||:|.|||||:|||.|.:||.|||||.||||||||AAGCAATATCAGCAGCACTTGGCTCATTGATAATTCTAAGTACATTGAGACCAGCAATAGTTCCAGCATCTTTGGTAGC|443120 |443130 |443140 |443150 |443160 |443170 |443180 |443190

|44540 |44530 |44520 |44510 |44500 |44490 |44480 |44470 TTGTCTTTGAGCGTCGTTAAAGTAAGCTGGGACAGTAATGACGGCCTTTTCAACCTTCTTACCAATCTTAGCTTCAGCA.||:.:.||||:||..||||||||||||||:||:||.|.:||.||:||::.|||::||||:||||::|:.|||||:|||CTGATGCTGAGAGTTATTAAAGTAAGCTGGCACTGTGACCACAGCATTGGTAACAGTCTTCCCAAGGTAGGCTTCTGCA |443200 |443210 |443220 |443230 |443240 |443250 |443260 |443270

|44460 |44450 |44440 |44430 |44420 |44410 |44400 ATTTCCTTCATCTTGGTCAAAACCATAGCGGAAATTTCTTGTGGGGAGAAAGTCTTGGTTTCTTCCAAGTA||||||||||||||:||||..|||||||:|||:|..||.|:|||.:||||..|.|||||.|||.||::|||ATTTCCTTCATCTTTGTCAGGACCATAGAGGACACCTCCTCTGGATAGAAGATTTTGGTCTCTCCCTTGTA |443280 |443290 |443300 |443310 |443320 |443330 |443340

Méthodes d’évaluation de la sensibilité Méthodes d’évaluation de la sensibilité

Quel motif donner à une graine espacée ?– Modèle d’alignement

• Alignements de taille 64 • Alignements sans indels• Alignements ayant environ 70% de similarité• Générés par un modèle de Bernoulli/Markov.

– Évaluer la sensibilité des différentes graines possibles sur ces alignements: probabilité d’apparition d’une graine d’un motif donné sur les séquences générées par ce modèle

Waiting Time– Cas pour lequel le calcul est simple

Deux méthodes proposées– Algorithme de programmation dynamique (Keich).– Automate (Bulher).

###_#__#_#__##_###

Problème relatif au Problème relatif au Waiting TimeWaiting Time

Données :– Une graine espacée (son motif)

Résultat :– Probabilité d’obtenir pour la première fois ce motif à la position i sur la

séquence générée.

Sum of Waiting Time– Sommation dans la fenêtre [1-n].

Cas particulier : – graines contiguës de poids k sur modèle de Bernouilli

Graines espacées– Sum of Waiting Time : Problème plus difficile.

kxippkxp

kxx

kx

i pk

k

k

pk

GPGP

pour 1 1 pour

0pour 0

1

0 ,

,

Algorithme proposé par KeichAlgorithme proposé par Keich

Données :– Une graine espacée (son motif)– Modèle d’alignements (modèle de Bernoulli).

• p = 0.70%• L = 64.

Résultat : probabilité d’apparition de cette graine dans le modèle d’alignement.

Schéma de calcul récursif.– Utiliser le mot w suffixe pour réaliser le calcul

###_#_#__#_###

wi

111011101111


P (w,i) = probabilité que l’alignement de longueur i + |w| soit détecté par la graine espacée.

(1) Cas triviaux P (w,i) = 0 si |w| + i < Étendue(graine)

P (w,i) = 1 si |w| = Étendue(graine) et graine détecte w

wi

111011101111


(2) Cas définis de manière récursive

P (w,i) = P(v,i) si la graine ne détecte pas le suffixe w de l’alignement à la dernière position.

Le mot 1Étendue(graine)-|w|.w n’est pas détecté par la graine espacée.

wi

111011101111

w

v

###_#_#__#_###

(2) Cas définis de manière récursive

P (w,i) = p. P (1.w,i-1) + q. P (0.w,i-1) (si |w| < Étendue(graine))

Le mot w est étendu à gauche, selon le modèle de Bernoulli.


wi

11101110111110

finalement :

P (w,i) = 0 si |w| + i < Étendue(graine) P (w,i) = 1 si |w| = Étendue(graine) et la graine détecte w P (w,i) = P(v,i) si la graine ne détecte pas le suffixe w de l’alignement. P (w,i) = p. P (1.w,i-1) + q. P (0.w,i-1) (si |w| < Étendue(graine))

Calcul réalisé par programmation dynamique :Ne calculer que les valeurs P (w,i) > 0…

Ne s’intéresser, dans l’arborescence des calculs, qu’aux feuilles contenant des mots w produisant un « match » éventuel avec la graine (2nombre de jokers)

Ce que l’on souhaite calculer : P (^,64)


wi

111011101111

Algorithme proposé par BuhlerAlgorithme proposé par Buhler[2][2]

Exemple :

– Reconnaître les mots détectés par la graine (automate)

#_#_#

1

0

1

1

1

0

1

1

0

1

1

1

1

11111101011011111101

Algorithme proposé par BuhlerAlgorithme proposé par Buhler

Exemple :

– Ne pas oublier les liens préfixes

0

0

0

0

0

0

0

#_#_#

1

0

1

1

1

0

1

1

0

1

1

1

1

11111101011011111101


Exemple :

– On obtient un automate qui trouve la première occurrence de la graine sur l’alignement.

0

0

0

0

0

0

0

1

0

1

1

1

0

1

1

0

1

1

1

1

#_#_#


Exemple :– Probabilité d’arriver à l’état E lors de la lecture du iéme caractère de l’alignement:

– Dépends de la probabilité d’être à l’état D1,D2,ou D3 lors de l’étape i-1.

• Cas Bernoulli …

0

0

0

0

0

0

0

1

0

1

1

1

0

1

1

0

1

1

1

1

#_#_#

E

D1

D2

D3


Exemple :– Au bout de n itérations, calculer la probabilité d’être à l’état final.

– Initialisation : A l’étape 0 : P( I ) = 1 , P( . ) = 0

– Complexité : O( l . w 2s-w . 2k) avec

l : taille de l’alignement , s-w : nombre de jokers, k : ordre de la Chaîne de Markov.

0

0

0

0

0

0

0

1

0

1

1

1

0

1

1

0

1

1

1

1

#_#_#

I F

Comment modéliser un alignement sans Comment modéliser un alignement sans gapsgaps

Une autre approche: Précédents graphiques: seuls les alignements de score fixé ont été utilisés. Remarque: certains de ces alignements contenaient cependant un sous alignement

de score supérieur

Se restreindre aux alignements homogènes (MSP): ceux dont le score est supérieur que le score de chacun de ses propres segments

On suppose que tous les alignement homogènes (d’une longueur donné) sont équiprobables.

Obtenir une mesure fiable des MSP détectées par les logiciels de type BLAST.

Alignements homogènesAlignements homogènes

S

Alignements homogènes de longueur n et score S marche de (0,0) jusqu’à (n,S) dans le rectangle vert.

Modèle de Markov vs. Alignement Modèle de Markov vs. Alignement HomogèneHomogène

Les modèles de Markov spécifient des propriétés locales et la composition probable de l’alignement.

Les alignements homogènes spécifient le score total et les propriétés globales de l’alignement (homogénéité).

Les deux approches sont complémentaires.

Génération uniforme d’alignements Génération uniforme d’alignements homogèneshomogènes

Approche proposée: compter le nombre de suffixes B.

Génération uniforme d’alignements homogènes de longueur n et score non-fixé S.

Pour un score fixé S, la génération est en O(n).

S

Calculer la probabilité d’un Calculer la probabilité d’un hithit

Problème: Étant donné une graine , calculer la probabilité que la graine détecte (hit) un alignement homogène de longueur n et de score S.

Exemple: graine: =111010010100110111 ~ ###_#__#_#__##_###,

alignements: n=100, S=20 (s=1,p=3)

P(i,M,y) : probabilité que la graine détecte le préfixe BM d’un alignement homogène aléatoire, avec |B|=i et Score(B)=y.

Conditions de bord:(i) P(i,M,y)=0, si i+|M|<||,(ii) P(i,M,y)=1, si |M|=|| et détecte M,

Conditions limites:(iii) P(i,M,y)=0, si yS et i<n, ou y0 et n>0,

P(i,M,y) : probabilité que la graine détecte le préfixe BM d’un alignements homogène aléatoire, avec |B|=i et Score(B)=y.

Conditions principales:(iv) P(i,Mb,y)=P(i,M,y), si ne détecte pas une séquence de suffixe

Mb,(v) si |M|< ||, alors P(i,M,y)=P1P(i-1,1M,y-s)+ P0P(i-1,1M,y+p),

avec P1 et P0 obtenus selon des formules de comptage.

L’algorithme de base calcule la probabilité en temps et espace O(2||Sn), ce qui peut être amélioré en O(||2||-w()(||2+Sn)), où w() est le poids de la graine

L’algorithme peut être étendu à certaines stratégies multi-graines.

ExpériencesExpériences

score 16: séquences homogènes

Graines contiguës (poids 11) Graines espacées (poids 11) 111010010100110111

ExperiencesExperiences

Graines contiguës (poids 11) Graines espacées (poids 11) 111010010100110111

score 32: séquences homogènes

Graines optimalesGraines optimales

ConclusionConclusion

Alignement local : algorithme exhaustif et ses limitations.

Présentation des techniques de filtrage pour l’alignement local heuristique.– Graines et modèles dérivés– Graines espacées et modèles dérivés– (YASS) http://www.loria.fr/~noe ou http://yass.loria.fr

Méthodes et algorithmes pour évaluer la sensibilité des graines espacées sur différents modèles d’alignements.

D’autres méthodes de filtrage à la fois aussi sélectives et plus sensibles ?

RéférencesRéférences

[1] M. Bin, J. Tromp John and L. Ming, PatternHunter: Faster and more sensitive homology search, Bioinformatics 18:3 440-445 2002

[2] J. Buhler, U. Keich and Y. Sun, Designing seeds for Similarity Search in Genomic DNA, RECOMB 2003 67-75

[3] K.Choi L.Zhang, Sensitivity Analysis and Efficient Method for Identifying Optimal Spaced Seeds

[4] P. Pevzner and M.Waterman, Multiple Filtration and Approximate Pattern Matching, Algorithmica 13(1/2), 135-154 1995

[5] S. Altschul, and all, Gapped BLAST and PSI-BLAST: a new generation of protein database search programs, Nucleic Acids Research, 27:17 3389-3402 1997

[6] J.Kent, BLAT--The BLAST-Like Alignment Tool, Genome Research 12, 656-664 2002

[7] G. Navarro and M. Raffinot, Flexible Pattern Matching in Strings -- Practical on-line search algorithms for texts, Cambridge University Press 2002

agctga

g?cc??

tatgag

caa?ga

cca??a

ctc?gc

ggcgca

tctagg

ag??ac

c???tc

ttcttc

g

???? ??

QuestionsQuestions

Documents

Filtrage à laide de graines pour lalignement local Laurent Noé [email protected] noe Université Henri Poincaré Travail commun avec