Fragment Assembly of DNA
Esempi, modelli e
soluzioni
I.Arduini, G.Caravagna, M.Pavesi
Indice
Storia
 Problema ed esempi
 Modelli
 Algoritmi
 Euristiche
 Assemblatori in pratica

Le tappe
Phage Phi-x174: 5kb, 1977
 Bacteriophage lambda: 50kb, 1982
 Haemophilius influenzae: 1.9Mb,
1995
 Drosophila: 180Mb, 2000
 Human: 3B, 2001

La storia

Tappe dello shotgun sequencing

80’s
• Si sequenziavano 5/10 kbp

<90
• Si sequenziavano circa 40 kbp

1995 (H. influenzae)
• Si supera il limite massimo supposto di 50 kbp
• Primo programma efficiente
La storia (I)

Opinioni di G.Myers
“I risultati del 1995 hanno ispirato me e
J.Webber a proporre l’uso dello shotgun
sequencing per sequenziare il genoma
umano”
 US National Institutes of Health non li
finanzia

• Maggio 1998: nasce Celera
La storia (II)

Celera

Obiettivi
• 1999: Drosophila
• 2001: Genoma umano
• Costi
• $ 0.01 per ogni base
• $ 130M per ogni anno di lavoro (≈3)
• $ 90M per software ed hardware
La storia (III)
• 26 Giugno 2000
• Celera Genomics annuncia il completamento
del primo assembly del genoma umano
• HGSC annuncia di aver completato una prima
bozza dello stesso progetto
La storia (IV)
• Febbraio 2001
• I due team pubblicano contemporaneamente
le loro analisi
• comprovare i loro risultati
• ridurre le critiche
• dimostrare uno scopo comune
Celera v.s. HGP
Il problema
Sequenziare lunghi filamenti di DNA
1. Problema biologico
2. Problema informatico
Il problema biologico
Incapacità tecnica delle macchine
 Frammentazione dei filamenti



Shotgun
Sequencing dei frammenti

Gel elettroforesi
Limiti tecnologici
• Metodi Gilbert-Sanger
• 500
1000 basi
• G.H. ≈ 3B di basi
ABI PRISM® 3100
Genetic Analyzer
Frammentazione

Clonazione


Virus
Shotgun

Enzima
Gel Elettroforesi
Tecnica che permette di separare frammenti
di acido nucleico, in funzione del peso
molecolare.
Il problema informatico

500-2000 frammenti di lunghezza
tra le 200 e le 700 basi.

Riassemblare i frammenti
Riassemblare i frammenti

Esempi
Caso ideale
 Complicazioni

Modelli
 Algoritmi
 Approccio pratico

Caso ideale - frammenti
A C C G T
C G T G C
T T A C
T A C C G T
Caso ideale - overlap
A C C G T
C G T G C
T T A C
T A C C G T
Caso ideale – allineamento
- - A C C G T - -
- - - - C G T G C
T T A C - - - - - T A C C G T - -
T T A C C G T G C
Complicazioni (caso reale)

Errori






Base call errors (BCE)
Contaminazione
Chimere
Orientamento sconosciuto
Mancanza di copertura
Ripetizioni


Dirette
Inverse
BCE - frammenti

Errore di lettura (biologico)
A C C G T
C G T G C
T T A C
T G C C G T
BCE - overlap

Errore di lettura (biologico)
A C C G T
C G T G C
T T A C
T G C C G T
BCE - layout
- - A C C G T - -
- - - - C G T G C
T T A C - - - - - T G C C G T - -
T T ? C C G T G C
BCE - soluzione
A
-
Selezione per
maggioranza
•2A
A
•1G
•1–
G
?
Vince la A !!!
BCE – stringa di consenso
- - A C C G T - -
- - - - C G T G C
T T A C - - - - - T G C C G T - -
T T A C C G T G C
Chimere

Fusione di due sottosequenze non
contigue in un unico frammento
DNA
frammento
Chimere

Problema biologico

Durante la clonazione
• Contaminazione dall’ospite
• DNA Arrays

Soluzione

Preprocessing dell’input
Chimere - frammenti
A C C G T
C G T G C
T A C C G T
T T A T G C
Chimere - overlap
A C C G T
C G T G C
T A C C G T
T T A T G C
TTATGC
TTA
TGC
Chimere – consenso
- - A C C G T - -
- - - - C G T G C
T T A - - - - - -
T T A C C G T G C
T T A - - - T G C
Contaminazioni

