UNIVERSITA’ DI MILANO-BICOCCA
LAUREA MAGISTRALE IN
BIOINFORMATICA
Corso di
BIOINFORMATICA: TECNICHE DI BASE
Prof. Giancarlo Mauri
Lezione 9
Pattern discovery
Il problema
 Abbiamo un insieme di sequenze (DNA o proteine) non
allineate e funzionalmente correlate
 Sappiamo che:
 tutte le sequenze (o la maggior parte di esse)
contengono regioni “simili” tra loro
 le regioni comuni potrebbero essere responsabili della
funzione delle sequenze
 Problema: esiste un metodo efficiente e affidabile per
trovare tali regioni?
2
Un problema più generale: confronto
di sequenze
 Obiettivo: individuare regioni simili all’interno di due o più
sequenze per scoprire
 origine evolutiva comune
 funzioni comuni
 Per le biosequenze (DNA, RNA e proteine), una forte
similarità di solito implica una significativa similarità
funzionale o strutturale
 Esempi:
 Similarità tra l’oncogene n-sys del virus del sarcoma delle
scimmie e il gene del fattore di crescita PDGF (Doolittle 83,
Waterfield, 83).
 Similarità tra i geni delle globine nell’uomo e nello scimpanzè
3
Quanto simili?
 Identiche
 Con nucleotidi diversi permessi in alcune posizioni
 Con mutazioni (in generale)
 Con inserzioni e/o delezioni
 Con alcune parti conservate separate da regioni casuali
 All of the above(??)
4
Mutazioni in posizione fissa
ttatcACAAAccaatggcgattccgaactttacc
gtacaactatcttAGAAAagcaaggattacttat
gggtgagtaATAAAtagtcgctaactactgaatc
gaccctggcaccccaacaAAAAAagaggaataca
ttatcACAAAccaatggcgattccga
gtacaactatcttAGAAAagcaaggattacttat
gggtgagtaATAAAtagtcgctaactactgaatc
ccccaacaAAAAAagaggaataca
Regione: AXAAA
5
Mutazioni
atattACAAAacctttgctctggtagaggttacg
ccccctggagcttaAAGAAcgtgatcggttcctt
ggggacccctgAAAATattatggcaagattgtga
aaacctgGAAAAagaccataaatggagccgttaa
gcccgactttccgttttcAAACAaggagttccct
atattACAAAaccttt
ccccctggagcttaAAGAAcgtgatcggttcctt
ggggacccctgAAAATattatggcaaga
aaacctgGAAAAagaccata
ttccgttttcAAACAaggagttccct
Regione: AAAAA
6
Gap
ccaaacAAAgcgAAAggtatcaaacacccggctt
agagcagcagtagtAAAtgAAAacgtcaggcaac
aacAAAggactAAActccgcatatgctctactac
cgaaatttctgagcttcctgAAAcAAAcctttat
caaacAAA---gcAAAggt
gagcagcagtagtAAA---tgAAAacgtcaggcaa
aacAAAggactAAAc
ttaatcctgAAAc----AAAcctttat
Regione: AAAX(1,5)AAA
7
Pattern Discovery
 Obiettivo:
 dato un insieme di sequenze (nucleotidi o proteine) trovare
tutti i pattern (anche detti segnali o motivi) che occorrono in
forma esatta o approssimata (con mutazioni, inserzioni o
delezioni) in tutte o in un numero significativo di esse
 Ricercare un singolo pattern esatto è facile (O(n)):
ACGAGCGAGCACGAAGCG
XXGXGXGAGCXXGAXGXG
8
Pattern Discovery approssimato
 Obiettivo: dato un insieme di sequenze (nucleotidi o proteine)
trovare tutti i pattern (anche detti segnali o motivi) che:
 occorrano, con un numero di mutazioni, inserzioni o delezioni
non superiore a un massimo assegnato, in ogni sequenza del
set; oppure:
 occorrano come sopra in forme non più distanti di un massimo
assegnato, secondo una assegnata misura di distanza; oppure:
 occorrano come sopra in un numero di sequenze
“sorprendentemente” elevato
 ma...
 non si sa quale pattern si deve cercare
