FASTA

I programmi dinamici come quello di Smith e Waterman sono ideali per allineare tra loro due sequenze in modo esatto, ma sono troppo lenti per effettuare ricerche di similarità in banche dati. Un moderno personal computer è in grado di completare l'allineamento in pochi centesimi di secondo, ma dovendo effettuare una ricerca in una banca dati come GenBank che contiene milioni di sequenze, allora il tempo di esecuzione diventerebbero molte ore. E se si volesse effettuare una ricerca in GenBank per ogni gene identificato nel genoma di un organismo, come per esempio il lievito con i suoi 6000 geni, allora ci vorrebbero diversi anni per completare l'analisi. Per effettuare ricerche di similarità nelle banche dati sono perciò necessari programmi più veloci.
  Il primo programma che ha veramente risposto all'esigenza di effettuare ricerche rapide di similarità in banche dati è stato FASTA, sviluppato da Lipman e Pearson nel 1985. L'algoritmo che consente di velocizzare le ricerche è basato su una strategia di indicizzazione di parole. Un importante parametro del programma è ktup che indica la lunghezza delle parole da indicizzare (chiamate k-tuples). L'indicizzazione consiste nel creare un elenco di tutte le posizioni in cui compare ogni possibile parola all'interno della sequenza.
  Si considerino ora due sequenze di aminoacidi da allineare con ktup = 2. La sequenza che si vuole usare per la ricerca di similarità è chiamata query, mentre subject è una delle sequenze della banca dati.
  Nella prima fase il programma trova parole contigue sulla stessa diagonale, nella seconda fase calcola i punteggi utilizzando una matrice di sostituzione e tiene i punteggi migliori, nella terza fase unisce i frammenti che possono essere congiunti entro una soglia di accettabilità, infine, nell'ultima fase il programma effettua un allineamento accurato utilizzando una variante dell'algoritmo di Smith & Waterman su una stretta banda per ottimizzare l'allineamento.

Schema delle principali fasi di elaborazione del programma FASTA


Pagina di accesso al pacchetto FASTA, disponibile al sito web dell'EBI.



[ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39  ]