Recherche heuristique dans les bases de données L’algorithme BLAST

Recherche heuristique dans les bases de donnéesL’algorithme BLASTNadia El-Mabrouk

Problématiques

Est-ce que cette séquence contient un gène? Est-ce que ce gène fait partie d’une famille

connue? Quelle est la fonction de cette protéine? Est-ce que cette protéine existe dans

d’autres organismes? Est-ce que d’autres protéines ont les mêmes

domaines ou motifs structuraux?

Rappel – Alignement de séquences

Seq1

Seq2

Seq1

Seq2

Alignement local:

Seq1

Seq2

Alignement global:

Recherche de motif:

Alignement localSimilarité locale entre S1 et S2: Valeur max d’un alignement

entre deux facteurs qcq de S1 et S2

Exemple: Score 2 pour match et -1 pour mismatch ou espace

CAGCAC TT – GG AT TCTCGG l l l l l TAGT TT A GG -T GGCAT

Problème: Retrouver les deux facteurs des deux séquences de similarité locale maximale

Fonction de score pour les substitutions de nucléotides ou d’AA

Fonction de score pour les trous (gaps)

Matrice BLOSUM 62

Score positif pour les identités, et négatif pour les mismatchs

Méthodes utilisées pour l’alignement local Méthode exacte: Smith-Waterman

Algorithme exact en O(n2) utilisant la programmation dynamique

Trop coûteux pour parcourir une banque de données

Heuristiques: Méthodes approximatives. Pas sûr d’obtenir le meilleur résultat

FASTA et BLAST: Heuristiques les plus utilisées. Basées sur une idée de filtrage Sélectionner des parties de la base de donnée par une

méthode de recherche exacte Pour chaque partie (intervalle) vérifier si une similarité locale

existe

Qualité d’un algorithme de comparaison de séquences Sélectivité: Capacité à ne détecter que la

réalité biologique et rien de plus

Problème des Faux-Positifs

Sensitivité: Capacité à détecter tout ce qui est intéressant sur le plan biologique

Problème des Faux-Négatifs

BLAST: Basic local alignment search tool

Similarité locale entre une séquence requête et une banque de donnéesDevenu populaire grâce à une implémentation très efficace.

BLASTP: séquence de protéine dans BD de protéines BLASTN: séquence de nucléotides dans BD d’ADN BLASTX: séquence de nucléotides (6 ordres de lecture) dans BD de

protéines TBLASTN: séquence de protéine dans BD traduite TBLASTX: séquence traduite dans BD traduite BLASTZ: Étudié pour aligner de longues séquences d’ADN, utilisé pour

l’alignement de l’homme et de la souris PHI-BLAST: Recherche d’une expression régulière (consensus) PSI-BLAST: Construit un consensus, ou matrice de score, à partir d’un

alignement multiple des ``hits’’ de plus haut score obtenus par une recherche BLAST initiale

Méthode utilisée par BLAST Former la liste de tous les facteurs de taille w de la séquence requête P

P

Maximum l-w+1 mots

Pour chaque facteur f, former la liste de tous les mots de taille w dont le score avec f dépasse un seuil T

Exemple: Pour f =PQG, {PQG, PRG, PKG, PDG, PMG…}

Identifier les occurrences exactes des mots de la liste dans la BD

Pour chaque paire de séquences trouvées, étendre l’alignement dans les deux directions, jusqu’à ce que le score de l’alignement chute de X par rapport à sa valeur d’origine. Segment accepté si score>S

Le HSP de score maximal sur l’ensemble de la séquence est appelé maximal scoring segment pair (MSP)

Les alignements locaux HSP sont chaînés pour former des alignements plus longs, incluant des espaces et des trous.

Si le MSP ou les HSP combinés ont un score qui dépasse un certain seuil S, il sont affichés

Paramètres La séquence format FASTA La banque (compressée) W (taille du mot).

Protéines: w de 3 à 5, et T = 17

Donne à peu près 50 mots pour chaque facteur Nucléotides: w = 12

S (seuil de sélection d’un score) Matrices de substitution (BLOSUM 62) ou

score pour les nucléotides (+5/-4)

Évaluation statistique

Expect-value = nb de fois où un HSP est attendu par chance sur l’ensemble de la banque. Plus cette valeur est faible, plus le HSP est significatif

P-value: P(N): Probabilité du score observé. Plus cette valeur est faible, plus le HSP est significatif.

La page d’entrée NCBI BLASThttp://www.ncbi.nlm.nih.gov/BLAST/

On choisit son BLAST

On entre la séquence à chercher Le programme choisi

Choisir la banque de données dans laquelle on veutfaire la recherche

life.csmu.edu.tw/lifeinfo/db_lifescience/0722-1.ppt

On a soumis et on attend les résultats


Les résultats: entête


Les résultats: vue graphique





Documents

Recherche heuristique dans les bases de données L’algorithme BLAST