Allineamento delle Stringhe e Distanza di Editing

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Qual è il significato del carattere speciale '-' nell'allineamento delle stringhe?

Simboleggia una sostituzione di caratteri

Indica un carattere mancante in entrambe le stringhe

Rappresenta un'inserzione nell'altra stringa (correct)

Denota una cancellazione nella sequenza (correct)

Cosa indica un'alta similarità tra due stringhe?

Le stringhe presentano molte sostituzioni

Ci sono molte differenze tra le stringhe

Le stringhe sono identiche

Le stringhe sono poco distanti l'una dall'altra (correct)

Qual è il metodo utilizzato per calcolare la distanza di editing tra due stringhe?

Minimo numero di operazioni necessarie per trasformare una stringa nell'altra (correct)

Analisi della frequenza dei caratteri comuni

Conteggio dei caratteri unici nelle stringhe

Differenza di lunghezza tra le due stringhe

Qual è un esempio di operazione considerata nella distanza di editing?

Sostituzione di un carattere con un altro Signup and view all the answers

Quale funzione viene usata per valutare il grado di similarità tra due stringhe?

Scoring function Signup and view all the answers

Qual è il punteggio totale dell'allineamento A dopo aver calcolato il punteggio del nuovo allineamento?

15 Signup and view all the answers

Come viene aggiornato il punteggio dell'allineamento quando si aggiunge un nuovo punteggio?

Sommandolo al punteggio precedente Signup and view all the answers

Quale dei seguenti non rappresenta una sequenza allineata?

C Y Signup and view all the answers

Qual è il punteggio dell'allineamento B nell'ultimo esempio fornito?

9 Signup and view all the answers

Nella derivazione dell'algoritmo di programmazione dinamica, qual è il risultato quando si calcola CTA?

C + AT Signup and view all the answers

Qual è la percentuale di identità associata alla matrice PAM 200?

25% Signup and view all the answers

Quando è consigliabile utilizzare matrici PAM con indici più alti?

Quando le sequenze sono significativamente distanti filogeneticamente Signup and view all the answers

Quale delle seguenti affermazioni è vera riguardo le matrici BLOSUM?

Derivano da allineamenti delle regioni più conservate di famiglie di proteine Signup and view all the answers

Cosa avviene per ogni tipo di matrice BLOSUM quando si stabilisce la soglia di identità?

Si eliminano sequenze con identità superiore a una certa percentuale Signup and view all the answers

Qual è il punteggio associato all'amminoacido 'A' nella matrice PAM 120?

2 Signup and view all the answers

Qual è il significato della notazione 'neutro' nella matrice degli amminoacidi?

Indica che non ha effetto sull'allineamento Signup and view all the answers

Nella matrice PAM, qual è il punteggio per l'amminoacido 'C' quando confrontato con se stesso?

-5 Signup and view all the answers

Qual è la percentuale di identità associata alla matrice PAM 110?

50% Signup and view all the answers

Che cosa rappresenta Sij in un algoritmo di programmazione dinamica?

Il punteggio di un allineamento ottimale tra due sequenze Signup and view all the answers

Quale delle seguenti affermazioni è vera riguardo le penalità per gap?

Dipendono dalla lunghezza del gap nelle sequenze Signup and view all the answers

Quale movimento consente di raggiungere una posizione (i,j) nell'algoritmo di programmazione dinamica?

Un movimento diagonale o da qualsiasi posizione nella stessa riga o colonna Signup and view all the answers

Cosa indica la funzione s(ai, bj) negli algoritmi di allineamento?

Il punteggio associato all'allineamento dei caratteri ai e bj Signup and view all the answers

Qual è la principale funzione di Sij durante il calcolo dell'allineamento ottimale?

Fornire il miglior punteggio per ciascuna posizione nella matrice Signup and view all the answers

Che cosa si intende per 'allineamento ottimale'?

Un allineamento con punteggio massimo possibile Signup and view all the answers

Quale equazione descrive il calcolo del punteggio Sij?

Sij = max{Si-1,j-1 + s(ai,bj), Si-x,j - wx} Signup and view all the answers

Qual è il ruolo iniziale della matrice Sij nel calcolo dell'allineamento?

Presentare punteggi iniziali per gli allineamenti Signup and view all the answers

Quale metodo di scoring si basa sul costo dei gap in funzione della loro lunghezza?

Scoring lineare Signup and view all the answers

Qual è il punteggio associato ad un match?

8 Signup and view all the answers

