View
103
Download
0
Category
Preview:
Citation preview
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
Recommended