9
Pattern Discovery approssimato
Problema 1
INPUT:
una sequenza S sull’alfabeto S, due valori e,q  N
OUTPUT:
tutti i pattern che occorrono in S
almeno q volte con
al più e mismatches
10
Pattern Discovery approssimato
Problema 2
INPUT:
un insieme S = {S1, …, Sk} di sequenze sull’alfabeto S,
due valori e, q N
OUTPUT:
tutti i pattern che occorrono in
almeno q elementi di S con
al più e mismatches
11
Pattern Discovery approssimato
Problema 3
INPUT:
una sequenza S definita sull’alfabeto S, due valori e, q
N ed una misura di distanza d
OUTPUT:
Misure di distanza:
tutti i pattern P che occorrono in S almeno q volte con
un forma P’ tale che- d(P,P’)
numero 
di e
mismatches (mutazioni)
- distanza di edit
- weight matrices (PAM,BLOSUM)
12
Metodi Pattern Driven
 La soluzione più semplice:
 Generare tutti i pattern fino ad una lunghezza massima m
 Cercare separatamente ogni pattern nelle sequenze
 Riportare il pattern più significativo sulla base di qualche
misura statistica
 La ricerca è più efficiente con l’aiuto di una struttura di
indicizzazione dei testi adatta
 Limite: ci sono 4m o 20m pattern candidati per ogni lunghezza m:
 m = 5 : 1024 pattern
 m = 10 : 1.048.576 pattern
 m = 15 : 1.073.741.824 pattern
13
Metodi Pattern Driven
 L’enumerazione di tutti i pattern possibili funziona solo per
lunghezze limitate e per DNA (l’alfabeto è più piccolo)
 Soluzioni possibili per accelerare la ricerca sono:
 Ridurre a priori il numero di pattern candidati (limitando la
ricerca a quelli che occorrono almeno una volta senza errori)
 Imporre restrizioni alle posizioni in cui possono verificarsi
mutazioni (ossia permettere errori solo in specifiche
posizioni)
 Se il pattern è contenuto nel set di candidati, questi metodi
garantiscono di trovarlo
14
Metodi Pattern Driven
 Funzionano bene nella pratica:
 con pattern corti (fino a 8-10 residui)
 se il pattern occorre esatto in almeno una sequenza
 se sono solo permesse mutazioni in posizione fissa (ad
esempio: ATXGGGXTCAXXG)
 Limite: deve essere predefinito un valore di errore
massimo (dipendente dalla dimensione del pattern)
15
Metodi Sequence Driven
 La maggior parte dei software usati si basano su
metodi sequence driven che:
 prendono tutti i pattern che occorrono nelle sequenze,
e cercano similarità tra di essi
 non necessitano di un limite superiore della lunghezza
del motivo e/o del numero di mutazioni
 non necessitano di una soglia di distanza:
semplicemente cercano il gruppo (o i gruppi) dei
pattern più simili (uno per ogni sequenza)
 Limite: il problema diventa anche più difficile di prima
16
Metodi Sequence Driven
Esempio: pattern di lunghezza m con al più d mutazioni
Grafo in cui:
- i nodi sono i pattern
- gli archi connettono
pattern entro una
distanza 2d (possono
essere istanze dello
stesso pattern)
ACAAA
GAAAA
GGATA
AAAAT
GAAAA
17
Metodi Sequence Driven
Equivalente a trovare una cricca massimale nel grafo...
…è NP-difficile!!!
18
Metodi Sequence Driven
 Miglioramenti: introdurre euristiche per ottenere una buona
(possibilmente la migliore) soluzione in un tempo accettabile,
senza verificare tutti i profili possibili
 La soluzione ottima non è più garantita
 I programmi più ampiamente utilizzati:
 CONSENSUS (greedy)
 Gibbs Sampler (probabilistico)
 MEME (machine learning)
sono sequence driven. Ognuno è basato su un’euristica diversa
19
Metodi Sequence Driven
 Pregi:
 Non si deve imporre nessun limite alla lunghezza della
regione comune
 Non si deve definire esplicitamente un limite superiore
all’errore
 Una soluzione viene sempre trovata
 Difetti:
 Non garantiscono di trovare la soluzione migliore
 La dimensione della regione deve sempre essere
“suggerita” all’algoritmo
20
Metodi Sequence Driven
 La sequenza può essere vista come generata da due
diverse sorgenti:
 una che genera nucleotidi appartenenti a rumore di
fondo casuale (random background noise)
 una che genera il motivo
 Soluzione: provare a stimare i parametri della