Quale delle seguenti affermazioni riguarda un gap non isolato?

Dà sempre lo stesso costo di un gap isolato. Signup and view all the answers

In un allineamento locale, quale è considerato il punto centrale per la valutazione?

Solo parti della sequenza. Signup and view all the answers

Che tipo di punteggio è il 'punctum doloris' in un scoring affine?

Gap-open penalty Signup and view all the answers

Quale delle seguenti affermazioni è vera riguardo ai modelli di transizione tra sequenze?

Eventi di mutazione sono più significativi. Signup and view all the answers

Cosa indica il simbolo '-' negli allineamenti?

Un gap. Signup and view all the answers

Qual è la differenza principale tra allineamento globale e allineamento locale?

L'allineamento locale si concentra su sottostringhe con similarità massima. Signup and view all the answers

Qual è l'obiettivo di un allineamento globale tra sequenze?

Allineare completamente tutte le parti. Signup and view all the answers

Quale metodo di scoring considera sia la penalità di apertura che quella di estensione dei gap?

Modello affine Signup and view all the answers

Qual è uno degli algoritmi comunemente utilizzati per l'allineamento globale?

Needleman-Wunsch Signup and view all the answers

Cosa si intende per 'similitudine' in un allineamento locale?

La massimizzazione del punteggio di allineamento tra sottostringhe. Signup and view all the answers

Cosa rappresenta il punteggio finale di 18 nell'esempio di allineamento?

La somma di match e gap. Signup and view all the answers

Quale dei seguenti è un metodo di ricerca in una banca dati di sequenze?

FASTA Signup and view all the answers

Perché è preferibile avere molte coincidenze sparse piuttosto che poche coincidenze concentrate?

Per garantire risultati più accurati nell'identificazione di simile sequenze. Signup and view all the answers

Cosa rappresenta il punteggio core in un allineamento di sequenze?

Il valore risultante dalla somma delle coincidenze. Signup and view all the answers

Qual è l'obiettivo primario dell'allineamento locale rispetto all'allineamento globale?

Identificare il segmento più simile in due sequenze. Signup and view all the answers

Quale metodo è più adatto per confrontare sequenze simili in un database?

Local aligner Signup and view all the answers

Study Notes

Allineamento e similarità di sequenze

L'allineamento di due o più sequenze aiuta a trovare regioni simili che potrebbero svolgere la stessa funzione.
La similarità tra sequenze può essere definita tramite una funzione distanza: sequenze più simili sono meno distanti.
Esistono diversi algoritmi di allineamento, ognuno con la sua funzione distanza.
Dato un allineamento, si può assegnare un punteggio (score) che indica il grado di similarità tra le sequenze.

Confrontare sequenze

Il confronto tra sequenze nucleotidiche o aminoacidiche è un compito fondamentale della bioinformatica.
In natura, le strutture molecolari sono generalmente modificazioni di modelli preesistenti, non create ex novo.
Gli obiettivi del confronto includono: filogenesi molecolare, evoluzione dei singoli genomi e caratterizzazione di proteine con funzione sconosciuta

Confrontare sequenze (2)

La filogenesi molecolare, tramite il confronto di sequenze nucleotidiche o aminoacidiche, permette di creare alberi filogenetici che mostrano la distanza ed i rapporti evolutivi tra le molecole analizzate.
A differenza della filogenesi classica che si basa sulle caratteristiche morfologiche degli organismi, la filogenesi molecolare si concentra sulle relazioni evolutive tra le molecole.
La caratterizzazione di proteine con funzione ignota può essere effettuata confrontando la proteina sconosciuta con famiglie di proteine a funzione nota, per formulare ipotesi sulla funzione della proteina sconosciuta.

Similarità e omologia

Tra due o più sequenze può esserci un certo grado di similarità, misurabile in modi diversi (a seconda se sono sequenze nucleotidiche o aminoacidiche).
La similarità strutturale e funzionale può derivare da una similarità tra sequenze.
L'omologia indica una comune origine evolutiva tra sequenze. Due sequenze sono omologhe se discendono da una comune sequenza ancestrale.
Due o più sequenze simili non sono necessariamente omologhe.

Omologia e Analogia. Ortologia e Paralogia

Omologia indica che due entità (es. due sequenze) condividono la stessa origine filogenetica (provengono da un antenato comune). È un carattere qualitativo.
Similarità (o analogia) indica che due entità (es. due sequenze) hanno un certo grado di somiglianza rispetto a un criterio di confronto. È un carattere quantitativo.
Ortologia si riferisce a elementi omologhi derivanti da un processo di speciazione.
Paralogia si riferisce a elementi omologhi derivanti da un processo di duplicazione genica.