Le chimere sono
contaminazioni


Il processo di
clonazione “sporca”
i filamenti con
pezzi di genoma
dell’organismo
ospite
DNA da clonare e dell’ospite
Processo di
clonazione
Unica soluzione il
preprocessing
DNA “sporco” e quello originale
Orientamento Sconosciuto
I frammenti clonati provengono da
una qualsiasi delle sequenze
 In principio non sappiamo da quale
 Con n frammenti abbiamo 2n(n-1)
coppie considerando le 2 eliche

ACTG
reverse
GTCA
complement
CAGT
Orientamento - frammenti
C A C G T
A C T A C G
G T A C T
Orientamento – quale elica?
C A C G T
A C G T G
A C T A C G
C G T A G T
G T A C T
A G T A C
1. genero tutti i possibili frammenti
2. ne scelgo alcuni (come?)
Orientamento – layout
Ori.
C A C G T - - - - - - C G T A G T - -
- - - - - A G T A C
C A C G T A G T A C
Copertura

La stringa target si riassembla da
dei frammenti
1. Quanti frammenti vogliamo?
• abbastanza
2. Quanti sono abbastanza?
• non lo sappiamo (non calcolabile)
3. Possono non bastare?
• sì
?
Copertura

Problema biologico

Il sampling è un processo casuale
Buon Principio
Più frammenti abbiamo, più è sicuro il
consenso basato sulla maggioranza

quindi
Quanti: tanti
 Quali: non si sa

Ripetizioni

Sequenze che compaiono 2 o più
volte nella sequenza target
x
x
DNA

Dato un frammento contenente x, in
quale punto del target lo assemblo?

sono sempre “pericolose” ?
Ripetizioni – quelle facili

Quelle facili
x
x
DNA
frammenti

I segmenti
e
disambiguano

Facili quando sono contenute
totalmente nei frammenti
Ripetizioni – quelle difficili

Quelle difficili
x
x
DNA
frammenti
NO
OK
i frammenti collassano !

Difficili se si spezza una ripetizione
Ripetizioni difficili – XXX
frammenti
A
x
B
x
C
x
D
DNA
frammenti
A
x
C
x
B
x
D
consenso
Ripetizioni difficili – XYXY
frammenti
A
x
B
y
C
x
D
y
E
DNA
frammenti
A
x
D
y
C
x
B
y
E
consenso
Ripetizioni – dirette/inverse

Abbiamo visto quelle dirette
Facili
 Difficili

Ce ne sono altre?

x
Quelle inverse
Facili
 Difficili
x
Ruota 180°

x
x
Modelli
SCS (Shortest Common Superstring)
 RECONSTRUCTION
 MULTICONTIG


Nessuno risolve i problemi biologici
Chimere
 Contaminazione

SCS

Il problema:
Data una collezione F di stringhe
 Trovare la più breve stringa S tale che
per ogni f appartanente ad F, S sia una
superstringa di f.

SCS (II)

In biologia:

La collezione F è l’insieme di frammenti
• orientati

S è la sequenza del DNA della molecola
target
SCS (III)

Limiti:

S deve essere una superstringa
perfetta
• Non tiene conto degli errori

Bisogna conoscere l’orientamento
• Quasi sempre impossibile

La superstringa trovata potrebbe non
essere la soluzione corretta
• Problema delle ripetizioni
SCS (IV)

In conclusione:
Il problema SCS è NP-hard
 Esistono algoritmi di approssimazione
 Non sono interessanti

• Limiti del modello
RECONSTRUCTION

Il problema:

Dati
• una collezione F di stringhe
• Un margine di errore ε, 0<ε<1

Trovare la più breve stringa S tale che
per ogni f appartanente ad F, sia
• Min(ds(f,S),ds(-f,S))<= ε|f|
RECONSTRUCTION (II)

Min(ds(f,S),ds(-f,S))<= ε|f|

ds è la substring edit distance
• Edit distance ignorando cancellazioni alle estremità
della seconda sequenza.
• ds(a,b)= min d(a,s)
• Dove s è una qualsiasi sottostringa di b

