Techniques de filtrage à laide de graines espacées Laurent Noé [email protected] noe Travail commun avec Gregory Kucherov Séminaire

Techniques de filtrage à l’aide de Techniques de filtrage à l’aide de graines espacéesgraines espacées

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

Travail commun avec Gregory Kucherov

Séminaire Symbiose – 4 mars 2004

2

PlanPlan

Introduction Deux problèmes

– Problème de l’alignement local (AL)– Problème de pattern matching approché (PMA)

Résolution utilisant des techniques de filtrage– Définition d’un filtre– Filtrage sans perte dans le cadre du pattern matching approché (PMA)– Filtrage avec perte dans le cadre de l’alignement local (AL)

Design de graines– pour l’alignement local (AL)– pour le problème de pattern matching approché (PMA)

Conclusion

– Deux problèmes sont considérés (AL et PMA)– Des techniques de filtrage (quelquefois semblables) sont proposées pour les résoudre

N’hésitez surtout pas à m’interrompre si vous avez des questions ou des remarques !!

3

IntroductionIntroduction

Motivations : – De nombreuses méthodes en BioInformatique reposent sur les

résultats issus de comparaisons ( de séquences/structures/… ) entre différentes entités ( gènes/chromosomes/espèces/…)

– Le coût des algorithmes utilisés est en général quadratique. Cependant, des gains significatifs peuvent être réalisés à l’aide de techniques dites de filtrage qui permettent d’éviter de considérer tout l’espace de recherche.

Problèmes posés:– Problème d’alignement local (AL).– Problème de Pattern Matching Approché (PMA) relatif à la

sélection d’oligonucléotides

4

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

T1 : TGTGCTTGGCAACATAGATAGATGCG

T2 : TACATGCGCAACATAGCTGTGCCTTG







(AL)

5

Qualité d’un alignementQualité d’un alignement

Objectif :essayer de distinguer les alignements dits significatifs du bruit de

fond (redondance naturelle de la séquence).

Evaluation basée sur une technique dite de score.– Chacune des opérations unitaires lors de la construction d’un

alignement possède un coût.• correspondance/substitution d’une nucléotide dans un alignement.• insertion/suppression de nucléotides

– Pour un alignement donné, la somme des coûts des opérations unitaires associées donne le score de l’alignement

La qualité d’un alignement sera jugée selon le score de l’alignement

TGTGC-TTG||.|| |||TGCGCCTTG

(AL)

6

ExempleExemple

Alignement donné :

Fonction de score– Matrice de substitution

• s(a,b)

– Coût pour l’insertion/la suppression de nucléotides (indels)• 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

(AL)

7

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

Meilleur Alignement Local– Celui qui maximise le score.

GATATGTGCTTGCTTCAATGAGCTTCGCCC

ATGTGCTT|||:||||ATGAGCTT

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

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

5 4 0

GATATGTGCTTGCTTCAATGAGCTTCGCCCGATATGTGCTTGCTTCAATGAGCTTCGCCC

(AL)

8

Recherche des alignements locauxRecherche des alignements locaux

Algorithme de Smith-Waterman– Etant données deux séquences T1 et T2, l’algorithme recherche le

score S(i, j) du meilleur alignement local se terminant

• à la position i sur la séquence T1

• à la position j sur la séquence T2

S(i, j) = max

