YASS : Recherche de similarités dans YASS : Recherche de similarités dans les séquences d'ADN les séquences d'ADN

Laurent Noé

Grégory Kucherov

Mardi 21 janvier 2003

2

Plan

Alignement local et méthodes heuristiques YASS : Méthode adoptée

• Modèle et Critères de chaînage

• Algorithme de chaînage

• Choix du critère de l’extension

Tests et Résultats

3

Introduction : Alignement local

Utilisation• Annotation

• Localisation de transposons

Algorithme de référence • Smith Waterman (1981)

Méthodes heuristiques• BLAST - FASTA• ASSIRC - PatternHunter

4

Méthodes Heuristiques

Méthode Couramment adoptée• Recherche de sous répétitions exactes

Arbre des suffixes• REPuter

Hachage en k-mots (éventuellement non contigus)• BLAST . FASTA • PatternHunter

• Extension ­ FASTA­ BLAST­ ASSIRC

5

BLAST et Gapped-BLAST

BLAST• Hachage

k-mot : taille 11 par défaut hit : même k-mot sur chacune des deux séquences à

comparer

• Extension Test d'extension systématique de chaque « hit » à l’aide d’un

algorithme de Xdrop Gapped-BLAST

• Extension « double hit » (deux hits distincts sur la même diagonale)

conduit à un test d’extension. Sensibilité des deux méthodes

T

Q

6

Signification Statistique

Karlin-Altschul 90• Théorie sur une seule séquence

• Théorie sur deux séquences

• Alignement sans gaps

Altschul & al. 01• Estimation des paramètres

7

YASS : Méthode adoptée

Alignement local et méthodes heuristiques YASS : Méthode adoptée

• Modèle et Critères de Chaînage

• Algorithme de chaînage

• Choix du critère de l’extension

Tests et Résultats

8

Méthode adoptée

Hachage en k-mots• Hash Table :

Deux tableaux F et L .

k-mots éventuellement non contigus.

• Appariement de k-mots pour former des graines

Groupement de graines• réalisé selon des critères relatifs à:

La distance entre les répétitions exactes

La variation de distance entre ces répétitions

• Critères calculés selon deux modèles ( modèle binaire + modèle d’indels)

des paramètres statistiques

T

Q

9

Choix d’un modèle

Modèle d’alignement binaire

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 • la distance entre des trains de k piles ~ distances entre deux

graines successives.

ATGACCAGTACCGTCCGCTATGTGCAGGACCGTGAGCT

1110011101111100111

10

Modèle d’alignement binaire

Distance entre trains de k piles (WT)

• Utilisée pour évaluer 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 = probabilité d’un match

• Bornes Statistiques

kxippkxp

kxx

kx

i pk

k

k

pk

GPGP

pour 1 1 pour

0pour 0

1

0 ,

,

ATGACCAGTACCGTCCGCTATGTGCAGGACCGTGAGCT

1110011101111100111

11

Modèle d’alignement binaire

Prendre en compte les indels

d

ATGACCAGTACGGTCCGCTATGTGCAGGACCGTGAGCT

1110011101101100111

1

ATGACCAGTCACGGTCCGCTATGTGCAGG-ACCGTGAGCT

111001110.1101100111

2

d+1

d

12

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.

• Borner statistiquement cette marche aléatoire

13

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:

Polynôme générateur

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

! )2(22)(

0

ppkjnkjj

n kjnkjL

Lk

kn

j

XpppXXP 21

11 XaXaXaXP n

nn

-nn

-nn

14

Méthode

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

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

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

entre répétitions de taille k.

ATGACCAGTACGGTCCGCTATGTGCAGGACCGTGAGCT

a1 a2 a’1 a’2

15

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

16

Algorithme de chaînage

Ce qu’il faut en retenir

• Forme des groupes de graines (couples de positions de k-mots identiques) susceptibles d’appartenir à une répétition approchée

• Prend en compte les indels.

• Génère un volume relativement important de données

l’alterner régulièrement avec l’algorithme d’alignement sur les chaînages complets

17

Choix du critère d’extension

Groupes de graines évaluer une extension sur chacun des groupes

• serait la méthode la plus sensible

• serait trop coûteuse en temps.

nombre de graines d’un groupe comme critère• perte de sensibilité trop importante lors de la recherche

similitudes de faible score.

Critère intermédiaire• Basé sur la taille du groupe définie comme la somme

de la taille des graines.

• Permet un compromis entre la rapidité de l’algorithme et sa sensibilité

18

Choix du critère d’extension

Exemple k fixé à 3 ... taille du groupe = 11

Taille du groupe simple à gérer… Sensibilité : on considère par la suite des répétitions de

score fixé mais de longueur variable.

ATGACCAGTACCGTCCGCTATGTGCAGGACCGTGAGCG

1110011101111100110

19

Sensibilité

Pour un score fixé • La relation entre le taux de similarité de la répétition approchée et sa

longueur minimale est une hyperbole.

• 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 notre critère (taille du groupe)

20

Sensibilité Comparaison avec les approches choisies par BLASTn et

Gapped-BLAST

21

Sensibilité Comparaison avec les approches choisies par BLASTn et

Gapped-BLAST

22

Sensibilité Comparaison avec les approches choisies par BLASTn et

Gapped-BLAST

23

Tests et Résultats

Alignement local et méthodes heuristiques YASS : Méthode adoptée

• Modèle et Critères de Chaînage

• Algorithme de chaînage

• Choix du critère de l’extension

Tests et Résultats

24

Comparaison des Méthodes

Temps principalement consommé à :• (FASTA)

générer et comptabiliser des hits de petite taille.

• (BLASTn) étendre les hits générés à l’aide d ’un algorithme de Xdrop

méthodes antagonistes YASS : temps relatif partagé

taille temps consommégraine groupe ρ δ chaînage alignement total

9 13 135 5 2s 2s 4s9 11 135 5 2s 6s 8s8 13 97 4 7s 7s 14s8 11 97 4 7s 11s 18s7 13 69 4 22s 35s 57s7 11 69 4 22s 41s 69s

25

Comparaison des Programmes

Temps

Résultats obtenus• Comparaison sur S.Cerevisiae chr.V vs chr.IX de

BLASTn et YASS

• Similitudes de score > 20 (Evalue < 0.22) retrouvées

sequence m n mxn BL2SEQ YASSListeria monocytogenes vs innocua plasmid 2 944 528 81 905 2.4 E 11 15.5 s 10.4s

S.cerevisiae chr.V vs chr.IX 576 869 439 885 2.5 E 11 5.3 s 6.8sS.cerevisiae chr.XVI vs chr.IV 918 120 1 531 929 1.4 E 12 80.3 s 36.2 s

Listeria monocytogenes vs S.cerevisiae chr IV 2 944 528 1 531 929 4.5 E 12 625.2 s 106.9 s

26

Caractéristiques techniques

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.

27

Extensions Envisagées

k-mots non contigus : meilleure intégration de ces derniers. (Sensibilité sur CDS)

Inclure un post-traitement pour rassembler les répétitions séparées par des gaps importants.

Inclure la possibilité d’éliminer les répétitions en tandem lorsque l’on recherche des similitudes sur une seule séquence (mreps)

Auto-paramétrage du programme selon la taille et le type de séquence.

28

Conclusion

Nouvelle approche pour la recherche de répétitions

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

• algorithme de regroupement

• critère d’évaluation efficace et sensible Solution satisfaisante

• sensibilité

• sélectivité

29

Questions

agctga

g?cc??

tatgag

caa?ga

cca??a

ctc?gc

ggcgca

tctagg

ag??ac

c???tc

ttcttc

g

???? ??