1

Recherche de répétitions distantes dans Recherche de répétitions distantes dans les séquencesles séquences

Etudiant : Etudiant : Laurent NOELaurent NOE Encadrant : Encadrant : Gregory KUCHEROVGregory KUCHEROV

2

Plan

1. Introduction au problème

2. Les programmes existants

3. La méthode adoptée

4. L’algorithme

5. Résultats obtenus et extensions envisagées

6. Conclusion

3

1. Introduction

L’ADN• La molécule

• L’information contenue

Extraction de l’information (séquençage) Gènes et fonctions Aspects automatisables

4

Recherche de répétitions• Problème connu de l’algorithmique du texte

• Spécificité de l’ADN : répétitions approchées

• Sous-répétitions exactes (graines)

• Approche choisie

5

Evolution des occurrences d’une répétition

s

1 2 31

23

d

1 345

14

35

i

6

2. Les programmes existants

BLAST

ASSIRC

7

BLAST

Nombreuses versions destinées à l’ADN et aux protéines

Recherche de similitudes significatives dans les bases de données.

Basé sur l’extension de graines de taille 11

8

ASSIRC

Recherche de répétitions exactes de k lettres (couples de k-mots)

Extension des répétitions exactes (graines) à l’aide d’une fonction propre

9

3. La méthode adoptée

Rassembler les graines (répétitions exactes)• Rechercher des répétitions exactes dont chacune des

occurrences est respectivement proche de l’autre

Utilisation de critères statistiques concernant:• La taille des répétitions exactes recherchées

• La distance entre ces répétitions exactes

• La variation de distance entre ces répétitions

10

Modèles choisis

Modèle d’alignement binaire• Comparaison d’occurrences de répétitions approchées

Marche aléatoire• simuler les indels (insertions/suppressions) sur les

occurrences de répétitions approchées

11

Modèle d’alignement binaire

Comparaison de deux répétitions approchées

Analogie avec le lancer de pièce:• un train (série successive) de k piles (valeur 1) équivaut à une

répétition exacte de taille k.

Etude de variables aléatoires issues du lancer de pièce:• le plus long train de piles espéré en n lancers.• la distance entre des trains de k piles.

ATGACCAGTACCGTCCGCTATGTGCAGGACCGTGAGCT

1110011101111100111

12

Modèle d’alignement binaire

Plus long train de piles espéré en n lancers.

• Permet de déterminer la taille maximale espérée des répétitions exactes dans une répétition approchée de taille n.

• Formule approchée:• p = taux de ressemblance,

• n = taille de la répétition approchée,

• α = tolérance

• Simulation

p

np 1 log

1 loglog 1 log

ATGACCAGTACCGTCCGCTATGTGCAGGACCGTGAGCT

1110011101111100111

13

Modèle d’alignement binaire

Distance entre trains de k piles

• Sert à étudier la distance entre les répétitions exactes de taille supérieure ou égale à k dans une répétition approchée.

• Formule récursive:

• Gk,p = « distance » entre les répétitions de taille k,• p = taux de ressemblance

• Bornes Statistiques

kxippkxp

kxx

kx

i pk

k

k

pk

GPGP

pour 1 1 pour

0pour 0

1

0 ,

,

ATGACCAGTACCGTCCGCTATGTGCAGGACCGTGAGCT

1110011101111100111

14

Indels

Indels = insertion / suppression de lettres

d

ATGACCAGTACGGTCCGCTATGTGCAGGACCGTGAGCT

1110011101101100111

1

ATGACCAGTCACGGTCCGCTATGTGCAGG-ACCGTGAGCT

111001110.1101100111

2

d+1

d

15

Marche aléatoire

• Déplacement discret probabiliste dans l’espace. 3 possibilités

• « aller un pas vers la gauche » avec une probabilité p.

• « aller un pas vers la droite » avec une probabilité p.

• « rester sur place» avec une probabilité 1-2p.

On évalue la position finale au bout de n itérations.

• Marche aléatoire simule la variation de d. p représente la probabilité d’indels par nucléotide.

Le nombre de déplacements n est égal à la zone d’influence des indels sur d.

16

Marche aléatoire

• Borner statistiquement la variation de d cela équivaut à borner statistiquement la marche aléatoire.

• 2 Méthodes Calcul d’intervalles [-L..L] sur une loi multinomiale:

