Les logiciels

La croissance pratiquement exponentielle de la taille des bases de données à forcé les biologistes à utiliser des logiciels spécifiques de plus en plus performants notamment du point de vue de la compléxité temporelle. De plus rare sont les chercheurs qui ont assez de ressources financières pour avoir accès aux machines massivement parallèles. C'est pourquoi on peut aujourd'hui interroger des serveurs web utilisant des logiciels de plus en plus performants avec des bases de données mises à jour quotidiennement.

Ces logiciels, pour les plus utilisés, ont pour but de rechercher des séquences similaires. Leur principe est de trouver dans une ou plusieurs bases de données le meilleur alignement avec la séquence fournie. Ils utilisent les matrices de substitutions pour rester proche de la réalité biologique. Pour parvenir aux meilleurs alignements, on emploie la notion de 'score de similitude'. Ce score est augmenté par une similitude ponctuelle entre deux acides aminés, au contraire on le diminue ou on le laisse inchangé lorsque deux acides aminés sont différents ou qu'on effectue une insertion/suppression (ou 'gap').

Pour améliorer leur vitesse d'exécution, sans perdre trop de sensibilité, on utilise des méthodes heuristiques, de cette façon, avant la véritable recherche on écarte par approximations les séquence ayant peu de chance de correspondre. Il existe de nombreux programme effectuant ce type d'opérations. On décrira ici les deux familles de logiciels les plus utilisées: Blast (Altschul et al, 1990) et FastA (Pearson and Lipman, 1988). Tout les deux utilisent des méthodes très heuristiques, ils ne procurent donc pas un résultat très fiable. Il est pratiquement nécessaire du point de vue de la recherche biologique de soumettre les séquences ainsi obtenues à une nouvelle analyse avec des outils plus pointus. Ceci explique que seules les machines parallèles ou massivement parallèle qui utilisent l'algorithme beaucoup plus exact de Smith&Waterman fournissent des résultats exploitables.

Blast 1.4(Basic Local Alignement Search Tool):

Il utilise les heuristiques, et donne des résultats sans 'gap'. Il s'exécute rapidement mais manque souvent de sensibilité.

Blast est l'algorithme de recherche heuristique utilisée par blastp, blastn, blastx, tblastn et tblastx. Ces 5 outils permettent d'évaluer différentes combinaisons de séquences de protéines et d'acides aminés aux bases de données.

blastp: compare une séquence donnée d'acides aminés à une base de données de séquences protéiniques.
blastn: compare une séquence nucléique donnée traduite en 6 phases à une base de données de séquences nucléiques.
blastx: compare une séquence donnée nucléique à une base de données de séquences de protéines.
tblastn: compare une séquence donnée protéinique à une base de données de séquences nucléiques traduite en 6 phases.
tblastx: compare une séquence donnée nucléique traduite en 6 phases à une base de données de séquences nucléique traduite en 6 phases.

utilisation du programme:
blastp aadb aaquery [paramètres]
blastn ntdb ntquery [paramètres]
blastx aadb ntquery [paramètres]
tblastn ntdb aaquery [paramètres]
tblastx ntdb ntquery [paramètres]

Principaux paramètres:
W=#
S=#
E=#
M=#
N=#
-matrix nom_fichier
Exemple:
blastn gbvrl query1 W=4 M=4 N=-3
blastp sw34 query2 -matrix PAM250

On note que du point de vue de la sensibilité, si W est faible alors on obtient une bonne sensibilité pour un temps de calcul long. Si W est élevé, l'exécution est rapide mais on a peu de sensible. Du point de vue de la sélectivité, si E ou S élevé alors la sélectivité est importante.

exemple de résultat de Blast1.4

Blast 2:

Blast 2 prend en compte le insertion/suppresion ou 'gap', ce que ne faisait pas son prédécesseur. On note aussi quelques changements dans la mise en forme des données en sortie, plus efficace. Il utilise mes mêmes 5 sous-logiciels.

Algorithme: Ils se servent du modèle statistique de Karlin et Altschul (1990, 1993) et de la notion de P-value, qui mesure la probabilité de de trouver par hasard une séquence homologue à la séquence soumise. Ces régions ayant un score significatif sont connues sous le nom de HSP (High-scoring Segment Pairs ou paires de segments ayant un grand score de similitude). On les obtient en déterminant les plus longues chaînes sans insertion/suppression (ou gap) qui ont un score au dessus d'un seuil choisi. On définit aussi la notion de MSP (Maximal-scoring Segment Pair) qui est la paire de segments qui obtient le meilleur score de similitude. Plus la P-value est petite plus cette probabilité est grande. Les méthodes statistiques sont utilisées pour déterminer la signification biologique du MPS et par conséquent des HSPs obtenues lors de la comparaison.

Ils sont conçus pour s'exécuter rapidement et efficacement dans leur configuration de défaut. il est tout de même possible de changer certains paramètres.

étapes de l'algorithme:

exemple de résultat de Blast2 pour un alignement local

exemple de résultat de Blast2 pour un alignement global

FastA:

FastA est accompagné de TFastA (ou FastATrans). Il effectue la recherche de similitudes plutôt "globale".
Fasta: recherche les similitudes entre une base de donnée de séquences nucléiques et une séquence nucléique ou entre une base de donnée protéinique et une séquence protéinique.
TFastA: recherche les similitudes entre une base de donnée de séquences nucléiques traduite dans les 6 phases et une séquence protéinique.

Algorithme: FastA effectue plusieurs lectures de la base de données au cours desquelles il ne retient que les meilleures solutions provisoires. Il identifie rapidement les zones de similitude puis à partir des meilleures similitudes applique localement un algorithme d'alignement optimal.

étapes de l'algorithme:

utilisation du programme:
fasta query bank [-options] [ktup]

Options (paramètres):
ktup (valeur entre 1 et 12)
-s fichier (matrice de substitution)
-f coût de cassure (gap)
-g coût d'extension (gap)

Sensibilité:
ktup faible entraîne une bonne sensibilité et temps de calcul long.
ktup élevé donne une exécution rapide mais peu de sensibilité.

Les résultats sont obtenus en format FastA

Ssearch:

Disponible dans le package FASTA Ssearch (W.R. Pearson) permet l'exploration des banques.
Il utilise l'algorithme de Smith et Waterman avec 'gap'. Il permet la recherche de similarités locales, mais a un temps d'éxécution très grand.

Utilisation du programme:
ssearch [options] séquence banque

options:
-Q supprime le mode interactif
-s matrice spécification de la matrice de substitution
-f # spécification coût du premier gap
-g # spécification coût des gaps suivants
-b # nombre de scores à afficher
-d # nombre d'alignements à afficher