ε è il livello di errore tollerato
|f| è la lunghezza della stringa f

Cosa significa tutto questo?

RECONSTRUCTION (III)

Cosa significa tutto questo?

Errore tollerato ε per ogni base.
• ε=0.05 significa che sono ammessi 5 errori
ogni 100 basi.

Cerco una stringa S
• di dimensioni minime
• ogni frammento (o inverso) è sottostringa
di S con margine ε.
RECONSTRUCTION (IV)

Vantaggi:


Tiene conto degli errori
Svantaggi:
Non risolve il problema delle chimere
 Il problema è ancora NP-hard

• Contiene SCS come caso particolare con
ε =0
MULTICONTIG

Introduce il concetto di good linkage
Def: good linkage
Misura del livello di sovrapposizione
di frammenti
--TAATG
TGTAA--
Livello di collegamento: 3
MULTICONTIG (PRO)

PRO
Errori (Base Call Errors)
 Orientamento
 Mancanza di copertura


Ripetizioni?
MULTICONTIG (CONTRO)

CONTRO


Non sfrutta le informazioni relative alla
dimensione della molecola target
NP-hard
• Cammini Hamiltoniani

Ripetizioni?
MULTICONTIG (Def. I)
F : collezione di frammenti
 L : allineamento multiplo dei
frammenti (Layout)

T G T A A - - - - - - T A A T G - - -
- - - - - - G T A C
MULTICONTIG (Def. II)
Numerazione delle colonne
 Per ogni frammento f si l(f) e r(f)
 Il valore di l e r dipende dalla
colonna

l(f1)=1
r(f1)=1
1 2 3 4 5 6 7 8 9 10
f1
T G T A A - - - - - - T A A T G - - - - - - - - G T A C
MULTICONTIG (Def. III)
|f|=r(f) - l(f) + 1
 Overlap [x..y]:

intersezione [l(f)..r(f)] e [l(g)..r(g)]
 Nonlink: se un altro frammento
contiene propriamente [x..y]
 Link: altrimenti


Weakest link: la più piccola
dimensione dei link della collezione
MULTICONTIG (VII)

T-contig


Un layout L è un t-contig se il suo
weakest link ha dimensione t
Una collezione F ammette t-contig se è
possibile costruire un t-contig con i suoi
frammenti
MULTICONTIG
(formulazione error-free)
PROBLEMA: Multicontig
 INPUT

F, collezione di stringhe
 t≥0, intero


OUTPUT

Una partizione di F nel minimo numero
di sottocollezioni Ci , 1≤i≤k, tale che
ogni Ci ammetta un t-contig
MULTICONTIG (esempio)


F={GTAC,TAATG,TGTAA}
t=3
T G T A A - -
G T A C
- - T A A T G

t=2
- - - T G T A A
T A A T G - - -

t=1
T G T A A - - - - - - T A A T G - - - - - - - - G T A C
G T A C
MULTICONTIG (errori)




Si associa a L una sequenza di consenso
S
Immagine di f nel consenso: S[l(f)..r(f)]
Tolleranza di errore: e
e-consenso: S è un e consenso per
questo contig quando la distanza di edit
fra ciascuno frammento allineato f e la
sua immagine nel consenso è al più e|f|.
MULTICONTIG
(formulazione)


PROBLEMA: Multicontig
INPUT




F, collezione di stringhe
t≥0, intero
0≤e≤1, tolleranza di errore
OUTPUT

Una partizione di F nel minimo numero di
sottocollezioni Ci , 1≤i≤k, tale che ogni Ci
ammetta un t-contig con un e-consenso
MULTICONTIG
(complessità)

Np-arduo

Anche nel caso error-free e
orientamento noto

Contiene una istanza di cammino
hamiltoniano
Indice Algoritmi

Rappresentare gli Overlap


Overlap Multigraph
Superstringhe e cammini

SCS come cammini su grafi
Algoritmo Greedy
 Sottografi aciclici

Rappresentare gli
Overlap(I)

Dati due frammenti



f1= TACGAA
f2= AACA
Quanti modi ci sono di sovrapporli?
• t=2
TACG AA
AA CA
t
f1
t
• t=1
TACGA A
A ACA
• t=0
TACGAA
t
AACA
f2
Ordinamento
f
su un grafo
f2 f f1
Rappresentare gli
Overlap(II)