Fonction génératrice

)21())! 2 ( ()! ( !

! )2(22)(

0

ppkjnkjj

n kjnkjL

Lk

kn

j

XpppXXP 21

11 XaXaXaXP n

nn

-nn

-nn

17

Méthode adoptée

Finalement …• Rassembler les répétitions exactes qui sont proches:

borne statistique sur la distance entre répétitions de taille k

• Considérer les effets produits par les indels: bornes statistiques sur la variation de distance entre

répétitions de taille k.

ATGACCAGTACGGTCCGCTATGTGCAGGACCGTGAGCT

d1 d2 d’1 d’2

18

4. Algorithme

Algorithme de chaînage

Algorithme d’alignement

Chaînages de répétitions

exactes

Séquence(s) d’ADN

Répétitions approchées

Paramètres utilisateur

19

Algorithme de chaînage

Utilise en entrée la liste chaînée des k-mots• k-mot : sous-mot du texte de taille k

• Cette liste donne l’ensemble des positions sur le texte d’un k-mot donné.

Création de couples de k-mots identiques c( i , j ).

Chaînage de ces couples selon les deux critères de distance vus précédemment.

20

Critères appliqués aux couples

distance di inter-couples inférieure à un seuil

variation de distance inter-couples inférieure à un seuil

lien entre la distance intra-couple ai et la distance inter-couples di.

Reformuler ce critère sur la distance intra-couple ai

ATGACCAGTACGGTCCGCTATGTGCAGGACCGTGAGCT..

d1 d2 d’1 d’2

a1

a2

21

Première approche

1 pour chaque k-mot wi de T ( 0 < i < n - k + 2 ) faire

2 pour chaque occurrence wj de wi ( j < i ) faire

3 si il existe un couple c’(i’, j’) satisfaisant les deux critères

4 alors chaîner c’(i’, j’) vers c(i ,j)

5 fsi

6 fpour

7 fpour

22

Respect des critères

Afin de respecter ces critères, on utilise un tableau des distances :

• Son rôle : conserver à l’indice d, la position i du dernier couple dont la distance intra-couple était d .

• Utilisé pour la recherche de couples antécédents.

• Afin de prendre en compte les indels, les couples antécédents ayant une distance intra-couple voisine seront également pris en compte.

23

Deuxième approche

01 pour chaque k-mot wi de T ( 0 < i < n - k + 2 ) faire

02 pour chaque occurrence wj de wi ( j < i ) faire

03 d = i - j

04 pour dobs dans {d, d+1, d-1, … d+ δ, d- δ} faire

05 i’ = CD [dobs ]

06 si i – i’ < ρ alors

07 j’ = i – dobs

08 chaîner c(i’, j’) vers c(i,j )

09 break // sortir de la boucle dobs

10 fsi

11 fpour

12 CD [d ] = i

13 fpour

14 fpour

24

5. Réalisation

Programme Résultats

• Donne les positions (début-fin) de chaque occurrence d’une répétition.

• Indique le taux de ressemblance ainsi que les tailles des graines qui interviennent dans la répétition.

• Possibilité de visualiser l’alignement des deux occurrences de la répétition approchée.

TTCTTGTCTT-TCATGTACCT-CTTTCAGATACC--ACTGAGTAATATGACTTTA-AAAGCTCT

......d.s.i..sd......i.ss.d....s.sii...ss...s.s..d....si...ssd..

TTCTTG-CATATCC-GTACCTACCGT-AGATTCAATACTCCGTAGTTTG-CTTTCGAAATA-CT

25

Expérimentation

ASSIRC• plus lent

BLASTN• approche moins sensible

Temps de calcul partagé entre chaînage/alignement• Le temps consommé par l’alignement augmente de

manière beaucoup plus importante que celui du chaînage lorsque l’on cherche des répétitions approchées moins ressemblantes.

• Ajout d’un filtre annexe (sous k-mots).

26

Extensions envisagées

Traiter le brin d’ADN complémentaire inversé

tttgac

gtcaaa

(1) duplication

(2) complémentaritéa-tg-c

Brins d'ADNcomplémentaires

27

6. Conclusion

Nouvelle méthode de recherche de répétitions

• propriétés statistiques des séquences approchées

• algorithme de regroupement Solution satisfaisante Extensions envisagées

28agc

tgag?c

c??tat

gagcaa

?gacca

??actc

?gcggc

gcatct

aggag?

?acc??

?tcttc

ttcg

???? ??

Questions