FASTA (programme informatique)

Informations
Développé par	William R. Pearson
Dernière version	36.3.5 (mai 2011)
Dépôt	github.com/wrpearson/fasta36
Écrit en	C
Système d'exploitation	Type Unix, Linux, Microsoft Windows et macOS
Environnement	UNIX, Linux, Windows, Mac OS X
Type	Bioinformatique
Licence	Libre pour un usage académique
Site web	fasta.bioch.virginia.edu

FASTA est à l'origine un programme d'alignement de séquences d'ADN et de protéine développé par William R. Pearson en 1988^[1]. Au fil de son développement, il est devenu une suite de programmes, étendant ainsi ses possibilités en termes d'alignement. FASTA est le descendant du programme FASTP publié par David J. Lipman et William R. Pearson en 1985^[2]. Un des héritages de ce programme est le format de fichier FASTA qui est devenu un format standard en bioinformatique.

Historique

À l'origine, le programme FASTP était conçu pour la recherche de similarités dans les séquences protéiques (protéine:protéine)^[2]. L'amélioration de ce dernier donna naissance au programme FASTA qui ajouta la possibilité de faire ce même type de recherche pour des séquences nucléiques (ADN:ADN) mais également des recherches de similarités entre séquences nucléiques et protéiques (ADN_traduit:protéine)^[1]. Par ailleurs la méthode de calcul du score de similarité fut aussi améliorée pour prendre en compte de multiples régions^[1].

En même temps que la publication de FASTA, deux autres programmes furent publiés^[1] : RDF2, programme testant statistiquement la pertinence des scores de similarité par une méthode de randomisation, et LFASTA, programme identifiant des similarités de séquence localement et non à l'échelle de la séquence entière (on peut voir ici les prémices du programme BLAST) et permettant l'affichage de ces alignements.

FASTA devrait être prononcé [fasteɪ] puisqu'il signifie "FAST-All", étant donné qu'il fonctionne avec l'alphabet nucléique et protéique et est une extension des programmes d'alignement "FAST-P" (pour protéine) et "FAST-N" (pour nucléotide)^[3]. Cependant la prononciation usuellement employé est [fasta].

Utilisation