F={TACGA, ACCC, CTAAAG, GACA}
Grafo

Escludendo da subito le sovrapposizioni nulle
(concatenazioni di frammenti)
TACGA
ACCC
CTAAAG
GACA
Rappresentare gli
Overlap(III)
TACGA
ACCC
CTAAAG
GACA
TACGA
ACCC
ACCC
GACA
CTAAAG
ACCC
Overlap Multigraph (I)
OM(F)=(F,A)
 I nodi rappresentano i frammenti
 (a,b), con peso t≥0  A  suffix(a,
t) = prefix(b, t)

t
prefix(b,t)
a
b
a
t
b
suffix(a,t)
t=2
a
TAGC AA
AA GC
TAGCAA
b
2
AAGC
Overlap Multigraph (II)

Raffinamenti possibili:
Elevato numero di nodi n
 Elevato numero di archi

• n2 solo per t=0

Valore di soglia su t
• Eliminare gli overlap “troppo deboli”
• Poco significativi
• Errori?
Superstringhe e cammini

I cammini in un OM rappresentano
un allineamento multiplo.

La sequenza di consenso è una
superstringa comune ai frammenti
del cammino

Non necessariamente la più corta.
Superstringhe e
cammini(II)

Cammini come sequenze di archi

Più di un arco tra due nodi
TACG AA
AA CA
t
TACGA A
A ACA
2
t
TAGCAA
1
AAGC
0
TACGAA
t
AACA
n overlap tra due frammenti
generano n cammini fra due
nodi
Superstringhe e
cammini(III)

Overlap multigraph

Quanti cammini?
ACCC
1
TACGA
2
1
1
CTAAAG
1
GACA
Superstringhe e
cammini(III)
ACCC
1
TACGA
2
1
1
CTAAAG
1
TACGA--------------ACCC--------------CTAAAG--------------GACA
TACGACCCTAAAGACA
GACA
Superstringhe e
cammini(III)
ACCC
1
TACGA
2
1
1
CTAAAG
1
TACGA------------GACA-------------ACCC-------------CTAAAG
TACGACACCCTAAAG
GACA
consenso
più corto
Considerazioni (I)

Come scegliere un cammino?

Due modi:
Senza regole
Massimizzo S pesi
CS-Problem
SCS-Problem
Common Superstring
Shortest Common
Superstring
Considerazioni (II)

Ma in fondo, quali cammini
vogliamo?

Hamiltonian Path (HAM)
HAM
Un cammino in un grafo non orientato
che visita tutti i vertici una e una sola
volta
HAM NP-C
Overlap Graph (OG)
Vogliamo cammini di peso massimo
 Eliminiamo


Tra archi paralleli quelli meno pesanti
2
TAGCAA
1
AAGC
0
TAGCAA
2
AAGC
L’Algoritmo

Un tentativo “greedy” per calcolare

Cammino di peso massimo sull’ OG
IDEA
Scegliere, al passo i-esimo, l’arco di peso massimo
tra quelli non ancora attraversati.
Questo arco non deve interferire con il cammino
HAM che stavamo costruendo al passo (i-1)-esimo
Ordinamento decrescente degli archi rispetto ai pesi
L’Algoritmo: terminazione

OG è completo

Tra due nodi esiste sempre un arco
Se |F| = n , allora ci fermiamo quando il cammino
è lungo (n-1) nodi.
Il cammino calcolato toccherà tutti i nodi del grafo.
L’Algoritmo: variazioni

Vediamo l’algoritmo direttamente su F
1.
Scegli ( f, g ) F di peso massimo
2.
Sovrapponi f a g secondo l’overlap
3.
Togli f e g da F
4.
Aggiungi la sovrapposizione a F
Ci fermiamo quando |F| = 1
• Otteniamo sempre il miglior risultato?
Un esempio
F = {GCC,ATGC,TGCAT}
GCC
Passo
Peso
F
1 3 {GCC,ATGCAT}
2
2 0 {ATGCATGCC}
2
ATGC
TGCAT
GCC
3
0
ATGCAT
ATGCATGCC
Un esempio(II)