sorgente che genera il motivo
 Più il motivo differisce dal rumore di fondo, più ci si
aspetta che sia significativo
21
Metodi Sequence Driven
 Computano la frequenza di ogni nucleotide nelle
sequenze (pi)
 Tentano di costruire un profilo della sorgente del
pattern con una matrice di frequenze
 Trovano la matrice le cui frequenze differiscono
maggiormente dalle frequenze di background
 Più il segnale è vicino alla distribuzione del rumore di
fondo, più è arduo rilevarlo con metodi sequence
driven
22
Profili
atattACAAAaccttt
ccccctggagcttaAAGAAcgtgatcggttcctt
ggggacccctgAAAATattatggcaaga
aaacctgGAAAAagaccata
ttccgttttcAAACAaggagttccct
A
C
G
T
|
|
|
|
1
2
3
4
5
----------------4
4
4
4
4
0
1
0
1
0
1
0
1
0
0
0
0
0
0
1
A
C
G
T
|
|
|
|
1
2
3
4
5
------------------0.8 0.8 0.8 0.8 0.8
0.0 0.2 0.0 0.2 0.0
0.2 0.0 0.2 0.0 0.0
0.0 0.0 0.0 0.0 0.2
23
Scoring Patterns (SD)
 Il solo conteggio del numero di occorrenze di un
pattern può non essere sufficiente
 Obiettivo: associare ad ogni pattern (o profilo) un
punteggio statistico, tentando di riflettere il più
possibile la sua rilevanza biologica
 Riporta dunque i pattern con score più elevato
 Pattern driven: computa il numero di occorrenze di un
pattern e lo compara con qualche valore atteso:
S(p) = Obs(p)/Exp(p)
24
Scoring Patterns (SD)
 I metodi SD classificano la matrice di frequenza
secondo il suo contenuto di informazione (o entropia
relativa):
I   j 1 i 1 f i , j log
m
4
fi, j
Pri
 Minimo quando fi,j = Pri
 Massimo quando il nucleotide meno probabile occorre
esclusivamente
25
Consensus (1990)
 Prende un pattern dalla prima sequenza, uno dalla
seconda e costruisce la matrice delle frequenze
 Ripete per ogni coppia di pattern
 Salva la matrice migliore
A
C
G
T
1
2
0
0
0
2
1
1
0
0
3
1
0
1
0
4
2
0
0
0
5
2
0
0
0
26
Consensus (1990)
 Ripete per k volte, aggiungendo ad ogni passo i pattern
di una nuova sequenza e salvando le più elevate matrici
di scoring
 Alla fine, stampa in output le matrici “migliori”, che
corrisponderanno alle occorrenze del motivo (uno per
ogni sequenza)
 L’algoritmo è greedy: nessuna garanzia che le matrici
finali siano le migliori possibili
27
Gibbs Sampler (1993)
 Sceglie a caso un pattern da ogni sequenza
 Costruisce la matrice delle frequenze
 Scarta il pattern appartenente ad una sequenza (S’)
 Per ogni pattern di S’ calcola la verosimiglianza (likelihood) che
venga generato dalla sorgente del motivo rispetto alla sorgente di
background:
L(Pi) = M(Pi)/B(Pi)
 Assegna ad ogni posizione i di S’ una probabilità proporzionale a
L(Pi) e sceglie uno nuovo pattern da S’
28
Gibbs Sampler (1993)
 Si ferma dopo un dato numero di iterazioni, o quando
gli score della matrice sono stabili
 Riporta i profili migliori
 Necessita di un elevato (>10) numero di sequenze in
input
 Una soluzione candidata (profilo) potrebbe essere
rimpiazzata da una peggiore
 Deve essere eseguito più di una volta
