Algoritmo FASTA Spiegazione

Question

Sto cercando di capire i passaggi di base dell'algoritmo FASTA nella ricerca di sequenze simili di una sequenza di query in un database. Questi sono i passi dell'algoritmo:

1. Identificare incontrate k-parole tra I e J
2. diagonali Punteggi con k-word partite, identificare 10 migliori diagonali
3. regioni iniziali Rescore con una matrice punteggio sostituzione
4. Registrati regioni iniziali utilizzando lacune, penalizzare le lacune
5. Eseguire la programmazione dinamica per trovare allineamenti finali

Sono confuso con il 3 ° e 4 ° passo nell'uso della matrice di punteggio PAM250 e come "unire usando gli spazi".

Qualcuno può spiegare questi due passaggi per me "nel modo più specifico possibile". Grazie

Answer 1

Questo è come funziona FASTA:

1. Trova tutte le identità k-lunghezza, poi trovare le regioni localmente simili scegliendo quelli densa con le identità k-word (cioè molte k-parole, senza troppo molte lacune tra). Vengono utilizzate le dieci migliori regioni iniziali.
2. Le regioni iniziali vengono segnate nuovamente lungo la loro lunghezza applicando una matrice di sostituzione nel solito modo. Sono state identificate le sottoregioni con punteggio ottimale.
3. Creare un allineamento delle regioni iniziali ritagliate utilizzando la programmazione dinamica, con una penalità del gap di 20. Le regioni con un punteggio troppo basso non sono incluse.
4. Ottimizza l'allineamento da 3) utilizzando la programmazione dinamica "a banda" (Smith-Waterman). Questa è una programmazione dinamica limitata alla banda a 32 residui attorno all'allineamento originale, che consente di risparmiare spazio e tempo su una programmazione dinamica completa.

Se ci sono regioni iniziali insufficienti per formare un allineamento in 3), il punteggio migliore da 2) può essere utilizzato per classificare le sequenze per similarità. I punteggi da 3) e 4) possono anche essere utilizzati a tale scopo.

Purtroppo la mia istituzione non ha accesso alla carta FASTA originale, quindi non posso fornire i valori originali dei vari parametri sopra menzionati.

Answer 2

La spiegazione è sostanzialmente corretto, ma l'ottimizzazione di banda finale è centrato su un allineamento migliore ungapped trovato al passo 2. Passo 3 viene usato semplicemente per migliorare la sensibilità nella scelta delle sequenze che ottengono passo 4.

La carta originale può essere vista qui: http://faculty.virginia.edu/wrpearson/papers/pearson_lipman_pnas88.pdf