S(i-1, j-1) + s(T1[i], T2[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

(AL)

9

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.– Adopter une technique heuristique basée sur un filtrage avec

perte.

)( log

2

nnhO

(AL)

10

Pattern Matching ApprochéPattern Matching Approché

Problème posé

Étant donnés

– un motif P de longueur m (ex P = “GCTACGACTTCGAGCTGC”, m=18 )– un nombre maximal d’erreurs k (ex k = 3 )trouver dans un texte T les positions i des occurrences approchées de P :

DHamming( P, T [i..i+m-1] ) ≤ k

Notation

GCTACGACTTCGAGCTGC ||||x|||x||||||x||...CTCAGCTATGACCTCGAGCGGCCTATCTA...

P :

T :

mk(m,k)

(PMA)

11

Liens entre les deux problèmesLiens entre les deux problèmes

Le problème de Pattern Matching Approché ~ une restriction du problème d’alignement local:

– alignements recherchés sont de taille fixée m et ne possèdent pas d’indels.

– alignements recherchés possèdent au plus k erreurs de type substitution.

Les deux problèmes peuvent être résolus à l’aide de techniques de filtrage.

(PMA<->AL)

12

PlanPlan



Résolution utilisant des techniques de filtrage– Définition d’un filtre– Filtrage sans perte dans le cadre du pattern matching approché

(PMA)– Filtrage avec perte pour l’alignement local (AL)


Conclusion

13

FiltrageFiltrage

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 – En général basé sur la connaissance de sous parties conservées. Ces sous

parties conservées seront appelées graines.

On propose d’étudier par la suite deux méthodes de filtrage:– Filtrage sans perte pour PMA– Filtrage avec perte pour AL

14

Filtrage sans perteFiltrage sans perte

PEX[4] – Recherche du plus long fragment conservé (graine contiguë).

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

• 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)

(PMA)

15

Filtrage sans perte Filtrage sans perte

Graines espacées (Q-grams espacés)Technique étudiée par Burkhardt & Kärkkäinen[3] .

PrincipePlutôt que rechercher des fragments contigus dans le texte, baser sa recherche sur des fragments dits espacés (graines espacées).

– La graine est composée à la fois• De caractères match « # » • De caractères jokers « - »

– Distinction entre le poids et la taille (étendue)• Poids : nombre de caractères de type « # ».• Etendue : nombre total de caractères.

– La graine est conçue (design) pour résoudre un problème (m,k) donné.

###-##

(PMA)

16

ExempleExemple

Sur le problème (m=18,k=3)

###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

17

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

18

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

19

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

20

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

21

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

22

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

23

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

24

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

25

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

26

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

27

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

28

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

29

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

30

ExempleExemple


###-##

###-##

###-##

###-## ###-## ###-##

(PMA)

31

Filtrage avec PerteFiltrage avec Perte

Techniques semblables à celles du filtrage sans perte.

– Basées sur la recherche de sous éléments conservés d’un alignement (graines) : ces graines doivent avoir une forte probabilité d’apparition dans les alignements recherchés

Dans le cadre de l’alignement local, ces graines servent à la fois d’indicateurs sur la présence potentielle d’un alignement, et de points d’ancrages pour réaliser une extension de l’alignement.

(AL)

T1 :

T2 :

32

Critère de Hit de Critère de Hit de BLASTBLAST[5][5]

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.

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

(AL)

33

Critère de Hit de Critère de Hit de BLATBLAT[6][6]

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.– Coût supplémentaire à l’exécution :

• index multiple (coût mémoire)• index simple (il est nécessaire de parcourir tous les mots dérivés)

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

(AL)

34

Critère de Hit de Critère de Hit de PatternHunterPatternHunter[1][1]

Notion de graine espacée

Apport de PatternHunter : proposer un design de ces graines (choix du motif)

###-#--#-#--##-###

###-#--#-#--##-###

###-#--#-#--##-###

(AL)

###-#-#--#-###

35

Filtrage : analyseFiltrage : analyse

Quantités considérées

Mesures effectuées– Sélectivité : VP/(FP+VP)– Sensibilité : VP/(FN+VP)

Vrais Positifs

Faux Négatifs

Faux Positifs

Vrais Négatifs

Détectés / Non détectés par le filtre

Vérifient /

Ne vérifient pas le critère

de similarité

36

Filtrage sans perte dans le cadre du PMAFiltrage sans perte dans le cadre du PMA

Quantités considérées

Filtrage sans perte: le nombre de faux négatifs est nul donc la sensibilité VP/(FN+VP) est = 1.

Maximiser la sélectivité VP/(FP+VP) soit minimiser le nombre de faux positifs.

Estimation de cette quantité:Si la longueur du texte est n, le nombre attendu de faux positifs est ~ n.m.δ (sur des séquences i.i.d).

PEX : δ = 1/|A|4, Graines espacées : δ = 1/|A|5

(PMA)

####

###-##

Vrais Positifs

Faux Négatifs

Faux Positifs

Vrais Négatifs


Vérifient /


de similarité

37

Filtrage avec perte dans le cadre de l’ALFiltrage avec perte dans le cadre de l’AL

Filtrage avec perte

– Mesure de la sélectivité : VP/(FP+VP) reste basée sur l’estimation de δ donc liée au poids des graines.

– Mesure de la sensibilité : VP/(FN+VP)Nécessité de définir le critère d’un alignement étalon.

ces deux quantités sont antagonistes.

Vrais Positifs

Faux Négatifs

Faux Positifs

Vrais Négatifs


Vérifient /


d’un alignement étalon

(AL)

38

Sensibilité des différentes approchesSensibilité des différentes approches

Modèle choisi : Alignements étalons

– Alignements sans gaps (pas d’indels dans l’alignement)

– Utiliser un système de score courant (celui de BLAST)+1/-3 (match/mismatch)

Paramètres proposés– Fixer une valeur pour le score des séquences générées – Faire varier la longueur de l’alignement (abscisse).

Mesure : Probabilité d’un hit

– A sélectivité égale, on considère la sensibilité : probabilité de trouver de tels alignements selon

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

(AL)

39

Sensibilité Sensibilité

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

(AL)

40


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

(AL)

41


Comparaison avec les approches choisies par BLASTn et PatternHunter (score 25)

(AL)

42


Comparaison avec les approches choisies par BLASTn et PatternHunter (score 25)

(AL)

43

Critère de Hit de Critère de Hit de YASSYASS

modèle inspiré des alignements biologiques– Les transitions sont toujours sur-représentées.

graine espacée autorisant des transitions– mot défini sur un alphabet à 3 lettres {‘@’,‘#’, ‘-’}.– symbole ‘@’ signifie “soit match soit transition”– poids d’un graine = ’#’ +’@’ / 2;

exemples de graines optimales trouvées – Alignements générés selon un modèle de Bernoulli.

– Alignements générés selon un modèle de Markov d’ordre 5

A T

G Ctransitions

transversions

(AL)

##@-#@#--#-###

##@##-##@##

44

SensibilitéSensibilité

Sur des alignements générés selon un modèle de Bernoulli. la sensibilité dépend du ratio entre le nombre de transitions et transversions.

(AL)

45

SensibilitéSensibilité

Sur des alignements générés selon un modèle de Markov (ordre 5).

(AL)

46

Critère de Hit de YASSCritère de Hit de YASS

Critère de Hit à la fois multi-seed (Gapped Blast) avec des propriétés issues de techniques single-seed (BLAST).

principes:

– regrouper efficacement les graines en sous-ensembles représentatifs d’alignements potentiels

un modèle statistique de la séquence pour simuler les effets des mutations et des indels sur la répartition des graines dans l’alignement.

– évaluer un critère global distribué sur l’alignement • Mesure du nombre de matches apportées par les graines• Hit si dépassement d’un seuil.

(AL)

47


(AL)

48


(AL)

49

PlanPlan



Résolution utilisant des techniques de filtrage– Définition d’un filtre– Filtrage sans perte dans le cadre du pattern matching approché

(PMA)– Filtrage avec perte pour l’alignement local (AL)


Conclusion

50

Design de graines espacéesDesign de graines espacées

Les techniques de filtrage par graines espacées necessitent une conception (design) de la graine:– dans le cadre du filtrage avec perte (AL)

– dans le cadre du filtrage sans perte (PMA)

Sur quels critères peut-on établir le choix de la graine ?

###-#-#--#-###

###-#--###-#--###-#

51

Design dans le cadre du filtrage avec perteDesign dans le cadre du filtrage avec perte

Méthode– On choisit un Modèle d’alignement

• Alignements de taille 64 • Alignements sans indels• Alignements générés selon un modèle de Bernoulli/Markov.

– Évaluer la sensibilité des graines de poids fixé w sur ce modèle.

Mesure de la sensibilité– Algorithme de programmation dynamique (Keich & all).– Automate (Bulher & all).– Alignements Homogènes (Kucherov & all).

###-#--#-#--##-###

(AL)

52

Algorithme proposé par Keich & allAlgorithme proposé par Keich & all

Données :– Une graine espacée – Modèle générant des alignements.

• alignements de longueur fixée• modèle de Bernoulli pour générer ces alignements

Résultat : – probabilité d’apparition de cette graine dans un alignement

généré selon le modèle.

Algorithme de programmation dynamique :– utiliser un mot suffixe pour réaliser le calcul

###-#-#--#-###

(AL)

53

Algorithme proposé par Buhler & allAlgorithme proposé par Buhler & all

Données :– Une graine espacée – Modèle générant des alignements.

• alignements de longueur fixée• modèle de Bernoulli/Markov pour générer ces alignements

Résultat : – probabilité d’apparition de cette graine dans un alignement

généré selon le modèle.

Algorithme basé sur un automate.– mots reconnus par la graine : langage régulier fini. (automate)

– Travaux de Nicodème & all [4].

(AL)

###-#-#--#-###

54

Algorithme proposé par Kucherov & allAlgorithme proposé par Kucherov & all

Idée: – les alignements de score maximum sont ceux qui sont recherchés

par les algorithmes d’alignements (Smith-Waterman).– ne s’intéresser qu’à ce type d’alignements, et non à des

alignements purement aléatoires.

Méthode:– compter le nombre d’alignements de score maximum.– calculer (programmation dynamique) la probabilité d’apparition

d’une graine donnée sur les alignements de score maximum.

(AL)

55

RésultatsRésultats

Filtrage avec perte pour l’alignement local– Des graines efficaces sur le modèle d’alignement proposé

– Des graines dont le motif est irrégulier

Qu’en est-il du filtrage sans perte pour le problème de Pattern Matching Approché ?

###-#--#-#--##-###

###-#-#--#-###

(AL-> PMA)

##@#-#@--##-#-@@##

##@-#@#--#-###

56

Filtrage sans perte pour PMAFiltrage sans perte pour PMA

Les graines obtenues dans ce cadre sont régulières

Exemples

• Problème (m=25,k=2) : une seule graine de poids optimal 12

• Problème (m=18,k=2) : une graine de poids optimal 8

Pourquoi une telle régularité ?

###-#--###-#--###-#

###-#--###-#

(PMA)

57

ExplicationsExplications

Le motif “répété” résout un problème “circulaire”

Problème Circulaire (m=11,k=3)

Problème Linéaire (m’=30,k=3)

###-#--#---

###-#--#---###-#--#

(PMA)

58

Famille de Graines Utiliser un ensemble de graines de manière disjonctive

Une famille de graines est un ensemble de s graines qui résout toutes les instances d’un problème (m,k) donné.

Les graines d’une famille sont de même poids.

ExtensionsExtensions

##-#-#######---#--##-#

Dans toute instance du problème (m,k), Il existe au moins une occurrence d’une des graines de la famille dans cette instance

(PMA)

59

Exemple

##-##-########-####--#####-##---#-#####----####-######---#-#-##-#####-#-#-#-----###

Famille de graines espacéesFamille de graines espacées

##-#-#######---#--##-#

###-##---#-###

###---#--##-# ###---#--##-#

(PMA)

60

Exemple

##-##-########-####--#####-##---#-#####----####-######---#-#-##-#####-#-#-#-----###


##-#-#######---#--##-#

###---#-#-##-## ##----####-######-#-#-#-----###

##-#-#### ##-#-####

(PMA)

61


La propriété de circularité s’applique également



###-#--#---

###-#--#---###-#--##--#---###-#--#---###

(PMA)

62


La propriété de circularité s’applique également



###-#--#---

###-#--#---###-#--# #--#---###-#--#---###

(PMA)

63

ConclusionConclusion

Deux problèmes– l’alignement local– un problème de pattern matching approché

Résolution par filtrage à l’aide de graines– Graines et modèles dérivés– Graines espacées et modèles dérivés

(YASS) http://www.loria.fr/projects/YASS

Problème du design de graines– Mesure de la sensibilité dans le cadre du Filtrage avec perte (AL)– Design régulier dans le cadre du Filtrage sans perte (PMA)

Vers de meilleures stratégies de filtrage ?

64

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] S. Burkhardt and J. Kärkkäinen, Better Filtering with Gapped q-Grams, Fundamenta Informaticae, 23:1001-1018 2003

[4] P. Nicodeme, B Salvy, P. Flajolet, Motif Statistics, Rapport de Recherche INRIA N° 3606, 1999

[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

65

agctga

g?cc??

tatgag

caa?ga

cca??a

ctc?gc

ggcgca

tctagg

ag??ac

c???tc

ttcttc

g

???? ??

QuestionsQuestions

Documents

Techniques de filtrage à laide de graines espacées Laurent Noé [email protected] noe Travail commun avec Gregory Kucherov Séminaire