© Dunod – Toute reproduction non autorisée est un délit.
37
4.3 • FASTA
Dans un algorithme global, ce qui est recherché c’est l’ensemble des séquences
avec un score significatif sur une longueur proche de la longueur des deux
séquences. Cela correspond typiquement à la recherche d’homologues. Dans l’algorithme local, ce qui est recherché ce sont des zones de similitudes dans des protéines
quelconques (homologues ou pas).
4.3 FASTA
Dans FASTA, les matrices de points entre la séquence d’intérêt (query) et chacune
n
des séquences (Subject) de la banque qui contient n séquences sont calculées dans la
mémoire de la machine. Une première heuristique est utilisée : deux séquences de
protéines homologues présentent des régions identiques. Il s’agit d’une heuristique
dans la mesure où deux séquences homologues peuvent partager jusqu’à 50 %
d’identité sans segment de longueur > 1 identique (cas de l’alternance d’un acide
aminé identique et d’un acide aminé différent). Cette heuristique est d’autant plus
« risquée » que la longueur des segments identiques (mot de longueur k ou k-tuple)
est grande. Mais un k-tuple élevé accélère la vitesse des calculs. Ainsi, pour les
protéines, on utilise un k-tuple compris entre 1 et 4 avec, par défaut, la valeur 2 (et 7
à 11 pour les séquences nucléiques). Une deuxième heuristique est que ces k-tuples
identiques doivent être proches de la diagonale d’une matrice de points et que pour
des raisons d’économie de calculs, seules les identités dans une bande d’une
distance d de la diagonale seront considérées. Les quatre étapes de FASTA sont résumées dans les quatre figures suivantes (figures 4.3 à 4.6).
1. Recherche des k-tuples identiques (calcul du score init1).
2. Chaînage des k-tuples qui sont sur la même diagonale (calcul du score initn). Un
score initn élevé reflète la capacité à étendre sur une même diagonale des segments
identiques.
Figure 4.3 – Un score init1 élevé indique un long segment
identique.
Figure 4.4 – Les diagonales représentées en gras ont pu
être étendues.
37
4.3 • FASTA
Dans un algorithme global, ce qui est recherché c’est l’ensemble des séquences
avec un score significatif sur une longueur proche de la longueur des deux
séquences. Cela correspond typiquement à la recherche d’homologues. Dans l’algorithme local, ce qui est recherché ce sont des zones de similitudes dans des protéines
quelconques (homologues ou pas).
4.3 FASTA
Dans FASTA, les matrices de points entre la séquence d’intérêt (query) et chacune
n
des séquences (Subject) de la banque qui contient n séquences sont calculées dans la
mémoire de la machine. Une première heuristique est utilisée : deux séquences de
protéines homologues présentent des régions identiques. Il s’agit d’une heuristique
dans la mesure où deux séquences homologues peuvent partager jusqu’à 50 %
d’identité sans segment de longueur > 1 identique (cas de l’alternance d’un acide
aminé identique et d’un acide aminé différent). Cette heuristique est d’autant plus
« risquée » que la longueur des segments identiques (mot de longueur k ou k-tuple)
est grande. Mais un k-tuple élevé accélère la vitesse des calculs. Ainsi, pour les
protéines, on utilise un k-tuple compris entre 1 et 4 avec, par défaut, la valeur 2 (et 7
à 11 pour les séquences nucléiques). Une deuxième heuristique est que ces k-tuples
identiques doivent être proches de la diagonale d’une matrice de points et que pour
des raisons d’économie de calculs, seules les identités dans une bande d’une
distance d de la diagonale seront considérées. Les quatre étapes de FASTA sont résumées dans les quatre figures suivantes (figures 4.3 à 4.6).
1. Recherche des k-tuples identiques (calcul du score init1).
2. Chaînage des k-tuples qui sont sur la même diagonale (calcul du score initn). Un
score initn élevé reflète la capacité à étendre sur une même diagonale des segments
identiques.
Figure 4.3 – Un score init1 élevé indique un long segment
identique.
Figure 4.4 – Les diagonales représentées en gras ont pu
être étendues.