Un cammino alternativo migliore
GCC
2
2
0
2
ATGC
2
TGCAT
3
3
ATGCATGCC v.s. TCGCATGCC
SOTTOGRAFI ACICLICI
Basato sul modello Multicontig
 Buon Campionamento

I frammenti coprono l’intera molecola
 Le connessioni fra frammenti sono
sufficienti

Campionamento

S={A,C,G,T}*

Campionamento di S


Collezione A di intervalli di S
A copre S

Se per ogni 1 ≤ i ≤|S| abbiamo almeno un
intervallo [j..k]є A t.c. i є [j..k]
Connessione

Due intervalli a e b sono connessi a
livello t


se |a∩b|≥t
Un campionamento di A è connessa
a livello t

Se per ogni coppia a e b є A esiste una
serie di intervalli ai con 0≤i≤l t.c. a=a0,
b=al e ai è connessa a livello t con ai+1
per 0≤i≤l-1
Copertura: esempio

Campionamento di A connesso a
livello t
È
sufficiente che ogni coppia di intervalli abbia una catena
di intervalli l’uno con l’altro sovrapposto a livello t
G C C
C C A T G
T G A G
A G T G
GCC
e AGTG non sono connessi a livello 2, ma il
campionamento è comunque connesso a livello 2
Buon campionamento

Un campionamento è buono se A è
connesso ad un livello t’ prefissato


t’ è 10, tipicamente.
Studieremo quindi collezioni di frammenti
connessi a livello t che coprono una
stringa S
Modifica al grafo

Si tagliano da OM(F) tutti gli archi da
f a g che pesino meno di t


Gli archi connettono solo nodi
corrispondenti a intervalli connessi a
livello t
Si indica con OM(F,t)
Concettualmente

Nel grafo
gli archi sono le sovrapposizioni
 I nodi sono intervalli


Stringa cercata = cammino che non
visiti due volte un nodo e visiti tutti i
nodi


Cammino Hamiltoniano
Esiste?
Cammini Hamiltoniani

Si può dimostrare che, dati



Allora il multigrafo OM(F,t)



Una stringa S sull’alfabeto {A,C,G,T}
Una collezione A connessa a livello t,
campionamento di S.
Con F generato da A
Ammette un cammino Hamiltoniano P.
Se A copre S, allora P può essere scelto
tale che S(P)=S.
Intuitivamente
Condizioni sufficienti per la presenza
di un cammino hamiltoniano
 Il cammino hamiltoniano
rappresenta una stringa



ci si muove su frammenti sovrapposti,
ovvero susseguenti
In assenza di cicli, questo cammino
si dimostra essere unico
Problema

Abbiamo F, vogliamo ricostruire S
Trovando un cammino hamiltoniano
 Possiamo farlo?


Il problema sono le ripetizioni
Sì, in assenza di ripetizioni
 Non si sa, altrimenti

Presenza di ripetizioni



Cicli nel grafo => ripetizioni nel grafo
 Il contrario non sempre è vero
Intersezione comune fra due intervalli è
dovuta a uno fra
 Sovrapposizione (overlap)
 Ripetizione
Si dimostra che in caso di ciclo nel grafo,
esisten almeno una ripetizione
Unicità del cammino
hamiltoniano

Trasformare il multigrafo OM in un
grafo aciclico OG


Se S non ha riptezioni, il cammino
hamiltoniano su OG esiste ed è unico
Il cammino hamiltoniano rappresenta
la stringa target ricercata
Topological sorting
Questo approccio è noto come
Topological Sorting
 Trovare un ordinamento di nodi
consistente con un insieme aciclico di
archi


In cui gli archi rappresentino un
ordinamento
Greedy VS Acyclic Subgraph
S=AGTATTGGCAATCGATGCAAACCTTT
TGGCAATCACT
 w=AGTATTGGCAATC
 z=AATCGATG
 u=ATGCAAACCT
 x=CCTTTTGG
 y=TTGGCAATCACT

Greedy VS Acyclic Subgraph
Greedy:
w, y, z, u, x
9
4
w
z
3
3
3
u
x
y
Sottografi aciclici:
w, z, u, x, y
Greedy VS Acyclic Subgraph

Greedy
Lunghezza 36
 Weakest Link 0
 Superstringa


Sottografi aciclici
Lunghezza 37
 Weakest Link 3
 Superstinga

Vince Acyclic Subgraph