29
Gibbs Sampler (1993)
1-1
2-1
3-1
4-1
5-1
6-1
7-1
8-1
9-1
10-1
11-1
12-1
13-1
14-1
15-1
sites:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
c
aa
gtg
agcg
gttgg
ctcgac
tgctacg
tcaaaaga
agacaaacc
atgacgaaat
gaacaaaact
aactacggct
tacagacgat
gttcaggcta
AATGCTCAGC
AATCGTCAGC
AATCCCCAGC
AATGCTCAGC
ATTCCTCAGC
GATCCTCAGC
AATCCTCAGG
AATCCTCAGT
AATCCTCCGC
AATTCTCAGC
AATCCTCTGC
AATCCTCACC
AATCCTCATC
AATCCTTAGC
AATCCCCAGC
**********
cataccaata
cagagctgtg
gaataacgcg
cagttaatgg
tgtcgggtag
ataaaaaaaa
agacgactta
atcttattca
aaatggttac
agaatgaagt
agacctggtc
tagcttgagg
tcctgggaag
agcccgctac
ggcacggtct
30
Gibbs Sampler (1993)
Motif model (residue frequency x 100):
POS
1
2
3
4
5
6
7
8
9
10
A
87
87
.
.
.
.
.
81
.
.
C G T
. . .
. . .
. . 93
75 . .
87 . .
. . 81
87 . .
. . .
. 81 .
81 . .
Info
1.2
1.2
1.5
0.9
1.3
1.1
1.3
1.0
1.0
1.1
31
Limiti di performance
Falliscono tutti sul seguente benchmark (Pevzner 2000):
Trovare un segnale lungo 15 nucleotidi che appare con
esattamente 4 mutazioni in un campione di 20 sequenze,
ognuna lunga 600 nucleotidi
In generale, Pevzner ha evidenziato i seguenti valori
limite per lunghezza pattern/numero di mismatches per
insiemi di venti sequenze di lunghezza 600
10
12
13
15
16
18
19
1
2
3
3
4
5
5
20
6
32
Segnale (15,4)
AGGAAGCCGAGCGAT
gctgtcgcacAGGAATCCGACGGACaatggcagctggggttaaagcatg
tcctgaaaagAGGAAGCCATATGATgggctttactacaccgagagaggt
gtttcaggtgTGAAAGCCGGGGGATacggcagcggaattgaataacggt
gagtgtcggtTGGATACCGATCGATtaaacgtcgcggtacaagtatcat
actcacgggaAGGAAGCCACGAGCTcacacataccactacctaagtcaa
ctccaagtatAATAAGCCGAGCGTCgcaagaggcttctatctacaattt
aaacacaaacAGTTGGCCGAGCGACttatgtgacgtacactccttattg
ataggtcataAAGAATCCGAGACATgacctcaacgattggcacacaagg
cgaggtcaccAAGAAGGCGAAAGATccaagggtataagtcaaggagtta
ggcaacggaaCGGATGCCGAGATATatgaacgccaggtgggaaggttcc
aggcctccggAGTAATTCTAGCGATctgtaacacctcggacgcaacgcc
tcttttattaAGTAAGCCCCGCGTTcgtggttacgtgggtgggcggaca
atgccaagtaACTAAGCTGAGCGACcgaagagtagactgcggagactgt
gactcgtcgcCCGAAGGTGAGCGATtatctgaattacacatctccatcg
tcgtgtccgaACGAAGCCGAATTATgtcgaatggacgaatggtagggca
ccctgtgcgcAGGAAGGCGACCGTCagggagtgccattagtttacgacg
ttatattccaAGGAAGTGGAACTATgcgtcacaagcggaggtaaaggca
ttgggaaggtATGAAGCAGCCCGATgggctccatggcacgtccttccga
tacctcccctGGGAAGCTGAACGAGagctttaaccctataaccagagca
ggggtcgatgTGGAAGCCCGTCGATgggtcgcgactcgggacgtgcgat
33
Le ricerche più recenti
 La ricerca recente si è focalizzata sul problema del motivo (l,e)
per il DNA: trovare tutti i pattern di lunghezza l che occorrono
con al più e mutazioni in un insieme di sequenze
 Il problema è stato “probabilmente” risolto in modo adeguato
 Più alta è la probabilità di successo desiderata, più tempo
richiede il programma
 Alcuni programmi:
 SP-Star
 Projection
 Weeder
34
SP-Star (2000)
 Per tutti i pattern p che occorrono esattamente nelle
sequenze, si trova la migliore istanza pi in ogni sequenza
i
 Si selezionano i pattern che minimizzano:
d( p
i
, pj)
i, j
 Si raffinano i pattern trovati costruendo una stringa
di consensus
35
Projection (2001)
 Idea: proiettare un pattern di m caratteri in un
sottospazio a k dimensioni, con k<l-d:
ACGAGGTCG
A
AG T G
 Alcune occorrenze del motivo saranno proiettate nello
