Allineamento delle Stringhe e Distanza di Editing

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

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.