Fra i due, prevale la logica del
migliore livello di sovrapposizione

Anche se la superstringa minore è quella
generalmente preferibile
Euristiche
Nessun formalismo è adeguato
 Ci buttiamo sulle euristiche


Quanto è adeguato un allineamento?
• Scoring
• Coverage
• Linkage

Assembly in pratica
Scoring

Situazione ideale:
In ogni colonna, un solo carattere
 Uniformità: bene
 Variabilità: male

Scoring: entropia

Entropia:

Definita su frequenze relative
• Bassa  una frequenza “spicca” nel gruppo
• Alta  frequenze omogenee

Su una colonna:

4 A, 1 G
• Entropia bassa, si sceglie A

3 A, 2G
• Entropia alta, non si sa cosa scegliere
Scoring: in pratica

Allineamento buono

Entropia bassa
• Sappiamo cosa scegliere per ogni colonna
Coverage
Un frammento “copre” una colonna?
 Siano l(f) e r(f) gli estremi sinistro e
destro di f


f copre la colonna i se l(f)≤i≤r(f)
a=CAGTC--b=--GTCATc=----CAT-
a e b coprono la
colonna, c no
Coverage (II)

Coverage di una colonna:


Numero di frammenti che la coprono
Coverage=0 per una colonna

Layout disconnesso
CATAG-------------
---AGTCGA------------------CTAGACTA
Coverage=0 !
Coverage (III)

In conclusione:

Più colonne con coverage=0
• Qualsiasi permutazione delle regioni tra di
esse è accettabile.
• Regione=contig

Coverage alta = consensus affidabile
Linkage

Il modo in cui ogni frammento si
lega agli altri

Presenza di overlaps
------ACTTTT-----TCCGAG------ACGGAC
------ACTTTT------
TCCGAG------ACGGAC
Esempio di buona copertura
ma scarso linkage
Assembly in pratica

Un buon algoritmo deve:

bilanciare
• Scoring
• Coverage
• Linkage


trovare tutte le soluzioni buone
Un compito difficile, quindi?
Assembly in pratica (II)

Un compito difficile

Si divide il problema in tre fasi:
• Trovare overlaps
• Costruire un layout
• Calcolare un consensus

Modello overlap-layout-consensus
Assembly in pratica (III)

Si divide il problema in tre fasi

Pro:


Più gestibile
Contro:

Difficile capire la relazione tra input e
output
Assembly in pratica (IV)

Di fatto

I metodi usati nelle tre fasi sono spesso
euristici
• Nessuna garanzia sulla qualità della
soluzione

Ci sono molte implementazioni
• Buone all’atto pratico
• Vale la pena studiare le tecniche
Trovare overlaps

Proviamo ogni coppia di frammenti
Anche i complementari inversi
 Con un margine di errore
 Algoritmo di programmazione dinamica

• Nessuna penalità per gaps alle estremità
• 1 match
• -1 mismatch
• -2 gaps
Costruire un layout

Trovare un buon ordinamento dei
frammenti in un contig.

Ogni frammento si sovrappone al
successivo
• Si trova il layout
Costruire un layout (II)

Non esiste un algoritmo
Semplice
 Generale
 Neanche affidandosi alle euristiche


Facciamo considerazioni pratiche

Da tenere a mente
Costruire un layout (III)

Considerazioni pratiche

Complementari inversi
• Espandere F con gli inversi
• Se due frammenti hanno overlap, anche i loro
inversi lo hanno

Errori
• Matching approssimato
Costruire un layout (IV)

Considerazioni pratiche

Trovare percorsi diretti sull’ OG
• Significa trovare ordinamenti
• Si costruisce contemporaneamente l’inverso
• Vengono costruiti entrambi i filamenti del DNA

Due ostacoli:
• Mancanza di coverage
• Ripetizioni
Costruire un layout (V)

Mancanza di copertura


Deriva da un grafo disconnesso
Ripetizioni

Causano cicli nel grafo
• Se la copertura è buona
Creano ambiguità
 Danno coverage stranamente alto

• Tutte le copie sono impilate insieme
• La coverage sale
Costruire un layout (VI)

Per concludere:
Percorsi complementari
 Ignorare frammenti contenuti
 Cicli indicano ripetizioni
 Coverage “strano”