stesso sub-pattern
 Le posizioni da rimuovere sono scelte a caso ad ogni passo
 Il raffinamento del pattern avviene con un profilo
36
Weeder (2001)
 Idea: invece di ridurre il set di pattern candidati,
ridurre il set di possibili match per ogni pattern,
tentando di risparmiare un numero significativo di
occorrenze valide
 Invece di effettuare una ricerca esaustiva dei
patterns che occorrono in ogni sequenza, si cercano
pattern che occorrono in un loro sottoinsieme
 L’algoritmo ha bisogno in input solo di un prefissato
rapporto di errore 
37
Weeder (2001)
 Input: un insieme di sequenze e un rapporto di errore 
 Output: tutti i pattern che occorrono in almeno q sequenze con al
più m mutazioni
 Le mutazioni non possono essere concentrate all’inizio del pattern
38
Weeder (2001)
 Dato un pattern P = p1p2....pm, l’algoritmo può trovare
tutte le occorrenze valide di P (con al più |P|
mutazioni), tale che al più i mutazioni occorrono nei
primi i caratteri del pattern
 Ma: alcune occorrenze del pattern possono venire
dimenticate completamente
 I segnali di DNA sono sempre così “puliti” da mostrarsi
decomposti in blocchi?
 La risposta è no, ma si può usare Weeder con buon
senso
39
Uso di Weeder
 Esempio: pattern (15,4) che occorre in 20 sequenze i.i.d.
 Possibili occorrenze valide (decomposte in blocchi): 829
 Possibili occorrenze totali: 1365
 Probabilità di “centrare” un’occorrenza possibile in una sequenza:
phit = .61
 Probabilita di trovare il pattern in ogni sequenza: come tentare di
vincere all’Enalotto!
 Se si cercano pattern che occorrono in almeno 10 sequenze, la
probabilità di vedere il pattern almeno 10 volte è:
Phit(20,10) = .89
40
Uso di Weeder
 Si può usare Weeder come setaccio, per filtrare il set
di pattern candidati
 Tutti i pattern trovati da Weeder in almeno q
sequenze possono essere ricercati nuovamente nelle
sequenze, questa volta senza restrizione sulla
posizione dei mismatch
 Ci si aspetta che il numero dei pattern (pattern casuali
diversi dal segnale reale) passati alla seconda fase sia
molto più piccolo di quello originale (e non più
esponenziale)
41
Uso di Weeder
 La probabilità di trovare un pattern in una sequenza
dipende dalla sua lunghezza e dal rapporto di errore
 La probabilità di trovare un pattern in un insieme di
sequenze (e in questo modo la scelta del quorum q per
la prima fase) dipende dal numero di sequenze
 Lo stesso approccio può essere applicato quando il
segnale non compare in ogni sequenza
42
Uso di Weeder
 Quando ci si aspetta che il segnale da trovare sia
corto, l’algoritmo può essere usato in exact mode
 Per segnale più lungo, più è basso il quorum q, più sarà
alta la probabilità di trovare il segnale
 Ma: anche il numero di pattern che soddisfano i vincoli
di input è più elevato, e il programma è più lento
 L’utente può scegliere un opportuno trade-off tra
tempo e accuratezza
43
Complessità teorica in tempo
 Approccio naïve
 O(4men)
 Approccio con suffix tree (Sagot, 1998)
 O(4emekn) con n dimensione dell’input, m lunghezza del
pattern ed e numero di mutazioni permesse
 Weeder
 O((1/)e4ekn) con e numero di mutazioni che occorrono
nel più lungo pattern trovato
44
Conclusioni
 Metodi esaustivi
 Adatti per pattern corti e analisi di dati once-for-all
(ad esempio per interi genomi)
 Metodi Sequence Driven
 Danno risposte più veloci ma meno accurate
 Per dati di dimensione limitata
 E’ possibile scegliere un trade-off tra tempo e
accuratezza
45
Cosa troviamo sicuramente
 Pattern corti
 Pattern che occorrono esatti almeno una volta
 Pattern composti da posizioni conservate e quelli
wildcard (senza limiti di lunghezza, eccetto...)
 DNA pattern con mutazioni (probabilmente! Ma si deve
sapere quante mutazioni sono permesse)
 Per il resto..... good luck!
46