Actuellement, FASTA est une suite de programmes permettant des alignements protéine:protéine, ADN:ADN, protéine:ADN_traduit (avec prise en charge des décalages de cadres de lecture) et pouvant utiliser des séquences ordonnées ou non-ordonnées^[4]. Les versions récentes de cette suite incluent des algorithmes spéciaux de recherche par traduction qui traitent correctement les erreurs de décalage de cadres de lecture (ce qu'une recherche dans les six cadres de lecture ne traite pas aussi efficacement) lors d'une comparaison de séquences nucléique et protéique.

En plus des méthodes de recherche heuristique rapides, la suite FASTA fournit le programme SSEARCH qui est une implémentation de l'algorithme de Smith-Waterman.

L'un des objectifs de cette suite est le calcul de statistiques de similarités précises, de sorte que les biologistes puissent juger s'il s'agit d'un alignement obtenu par chance ou s'il peut être utilisé pour inférer une homologie.

La suite FASTA peut être utilisée localement ou à partir de trois serveurs se situant :

sur le site officiel
sur le site de l'Institut Européen de Bioinformatique (EBI)
sur le site de l'Encyclopédie de Gènes et Génomes de Kyoto (KEGG)

Le format de fichier FASTA utilisé comme fichier d'entrée pour les programmes de cette suite est un format devenu un standard de facto par sa très large utilisation dans le domaine bioinformatique^[5], étant amplement utilisé par d'autres programmes de recherche de séquences au sein de bases de données (tel que BLAST) ou d'alignement de séquences (comme Clustal, T-Coffee, etc.).

Méthode de recherche

Pour une séquence de nucléotides ou d'acides aminés donnée, FASTA recherche un ensemble de séquences correspondantes au sein d'une base de données par alignements locaux de séquences.

Le programme FASTA suit une méthode heuristique qui contribue à une exécution très rapide des tâches. Il recherche pour cela des correspondances de groupes d'acides aminés ou de nucléotides consécutifs de longueur k (des k-uplets ou k-tuples en anglais). Il observe en premier lieu le patron des correspondances de ces motifs d'une longueur donnée, et retient les correspondances possibles avant d'exécuter une recherche plus chronophage par l'utilisation d'un algorithme de type Smith-Waterman.

Le taille du motif, donnée par le paramètre ktup, contrôle la sensibilité et la rapidité du programme. Accroître la valeur du ktup diminue le nombre total de résultats pouvant être trouvés, mais accélère la rapidité du programme. À partir des résultats de motifs, le programme analyse les segments qui contiennent un groupe de résultats proches. Il traite ensuite ces segments afin de trouver des correspondances possibles.

Bien qu'il y ait quelques différences entre FASTN et FASTP concernant le type de séquence utilisé, ils traitent tous deux les données en quatre étapes et calculent trois scores pour décrire et formater les résultats de similarités de séquences. Ces étapes sont :

Identifier les régions de plus haute densité pour chaque comparaison. Utilisation d'un ktup égal à 1 ou 3.

Pour cette étape, toutes ou une partie des identités entre deux séquences sont identifiés à l'aide d'une table de correspondance. La valeur du ktup détermine combien d'identités consécutives sont requises pour qu'une correspondance puisse être déclarée. Ainsi plus la valeur de ktup est faible, plus la recherche est sensible. Un ktup de 2 est fréquemment utilisé pour une séquence protéique et un ktup de 4 ou 6 pour une séquence nucléique. Concernant les oligonucléotides courts, un ktup de 1 sera préféré. Le programme identifie ensuite toutes les régions locales similaires entre deux séquences, représentées par des diagonales de longueur variable sur un dot plot, en comptant les correspondances de ktup et en pénalisant les non-correspondances. De cette façon, les régions locales ayant une haute densité de correspondances sur la diagonale sont différenciées des l'ensemble des résultats. Pour les séquence protéiques, un score est calculé en utilisant une matrice de similarité entre acides aminés, comme BLOSUM50, pour chaque correspondance de ktup. Ceci permet aux groupes d'identités avec un score élevé de similarité de contribuer de façon plus importante au score de la diagonale de la région locale que les identités avec un faible score de similarité. Les séquences nucléiques utilisent quant à elles la matrice d'identité. Les dix meilleures régions locales sont sélectionnés sur toute la diagonale et sauvegardées.

Nouveau scan des régions sauvegardées à l'aide de matrices de similarité. Élimination des extrémités de chaque région pour inclure uniquement celle qui contribuent aux scores les plus élevés.

Le nouveau scan des dix régions sélectionnées est réalisé à l'aide d'une matrice de scores afin d'effectuer une recalibration permettant d'analyser des identités plus petite que la valeur du ktup. De plus, lors de la recalibration, les substitutions conservatives qui peuvent contribuer au score de similarité sont prises en compte. Bien que la matrice utilisée pour les séquences protéiques soit une matrice BLOSUM50, les matrices de scores basées sur le nombre minimum de changement de base requis pour une substitution spécifique, pour une identité unique ou pour une mesure alternative de similarité telle que la matrice de substitution PAM, peuvent aussi être utilisées. Pour chacune des régions de la diagonale rescannées de cette façon, une sous-région comprenant le score maximum est identifié. Les scores initialement trouvés à l'étape 1 sont utilisés pour ordonner les séquences de la base de données. Le score le plus élevé est désigné comme score init1.

Dans un alignement, si plusieurs régions initiales avec un score plus élevé que la valeur seuil (valeur CUTOFF) sont identifiées, vérifie si les régions initiales éliminées peuvent être jointes pour former un alignement approximatif comprenant des gaps. Calcule un score de similarité correspondant à la somme des scores des régions jointes avec une pénalité de 20 points pour chaque gap. Ce score initial (initn) est utilisé pour ordonner les séquences de la base de données. Le meilleur score de la région initialement trouvée à l'étape 2 (init1) est rapporté.

Le programme calcule un alignement optimal des régions initiales en combinant les régions compatibles présentant le meilleur score. Cet alignement optimal peut être rapidement calculé en utilisant une algorithme de programmation dynamique. Le score initn résultant est utilisé pour ordonner les séquences de la base de données. Cette méthode d'assemblage augmente la sensibilité mais diminue la sélectivité. Le calcul d'une valeur seuil pour contrôler cette étape a donc été implémenté : cette valeur correspond approximativement à un écart-type au-dessus du score moyen attendu pour des séquences sans rapport au sein des séquences de la base de données. Une séquence d'entrée de 200 résidus avec un ktup de 2 utilisera une valeur seuil de 28.

Utilise l'algorithme de Smith-Waterman par bande pour calculer une score optimal pour l'alignement.

Cette étape utilise un algorithme de Smith-Waterman par bande pour déterminer un score optimisé (opt) pour chaque alignement de la séquence d'entrée à la base de données. L'algorithme prend en compte une bande de 32 résidus centrée sur la région init1 de l'étape 2 pour calculer un alignement optimal. Après la recherche de l'ensemble des séquences, le programme détermine graphiquement les scores initiaux de chaque séquence de la base de données sur un histogramme et teste le score opt afin de savoir s'il est statistiquement significatif. Pour les séquences protéiques, l'alignement final est produit en utilisant un alignement complet de Smith-Waterman. Pour les séquences nucléiques, un alignement par bande est fourni.

Références

↑ ^{a b c et d} (en) Pearson WR. & Lipman DJ., « Improved tools for biological sequence comparison. », Proceedings of the National Academy of Sciences of the United States of America, vol. 85, n^o 8,‎ 1988, p. 2444-8 (ISSN 0027-8424, PMID 3162770, DOI 10.1073/pnas.85.8.2444)
↑ ^{a et b} (en) Lipman DJ. & Pearson WR., « Rapid and sensitive protein similarity searches. », Science (New York, N.Y.), vol. 227, n^o 4693,‎ 1985, p. 1435-41 (ISSN 0036-8075, PMID 2983426, DOI 10.1126/science.2983426)
↑ (en) William R. Pearson, « Documentation de la version 2.0 de la suite de programmes FASTA », sur Center for Biological Sequence analysis (consulté le 9 février 2013)
↑ (en) William R. Pearson, The FASTA program package, 2011, 29 p. (lire en ligne)
↑ (en) Cock PJ., Fields CJ., Goto N., Heuer ML. & Rice PM., « The Sanger FASTQ file format for sequences with quality scores, and the Solexa/Illumina FASTQ variants. », Nucleic Acids Research, vol. 38, n^o 6,‎ 2010, p. 1767-71 (ISSN 1362-4962, PMID 20015970, DOI 10.1093/nar/gkp1137)

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « FASTA » (voir la liste des auteurs).

Voir aussi

Articles connexes

Liens externes

(en) Site officiel de FASTA
(en) FASTA sur EBI - Page web de l'EBI permettant d'accéder à la suite FASTA
(en) FASTA sur KEGG

[Pearson1988-1] {a b c et d} (en) Pearson WR. & Lipman DJ., « Improved tools for biological sequence comparison. », Proceedings of the National Academy of Sciences of the United States of America, vol. 85, n^o 8,‎ 1988, p. 2444-8 (ISSN 0027-8424, PMID 3162770, DOI 10.1073/pnas.85.8.2444)

[Lipman1985-2] {a et b} (en) Lipman DJ. & Pearson WR., « Rapid and sensitive protein similarity searches. », Science (New York, N.Y.), vol. 227, n^o 4693,‎ 1985, p. 1435-41 (ISSN 0036-8075, PMID 2983426, DOI 10.1126/science.2983426)

[fasta20-3] (en) William R. Pearson, « Documentation de la version 2.0 de la suite de programmes FASTA », sur Center for Biological Sequence analysis (consulté le 9 février 2013)

[4] (en) William R. Pearson, The FASTA program package, 2011, 29 p. (lire en ligne)

[Cock2010-5] (en) Cock PJ., Fields CJ., Goto N., Heuer ML. & Rice PM., « The Sanger FASTQ file format for sequences with quality scores, and the Solexa/Illumina FASTQ variants. », Nucleic Acids Research, vol. 38, n^o 6,‎ 2010, p. 1767-71 (ISSN 1362-4962, PMID 20015970, DOI 10.1093/nar/gkp1137)

[1]

[2]

[3]

[4]

[5]