• Può derivare da ripetizioni
Consensus

Abbiamo un ordinamento di
frammenti

Come li disponiamo?
• Banale nel caso ideale
• Problematico con overlaps approssimati
Consensus (II)

Abbiamo un ordinamento

fgh
• f = CATAGTC
• g = TAACTAT
• h = AGACTATCC
• Due allineamenti possibili tra f e g
CATAGTC---
CATAGTC---
--TAA-CTAT
--TA-ACTAT
Problema: stesso punteggio!
Consensus (III)

Due allineamenti possibili tra f e g


Con lo stesso punteggio
Quando entra in gioco h:
CATAGTC-----
CATAGTC-----
--TAA-CTAT--
--TA-ACTAT--
---AGACTATCC
---AGACTATCC
CATAG?CTATCC
CATAGACTATCC
Consensus (IV)

Evidenziamo le differenze tra
frammenti e consensus
CATAGTC-----
CATAGTC-----
--TAA-CTAT--
--TA-ACTAT--
---AGACTATCC
---AGACTATCC
CATAG?CTATCC
CATAGACTATCC
2 differenze
1 differenza
Consensus (V)

In pratica

Struttura dati che distingue
• Basi già “piazzate” da altri frammenti
• Basi con posizionamento “ambiguo”

Sequenza come lista di nodi (basi)
Consensus (VI)

Sequenza come lista di nodi (basi)
Assemblatori

Due generazioni

Prima (1992≈1998)
• CAP
• Phred & Phrap

Seconda(1995≈..)
• TIGR
• Celera
Assemblatori: prima
generazione

Contig Assembly Program (CAP) di
Xiaoqiu Huang, Genomics
Risolve SCS con programmazione
dinamica su coppie di frammenti
 Del 1992, migliorato in CAP2 nel 1996

“As to performance, CAP took 4 hours to assemble 1015
fragments of a total of 252,000 characters on a Sun
SPARCstation SLC”
http://www.cs.sunysb.edu/~algorith/implement/cap/implement.shtml
Assemblatori: prima
generazione

Phred Phrap di Phil Green,
Laboratory of Phil Green


Del 1998
Approccio


Controllo della qualità dei frammenti
Guidato da una euristica
Assemblatori: seconda
generazione

The Institute for Genomic Research
(TIGR)


Nel 1995 sequenzia H.influenzae (1.8Mb)
Approccio

Utilizzo di strutture dati sofisticate
• Unitigs (UNIquely Assemblable conTIG)
• Scaffold (unitigs contigui ed ordinati)
Assemblatori: seconda
generazione

Celera Genomics
Celera: pipeline

Screener



Cerca le ripetizioni conosciute in un database
Il database per la Drosophila era “fatto a mano”
Overlapper

Ogni frammento viene comparato con quelli
precedentemente esaminati
• Differenza < 6%
• Overlap più lunghi di 40 basi

L’approccio è quello di BLAST
Celera: pipeline

Unitigger
 Riunisce frammenti non ambigui in unitigs
• U-unitigs : quelli fuori dalle ripetizioni

Scaffolder

U-unitigs vengono raccolti in insiemi di contig di
dimensione nota orientati ed ordinati
Celera: pipeline

Repeat Resolution
 Elimina le ripetizioni note
 Aggiorna il database

Consensus
“La qualità della sequenza è così alta che il consenso
è ottenuto da un semplice algoritmo denominato
Abacus “
Myers et al
Osservazioni finali

Overlap Layout Consensu: le
tecniche più avanzate per la fase
Layout sono NP-hard
Ma il vero ostacolo è nella fase Overlap,
anche se quadratica
 3Miliardi di basi x 12 (copertura) x 2
(orientamento)

Osservazioni 2

Celera e HGSC hanno annunciato di
aver sequenziato del genoma umano

Come si fa a dare questa valutazione, se
non si può confrontare il risultato con il
“vero genoma”?
Metro di valutazione: lunghezza
 Siamo davvero simili al topo per il
99% del genoma?

Osservazioni 3
La soluzione del problema biologico è
stata favorita dall'Informatica
 Ma l'informatica ha fino ad ora fatto
uso dei PROPRI mezzi principalmente
 E' possibile sfruttare meglio i vincoli
biologici?


Uso di database come guida