Appunti VERIFICATO
bioinformatica
Università degli Studi di Napoli - Federico II biotecnologie per la salute Curriculum medico clinico 2019
7 download
Nessun voto ancora
Di cosa parla
- **Needleman-Wunsch (N&W) Algorithm: Principi e Ottimizzazione**
- L'algoritmo N&W, per sequenze di lunghezza 'n', ha una complessità computazionale di O(n²) per i calcoli e O(n³) per il processo complessivo.
- Un approccio migliorato punta a ridurre la complessità a O(n²) tramite una rappresentazione ottimizzata del percorso, valutando solo tre possibilità (diagonale, verticale, orizzontale) per ogni cella.
- In una matrice quadrata, gli angoli di partenza equivalenti garantiscono lo stesso valore di percorso ottimale.
- La differenziazione tra 'match' (diagonale, aggiunge punti) e 'gap' (orizzontale/verticale, sottrae punti) è cruciale per semplificare i calcoli.
- **Miglioramenti alla Rappresentazione del Percorso (N&W Accelerato)**
- Ogni cella offre tre opzioni: diagonale (somma), gap verticale (sottrazione/zero) e gap orizzontale (sottrazione).
- Si sceglie il percorso che massimizza il punteggio, rendendo la tecnica più rapida (O(3*n²)).
- Un sistema di scoring con valori molto negativi per i gap scoraggia i percorsi orizzontali e verticali, privilegiando i match diagonali.
- **Waterman e Smith (W&S) Algorithm: Il Concetto di Allineamento Locale**
- W&S è un algoritmo bioinformatico basato sulla programmazione dinamica, derivato da N&W, per l'allineamento locale di sequenze.
- La differenza fondamentale è che i valori negativi delle celle vengono azzerati, impedendo la propagazione di punteggi bassi.
- Per un'efficace identificazione degli allineamenti locali, i mismatch e i gap devono avere valori negativi.
- Il principio è "seguire il percorso che non fa perdere punti", mantenendo i punteggi positivi o azzerati.
- **Confronto e Applicazioni N&W vs. S&W:**
- **N&W** esegue l'**allineamento globale**, allineando l'intera lunghezza di due sequenze, ideale per sequenze con similarità estesa.
- **S&W** esegue l'**allineamento locale**, identificando le sottosequenze più simili all'interno di sequenze più grandi.
- Nella matrice S&W, i valori massimi non sono localizzati e i percorsi possono salire e poi scendere, azzerandosi se negativi, evidenziando così le regioni di alta similarità.
- Un 'doppio negativo' (punteggi negativi per gap e mismatch) è essenziale in S&W per differenziare e prevenire la ridondanza.
- **Esempi:** S&W è utile per individuare pattern di similarità locali (es. esone umano vs. sequenza genomica umana).
- **Strumenti:** "Needle Stretcher" implementa N&W per allineamenti globali, mentre "Water Matcher" implementa S&W per allineamenti locali.