Appunti VERIFICATO
bioinformatica
169 visualizzazioni
7 download
Nessun voto ancora
Di cosa parla
Riassunto AI · si legge in un minuto
Il documento analizza e confronta gli algoritmi di allineamento di sequenze Needleman-Wunsch (N&W) e Smith-Waterman (S&W), fondamentali in bioinformatica. N&W esegue l'allineamento globale, con una complessità computazionale di O(n³), ottimizzabile a O(n²), e identifica la migliore corrispondenza complessiva. S&W, una derivazione di N&W, è specializzato nell'allineamento locale. La sua innovazione chiave consiste nell'azzerare i punteggi negativi, permettendo di evidenziare regioni di elevata similarità anche in sequenze globalmente dissimili. Entrambi usano la programmazione dinamica, ma S&W è più efficace per la scoperta di pattern localizzati, cruciale per le applicazioni biotecnologiche mediche.
Leggi il riassunto completo
- **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.
Riassunto generato con l'intelligenza artificiale a partire dagli appunti. Come lo facciamo
Stai vedendo l'anteprima delle prime pagine. Il file completo è gratis: registrati per leggerlo tutto.
Studia questi appunti con l'AI
Riassunto e domande d'esame sono gratis: chiedili e ti mandiamo un'email quando sono pronti.
In preparazione: di solito è pronto in giornata.
Questo appunto è gratis. Registrati in 30 secondi per leggere tutte le pagine e scaricarlo.
Simula l'esame con domande costruite su questi appunti.