Analyse
bioinformatique des séquences
5. - La comparaison de séquences
5.6 - Le logiciel FASTA
Les qualités de l'algorithme
L'algorithme possède une bonne sensibilité du fait qu'il prend en compte les insertions-délétions. Ceci est fait en minimisant les explorations entre les deux séquences puisqu'on ne considère que les séquences potentiellement intéressantes pour effectuer l'étape de programmation dynamique, en ciblant de plus, les régions où l'on doit effectuer la recherche d'alignement. L'étape ultime d'alignement optimal est réalisée uniquement sur la meilleure région de haute similitude même si d'autres régions possèdent un score suffisant pour l'effectuer. Cela permet d'éviter en partie le bruit de fond dû à des motifs non significatifs et intrinsèques à la séquence recherchée mais a l'inconvénient de ne pas pouvoir considérer de grandes insertions durant l'alignement des séquences.
Cette lacune est maintenant évitée dans la dernière version du logiciel (Octobre 1995) pour l'alignement des séquences protéiques. En effet celle-ci considère la totalité des séquences pour effectuer l'algorithme d'alignement local de Smith et Waterman (1981) plutôt que d'effectuer l'alignement global de Needleman et Wunsch (1970) uniquement sur des portions de séquences protéiques. L'édition des résultats est maintenant triée en fonction des scores opt contrairement aux premières versions qui considéraient les scores initiaux (initn), ce qui rendait parfois difficile la détection d'un alignement dont le score optimal est bon mais dont le score initial initn est médiocre. Enfin Pearson (1990) explique que lorsque le score opt est plus faible que le score initn, alors la similitude est souvent inintéressante.
L'estimation statistique est faite à partir des scores obtenus avec l'ensemble des séquences de la banque. Une estimation statistique est donnée en traçant l'histogramme des meilleures scores obtenus pour chaque séquence de la banque avec le calcul de la moyenne et de l'écart type liés à cette distribution. Cette estimation utilise la théorie selon laquelle les similarités locales d'une séquence comparée avec une banque de données suit une distribution de valeurs extrêmes (voir par exemple Altschul et al.,1994).
Cependant, le logiciel fournit également des programmes d'estimation statistique
basés sur une méthode de Monte Carlo (cf. l'évaluation des
résultats) pour estimer la validité d'un score opt particulier
entre une séquence de la banque et la séquence recherchée.
Il s'agit des programmes PRDF et PRSS qui considèrent une distribution
de valeurs extrêmes pour les scores aléatoires et qui sont directement
inspirés du programme PRDF2 (Pearson, 1990) qui regroupe les séquences
en courts segments pour effectuer les simulations. Le programme PRDF produit
des simulations selon l'algorithme de Needleman et Wunsch appliqué localement
pour l'étape d'alignement optimal alors que le programme PRSS utilise
l'algorithme complet de Smith et Waterman entre deux séquences.
Exemple de fichier résultat
S'exercer avec FASTA
S'exercer avec PRSS