Allineamento di sequenze

Per confrontare sequenze nucleotidiche o proteiche, è necessario allinearli.
Gli esempi presentano allineamenti multipli di brevi sequenze aminoacidiche.

Allineamento Globale vs. Locale

Global alignment: Si cerca la corrispondenza ottimale tra tutte le sequenze.
Local alignment: Si cerca di individuare regioni specifiche di similarità all'interno delle sequenze.

Allineamento a coppie (Pairwise Alignment) - Matrici Dot Plot

Si crea una matrice per confrontare tutti i possibili appaiamenti tra i caratteri delle sequenze da allineare.
La matrice viene riempita annerendo le caselle che contengono la stessa lettera nelle corrispondenti righe e colonne.
Sono disponibili programmi come DOTLET che permettono di creare facilmente le matrici dot plot.

Similarità, distanze e matrici di editing

La similarità tra stringhe può essere valutata calcolando la loro distanza.
Due stringhe con alta similarità sono poco distanti, mentre due stringhe con bassa similarità sono molto distanti.
La distanza di editing è il numero minimo di operazioni di inserimento, cancellazione o sostituzione necessarie per trasformare una stringa nell'altra.

La scoring function: similarità e distanza

La scoring function assegna un punteggio agli allineamenti, valutando il grado di similarità o distanza tra due stringhe.
Un esempio di scoring function assegna un punteggio (+2) per ogni match esatto e (-1) per ogni mismatch o indel.
Un altro esempio di scoring function assegna uno score (0) ai match, (1) alle sostituzioni e (2) agli spazi.

La scoring function, più formalmente

La scoring function (σ) assegna uno score agli allineamenti dei singoli caratteri o spazi.
È possibile costruire scoring function ad hoc per diversi problemi, ad esempio per confrontare aminoacidi, tenendo conto delle loro proprietà chimico-fisiche.

Allineamento di stringhe

Si inizia analizzando il problema generale dell'allineamento di una coppia di stringhe.
Per allineare due stringhe come "acbcdb" e "cadbd", si cercano allineamenti ottimali.
Il carattere "-" rappresenta uno spazio, indicante una cancellazione o inserzione nella sequenza.

Allineamento pairwise(2)

Lo score dell'allineamento di una coppia di sequenze è calcolato sommando gli scores dei singoli allineamenti dei caratteri.
Un allineamento ottimale è quello che minimizza la distanza o massimizza la similarità tra due sequenze.
Gli scores rappresentano il grado di similarità tra sequenze.

Algoritmo di programmazione dinamica

Score di nuovo allineamento = Score dell'allineamento precedente + Score della nuova coppia allineata.
Si ripetono queste operazioni fino ad arrivare alla fine dell'allineamento.
Diagramma che indica le azioni possibili per arrivare alla posizione (i, j) nel diagramma.

Allineamento locale vs. globale

Allineamento globale: Si allineano le intero sequenze.
Allineamento locale: Si allineano i frammenti di sequenza con massimo punteggio.

Ricerca per similarità

BLAST (Basic Local Alignment Search Tool) individua regioni di similarità fra sequenze.
BLAST non effettua un allineamento globale ma si concentra sulle regioni più simili.
BLAST può confrontare migliaia di sequenze rapidamente.

Come funziona BLAST?

BLAST estrae tutte le possible words di lunghezza fissa da una sequenza data.
Per ogni word, crea una lista delle possibili parole corrispondenti nella banca dati, basandosi su una soglia di punteggio.
Il processo viene esteso (a monte e valle) per trovare un tratto di sequenza con punteggio superiore alla soglia.

NCBI BLAST

NCBI BLAST è un'implementazione dell'algoritmo di BLAST.
Offre diversi tipi di BLAST (BLASTN, BLASTP, TBLASTN, BL2SEQ) per diversi tipi di confronto.

Altri argomenti

Matrici di parole e di punti
Analisi di errori nelle parole
Significato strutturale delle sequenze

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Questo quiz esplora i concetti fondamentali dell'allineamento delle stringhe e della distanza di editing. Attraverso una serie di domande, il quiz verifica la comprensione delle operazioni di allineamento e delle metriche di similarità. È un ottimo modo per testare le tue conoscenze in materia di algoritmi di stringhe.