Metodologie bioinformatiche

RIDURRE IL TEMPO DI ESECUZIONE

• Si supponga di essere nella seguente situazione con P(1) in s+1

NB: all'interno del matching P[1..5] lungo q=5 esiste il suffisso P[3..5] = aga lungo k=3 che coincide con il prefisso P[1..3].

E' evidente che conviene spostare P(1) in s'+1 = s+(q-k)+1

NB: si è così sicuri che esiste un matching iniziale di lunghezza k=3 tra il prefisso P[1..3] e la sottostringa T[s'+1..s'+3].

Dato che il prefisso P[1...q] coincide con la sottostringa T[s+1...s+q], ci si chiede quale sia il minimo spostamento s'>s tale che:

NB: il confronto dei primi k caratteri di P è superfluo

Dato un pattern P[1, ..., m], si calcola la sua funzione prefisso:

NB: π[q] è la lunghezza del più lungo prefisso di P che è anche suffisso di P[1..q]

Esempio di funzione prefisso π per un pattern P:

Algoritmo di Knuth-Morris-Pratt:

Caratteristiche dell'algoritmo KMP:

• È suddiviso in 2

fasi: pre-processing + ricerca effettiva

• Sposta in genere il pattern P di più posizioni a destra
• La complessità in tempo della fase di pre-processing è O(m)
• La complessità in tempo della fase di ricerca è O(n)

Complessità algoritmo K-M-P: O(m+n)

Algoritmo di Boyer-Moore:

Idee generali:

• Il confronto tra il pattern e il testo avviene da destra a sinistra
• Il numero dei confronti viene ridotto usando due euristiche
• euristica del carattere discordante (bad character rule)
• euristica del buon suffisso (good suffix rule)

NB: quando pattern e testo non coincidono si sceglie il massimo tra gli spostamenti proposti dalle due euristiche

Si supponga di essere nella seguente situazione con P(1) in s+1

NB: il carattere P[k] coincide con il carattere T[s+j] per k=4 e j=7

È evidente che conviene spostare P(1) in s'+1 = s+1+j-k

NB: il carattere P[k] coincide con il carattere T[s+j] per k=4 e j=7 26

Dato che esiste un j

(1≤j≤m) per cui P[j] ≠ T[s+j], trovare il massimo k (1≤k≤m), se esiste, tale che:

e spostare P(1) in s’+1 tale che:

Dato un pattern P, si trova la funzione carattere discordante λ:

NB: σ(i) è l’i-esimo simbolo dell’alfabeto Σ

Euristica del carattere discordante:

CASO 1: il carattere discordante non appare nel pattern P

Lo spostamento è tale da allineare il primo carattere di P con il carattere di T successivo al carattere discordante.

CASO 2: l’occorrenza più a destra in P del carattere discordante è in una posizione k che precede la posizione j del carattere di P allineato con il carattere discordante

Lo spostamento è tale da allineare P[k] con il carattere discordante in T(s+j).

CASO 3: l’occorrenza più a destra in P del carattere discordante è in una posizione k successiva alla posizione j del carattere di P allineato con il carattere discordante

Si può solo effettuare lo

spostamento di un postoa destra.Euristica del buon suffisso:Si supponga di essere nella seguente situazione con P (1) in s+1 27NB: la sottostringa P[2..4] coincide il suffisso P[5..7] e quindi con la sottostringa T[s+5..s+7]È evidente che conviene spostare P(1) in s’+1NB: la sottostringa P[2..5] coincide il suffisso P[5..7] e quindi con laDato che il suffisso P[j+1, m] coincide con la sottostringa T[s+j+1, s+m], occorre trovare, se esiste,la posizione k<j più a destra tale che:e spostare P in s’+1 tale che:NB: il confronto dei caratteri di P da k a k+m-j è superfluo.Dato un pattern P, si trova la funzione suffisso γ:Euristica del buon suffisso• CASO 1: k non esiste➪ si sposta P fino a far coincidere un suo prefisso con un suffisso di T[s+j+1..s+m], o di mpassi se nessun prefisso di P è suffisso di T[s+j+1..s+m]• CASO 2: k esiste➪ si sposta P del numero minimo di passi occorrente per far coincidere un suo prefissoproprio

• È suddiviso in due parti: pre-processing + ricerca effettiva
• Sposta in genere il pattern P di più posizioni a destra
• La fase di pre-processing è basata su due euristiche
• Funziona “bene” se il pattern P è relativamente lungo e se l'alfabeto |Σ| è ragionevolmente grande
• La complessità in tempo della fase di pre-processing è: O(|Σ|+m)+O(m) = O(|Σ|+m)
• La complessità in tempo della fase di ricerca è: O(n-m+1)m = O(nm)
• La complessità in tempo di BM è: O(nm)

SEQUENZA

Cos'è un allineamento globale?

Date due sequenze sull'alfabeto Σ:

S = s1s2…sn

T = t1t2…tm

Un allineamento (globale) di S e T consiste in una coppia di sequenze S' = s'1s'2…s'l e T' = t'1t'2…t'l sull'alfabeto Σ U{-} (con - carattere di spazio), che godono delle seguenti proprietà:

|S'| = |T'| = l (max(n,m) ≤ l ≤ (m+n))

- Eliminando gli spazi da S' si ottiene S

- Eliminando gli spazi da T' si ottiene T

- Se s'i = -, allora t'i ≠ - e viceversa

Match (ES):

La definizione matematica riflette semplicemente una corrispondenza a coppie tra i caratteri di una sequenza, ma a noi interessa un allineamento che rifletta la relazione evolutiva tra due o più omologhi.

- Strutture o sequenze ortologhe in due organismi sono sequenze omologhe che sono evolute dalla stessa caratteristica nel loro ultimo antenato comune ma

• Sequenze omologhe la cui evoluzione riflette invece eventi di duplicazione genica si definiscono paraloghe.
• ES: la catena β dell'emoglobina è un paralogo della catena α dell'emoglobina e della mioglobina, dal momento che ambedue si sono evolute dallo stesso gene ancestrale attraverso ripetuti eventi di duplicazione genica.
• La similarità biologica è spesso dovuta ad omologia, ma può anche presentarsi per caso oppure per fenomeni di convergenza adattativa.
• ES: l'ala di un uccello e l'ala di un pipistrello si sono evolute indipendentemente e di conseguenza non sono omologhe.
• Nel trattare le sequenze è sempre più corretto utilizzare il termine similarità, in quanto è sempre possibile stabilire quanto due sequenze siano simili, mentre non sempre si può decidere se la similarità sia dovuta ad omologia, a convergenza adattativa.

oppure al caso. Rispetto alla distanza di edit, massimizza la similarità anziché minimizzare la differenza. La distanza di edit è riconducibile ad esso.

Tecniche utilizzate:

• Analisi di dot matrix (dotplot)
• Algoritmi di Programmazione Dinamica
• Metodi euristici (FASTA, BLAST)

Matrice a punti (dot plot):

1. Consideriamo una matrice nxm in cui le righe e le colonne sono indicizzate rispettivamente dalle sequenze S (dall'alto in basso) e T (da sinistra a destra)
2. In ogni punto in cui le etichette di riga e di colonna coincidono, introduciamo un asterisco nel grafico

NB: le regioni delle sequenze che possono essere allineate senza introdurre gap emergono come una serie contigua di punti sulla diagonale

Le matrici a punti forniscono una buona rappresentazione grafica di un allineamento. Inoltre, consentono di visualizzare similarità di sequenze anche in presenza di gaps, che appaiono come "salti di diagonale".

Esistono programmi in grado di sfruttare

• EMBOSS
• DOTTER

• Le sequenze S' e T' hanno la stessa lunghezza (max(n,m) ≤ l ≤ (m+n))
• Eliminando gli spazi da S' si ottiene S
• Eliminando gli spazi da T' si ottiene T
• Se S' = -, allora T' ≠ - e viceversa

Per farle raggiungere la stessa lunghezza si aggiungono GAP: la seconda coppia di sequenze è ottenuta dalla prima grazie all'aggiunta dei GAP. La lunghezza può variare: prendo la più lunga e la lascio invariata, quella più corta viene allungata aggiungendo GAP.

ES:

1. A A C -
2. G A T T

Scegliamo quello che ci consente di misurare meglio la somiglianza tra due sequenze. ASSUNZIONE: Sequenze simili Funzioni simili

Come si misura la similarità?

Allineamento senza gap interni:

• Si scrivono le due sequenze su due righe, in tutte le posizioni relative possibili
• Per ognuno degli allineamenti generati si calcola un punteggio contando le

posizioni in cui compaiono gli stessi simboli (matches): 31•

→Simboli = 1•

→Simboli diversi o gap 0- L'allineamento col massimo punteggio verrà scelto come il migliore degli allineamenti possibili (crescono esponenzialmente), e il punteggio, normalizzato come percentuale della lunghezza delle sequenze, rappresenta la misura di similarità tra le sequenze

Avere 80 matches su una lunghezza di 100 è diverso che averne 80 sulla lunghezza di 200→bisogna normalizzare.

ES:→Quello indicato dalla freccia è l'allineamento minore.

Già con sequenze molto corte e senza infilare gap si ottengono 10 possibili allineamenti: il numero cresce molto velocemente.

In tutto abbiamo valutato 10 (5+5) allineamenti e abbiamo confronta