Lezione 1 Assemblaggio dei genomi

Lezione 1
Assemblaggio dei genomi
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Genomica – Introduzione
Genoma: corredo dell'acido nucleico contenente l'informazione genetica di un organismo
Nucleare
Cromosomico
Genoma
Degli organelli
Extracromosomico
Individuali
Variazioni genomiche
In alcuni tipi cellulari
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Genomica – Introduzione
●
●
La Genomica è
strettamente legata a molte
altre discipline, ciascuna
delle quali impiega molte
metodologie computazionali
●
●
●
●
●
●
Lezione 1
GENOMA
Geni e sequenze reagolatorie
TRASCRITTOMA
RNA ed espressione genica
PROTEOMA
Proteine
METABOLOMA
Metaboliti e vie metaboliche
FARMACOGENOMA
Relazione tra genoma e risposta ai farmaci
INTERATTOMA
Insieme di interazioni fra proteine
EPIGENOMA
Modificazioni del genoma
REGOLOMA
Sequenze regolative e molecole regolatrici
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Genomica – Introduzione
Risposta all'ambiente
Evoluzione
Reti di regolazione
Caratteristiche
degli individui
Genomica
Computazionale
Espressione Genica
Proteomica
Identificazione di
nuove terapie
Insorgenza malattie
Risposta ai farmaci
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Genomica – Introduzione
●
●
●
●
Lezione 1
1953: F. Crick e J. Watson scoprono la struttura a doppia elica
del DNA
anni ’70: si sviluppano le tecniche per il sequenziamento di
spezzoni di DNA (F. Sanger)
anni ’80: viene lanciato il progetto genoma e partono le prime
sperimentazioni pilota (insieme alle prime compagnie per lo
sfruttamento commerciale di queste ricerche)
anni ’90: vengono sequenziati i primi organismi (qualche M di
paia di basi)
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Genomica – Introduzione
La Genomica e la Biologia Computazionale sono evolute insieme
Anni 70: i dati erano pochi e poco rappresentativi, ma gia i biologi iniziavano
ad applicare algoritmi per analizzare sequenze di proteine ed acidi nucleici;
Anni 80: vari studiosi iniziarono ad introdurre metodi presi in prestito da
informatica e statistica per analisi più sofisticate;
Anni 90: non appena i primi genomi iniziarono ad essere sequenziati, nasce
la genomica computazionale;
2000: i genomi completamente sequenziati sono numerosi, nuove tecnologie
promettono di ottenere valanghe di dati in tempi brevissimi, e la genomica
computazionale è ormai integrata nelle metodologie di analisi biologica e non
più applicata solo a posteriori.
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Genomica – Introduzione
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Genomica – Introduzione
Figure 7.14 Genomes 3 (© Garland Science 2007)
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Genomica – Introduzione
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Genomica – Introduzione
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Genomica – Introduzione
Organismo
Paia di basi
(aploide)
Numero
geni
Saccharomyces
cerevisiae
12,495,682
5,770
Lievito della birra
Cyanidioschyzon merolae
16,520,305
5,331
Alga rossa unicellulare
Plasmodium falciparum
22,853,764
5,268
Protozoo
Caenorhabditis elegans
100,258,171
19,427
Nematode
Arabidopsis thaliana
115,409,949
28,000
Angiosperma
Drosophila melanogaster
122,653,977
13,379
Moscerino della frutta
Anopheles gambiae
278,244,063
13,683
Zanzara
Mus musculus
2.6 x 109
22,000
Topo domestico
Homo sapiens
3.2 x 109
22,000
Uomo
Tetraodon nigroviridis
3.42 x 108
27,918
Pesce palla
Oryza sativa
3.9 x 108
37,544
Riso
Lezione 1
Descrizione
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
The Sanger chain-termination method
Molecole di DNA a singolo filamento
che differiscono anche solo di una
singola base in lunghezza possono
esere separate su gel di poliacrilamide
per elettroforesi
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
The Sanger chain-termination method
ddNucleotidi
●
●
Lezione 1
ddA, ddT, ddC, ddG
Quando incorporati nella
catena nascente di DNA
causano l'arresto della
replicazione.
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
The Sanger chain-termination method
Si parte da DNA a singolo strand
che si vuole sequenziare;
Si iniziano 4 reazioni di replicazione
separate;
Nella miscela di reazione sono
presenti i 4 nucleotidi standard e
sono aggiunti dideossinucleotidi
(ddNTPs) marcati che terminano
l'allungamento;
Dopo un numero sufficiente di cicli
ci saranno polimeri che terminano
ad ogni possibile posizione del
templato.
Separando per elettroforesi questi
polimeri
in
base
alla
loro
dimensione, si osserveranno una
serie di bande corrispondendti alla
sequenza del templato.
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
The Sanger chain-termination method
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
The Sanger chain-termination method
Elettroferogramma
Mentre i frammenti ottenuti dalla reazione di sequenziamento sono separati dal gel,
un laser legge la fluorescenza di ogni frammento e determina automaticamente la
sequenza. Ogni colore (blu, verde, rosso o giallo), oppure l'intensità della
fluorescenza, corrisponde ad un nucleotide diverso (ad esempio blu per le G, e cosi
via).
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
The Sanger chain-termination method
Sequenziatori:
- La separazione e' effettuata per
elettroforesi su capillare invece che su gel
- 1 corsa = 4 ore
- 1 corsa = 384 sequenze in parallelo
- più di 2000 sequenze al giorno
- ogni sequenza = 700 bp
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
The Sanger chain-termination method
Phred
PHRED: processing the
gel chromatographs (Phill
Green)
Generate sequence and
quality estimation
PHRED quality =
-10×log10Prob(Error)
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Strategie per il sequenziamento di genomi
Le tecniche di sequenziamento del DNA correnti sono in grado di determinare
accuratamente solo sequenze di 600-700 nucleotidi per volta.
Shotgun Sequencing (Fred Sanger 1982):
1. Frammentazione fisica del DNA
2. La sequenza dei frammenti (o di porzioni di essi) è letta
3. Assemblatori sono usati per ricostruire la sequenza originale
Problemi:
L' assemblaggio è difficile
Le sequenze possono contenere errori
Il DNA ripetitivo causa problemi di assemblaggio
Alcune regioni possono rimanere scoperte (gaps)
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2009/2010
2010/2011
Strategie per il sequenziamento di genomi
Coverage
(numero totale di basi sequenziate)/
(lunghezza della sequenza
assemblata)
31/13=2.3
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Strategie per il sequenziamento di genomi
Bottom-up
Lezione 1
Top-down
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Metodo top-down
Top-down (or hierarchical, or clone-based) shotgun sequencing
1. Il genoma è frammentato, e i frammenti sono clonati in un vettore adatto:
- YAC (yeast artificial chromosome)
- BAC (bacterial artificial chromosome)
2. I BAC o YAC sono replicati nelle cellule ospiti per produrre milioni di copie.
3. Questi cloni sono poi analizzati cercando dei marcatori specifici (STS, siti di
restrizione, etc.).
4. Marcatori condivisi da piu' cloni sono utilizzati per determinare l'ordine di questi cloni
sul cromosoma da cui originano (tiling path). Gruppi di cloni con regioni sovrapposte
sono chiamati contigs.
5. Un sottoinsieme di questi cloni e' scelto per massimizzare la copertura della
sequenza e al contempo minimizzare il numero di sequenze necessarie, e sottoposto
a sequenziamento shotgun.
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Metodo top-down
Top-down Method
~100mln bp
Libreria di YAC
(Yeast Artificial
Chromosome)
YACs
~1mln bp
~40k bp
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Strategie per il sequenziamento di genomi
Top-down Method
~40k bp
Sequenziamento
shotgun
Lezione 1
Libreria di BAC
(Bacterial
Artificial
Chromosome)
Vettore virale,
Plasmide
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Metodo top-down
Un clone in un BAC
genoma
mappa
1. Si parte da una libreria di cloni in BAC
2. Mappatura dei cloni sul genoma (mediante mappe fisiche)
3. Selezione un set minimo di BAC sovrapposti (minimum tiling path)
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Metodo top-down
Mappe fisiche cromosomiche
Forniscono la posizione
relativa e una stima della
distanza di una serie di
marcatori:
- geni
- poliformismi
- siti di restrizione
- STS
- etc.
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Metodo top-down
Un clone in un BAC
genoma
1.
2.
3.
4.
5.
6.
Lezione 1
mappa
Si parte da una libreria di cloni in BAC
Mappatura dei cloni sul genoma (mediante mappe fisiche)
Selezione un set minimo di BAC sovrapposti (minimum tiling path)
Sequenziamento di ogni clone per shotgun
Assemblaggio
Identificazione relazioni a lunga distanza
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Metodo top-down
I BAC che sono stati selezionati sono poi
purificati dalle corrispondenti colonie
batteriche.
Il DNA purificato è rotto con mezzi fisici, e
frammenti di dimensione 2–5 kb sono clonati,
stavolta in plasmidi.
Questi frammenti sono poi sequenziate con il
metodo di Sanger a partire da una od
entrambe le estremità.
Le sequenze generate sono chiamate reads.
Le reads le cui sequenze si sovrappongono
sono raggruppate (assemblate), e la
sequenza che si genera dalla loro
sovrapposizione e' chiamata contig di
sequenza.
Questi contigs sono una versione preliminare
dell'assemblaggio finale, intervallati da regioni
non coperte (gaps) o di scarsa qualità. La
ripetizione di alcune sequenze, o l'aggiunta di
nuovi dati, può aiutare a rifinire
l'assemblaggio.
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Metodo top-down
Contig: un set continuo di sequenze overlappanti
Gap
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Metodo top-down
Read Coverage
l
n
L
Lunghezza del segmento assemblato: L
Numero di reads:
n
Lunghezza media delle reads:
l
Coverage C = n l / L
Modello di Lander-Waterman:
Assumendo una distribuzione uniforme delle reads, C=10 equivale a 1 gap
ogni 1,000,000 di nucleotidi
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Double barrel shotgun sequencing
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Double barrel shotgun sequencing
Assemblaggi fatti senza dati di
reads appaiate conducono a
contigs il cui ordine e
orientamento non sono noti.
Contig
Consensus (15-30Kbp)
Reads
?
Reads appaiate possono
creare ponti fra contigs, e
permettono anche di stimare
le dimensioni dei gaps
550bp
10,000bp
Gap
Scaffold
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Double barrel shotgun sequencing
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Strategie per il sequenziamento di genomi
Terminologia:
read
una sequenza di 500-900 basi determinata
dal sequenziatore
overlap
regione significativa di sovrapposizione fra
due reads che ne fa supporre la contiguità
sul genoma
paired reads una coppia di reads dalle due
estremità dello stesso clone
contig
una sequenza ininterrotta formata
da molte reads sovrapposte
supercontig un insieme ordinato e orientato di contig,
(scaffold)
basato sulle reads appaiate
sequenza
consenso
Lezione 1
sequenza derivata dall'allineamento
multiplo delle reads di un contig
..ACGATTACAATAGGTT..
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Strategie per il sequenziamento di genomi
Hierarchical shotgun sequencing
Lezione 1
Whole-genome shotgun sequencing
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Double barrel shotgun sequencing
Bottom-up
Top-down
Frammento di DNA (poche kb)
paired-end reads (500b)
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Strategie per il sequenziamento di genomi
Whole-genome shotgun sequencing
Clone-based sequencing
Vantaggi:
Non richiede conoscenze preliminari
Veloce
Vantaggi:
Basato su mappe fisiche dei
cromosomi
Richiede un numero minore di
sequenze
Svantaggi:
Richiede un numero elevato di
sequenze
Assemblaggio complesso
Riempimento dei gaps
Costi (?)
Svantaggi:
Basato su mappe fisiche dei
cromosomi
Creazione delle librerie di BACs
Selezione dei BACs
Tempi
Costi (?)
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Strategie per il sequenziamento di genomi
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Human Genome Project (1990)
- Scopo: ottenere la sequenza del genoma umano eucromatico;
- Dimensioni: 3Gb
- Approccio: clone-based genome shotgun
- Data prevista di completamento: 2005
- Finanziamento: 3 miliardi di dollari
- Partners: laboratori in USA, UK, Francia, Germania, Giappone, Cina e India
- Sono stati usati una serie di donatori anonimi, uomini e donne
2000: il primo assemblaggio (working draft) viene completato nello UCSC Genome
Bioinformatics Group, da Jim Kent, Patrick Gavin, Terrence Furey, e David Kulp.
2003: l' assemblaggio completo viene pubblicato
La maggior parte del genoma umano è stato sequenziato con coverage di 12X,
quindi ogni nucleotide del genoma è presente in media su 12 reads. Nonostante
questo, non si e' ancora stati in grado di sequenziare od assemblare circa 1% del
genoma eucromatinico.
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2009/2010
2010/2011
Human Genome Project
Strategia usata: Hierarchical shotgun
1. Il genoma e' rotto in frammenti da
150mila basi, inseriti in vettori chiamati
BAC (cromosomi artificiali batterici).
2. I frammenti sono sottoposti a
sequenziamento shotgun per ottenere
delle sequenze di qualche centinaia di
basi (reads).
3. Le reads sono assemblate da algoritmi
appositi mediante regioni di overlap.
4. I frammenti cosi sequenziati sono
mappati sul genoma grazie a marcatori
(ad esempio genetici).
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Human Genome Project
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Human Genome Project
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Human Genome Project
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Celera (1998)
Nel 1998 una azienda privata la Celera, fondata da Craig Venter (che era stato il
primo ad applicare WGS ad organismi superiori) raccolse 300 milioni di dollari per
sequenziare il genoma umano più in fretta (e più economicamente) del consorzio
HGP.
Fino a quel punto, il genoma di Heamophilus influenzae (1.8 Mbp) e di Drosophila
melanogaster (135 Mbp) erano stati sequenziati con successo per WGS.
Venter intendeva sequenziare ed assemblare il genoma in meno di due anni con
coverage 10X, generando 50-60 milioni di reads.
Tutto dipendeva dal suo assemblatore e dall'utilizzo del double barrel shotgun per
identificare relazioni a lunga gittata
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Haemophilus Influenzae Sequencing
Estrazione del DNA
Frammentazione
per sonicazione
1.5-2kb
Separazione dei
frammenti
Libreria di cloni
Sequenziamento
Assemblaggio
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Celera (1998)
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Sequenziamento del genoma umano
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Sequenziamento del genoma umano
- Chi ha vinto?
Il genoma umano e' di dominio pubblico
La Celera ha dovuto ricorrere ad informazioni prodotte dal consorzio HGP
Ma l'approccio WGS ha funzionato
- Cosa e' stato prodotto?
90% della sequenza (320 milioni di bp erano mancanti)
Coverage medio 4X
25% della sequenza a 8-10X
50000 scaffolds (lunghezza media 54.2 Mbp)
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Sequenziamento del genoma umano
E' stato spesso affermato che il genoma umano e' stato completamente sequenziato,
ma stime recenti mostrano come solo intorno al 93% della sequenza e' nota. Alcune
regioni rimangono incomplete o del tutto sconosciute.
- Centromeri: sequenze altamente ripetitive di DNA molto difficili da sequenziare.
Possono essere anche molto lunghi (fin a milioni di basi), e sono quasi
completamente non sequenziati;
- Telomeri: anche essi sono sequenze altamente ripetitive. Possono avere
lunghezza variabile, per questo non e' chiaro quanto ne rimanga da sequenziare;
- Famiglie multigeniche complesse: geni simili in sequenza e vicini sul
cromosoma possono causare ambiguità durante l'assemblaggio. Un esempio sono
geni coinvolti nel sistema immunitario;
- Ci sono poi alcune decine di lacune (gaps) nella sequenza, alcune anche molto
grandi, ma che per motivi non noti non hanno raggiunto un livello di coverage
sufficiente.
Per regioni come telomeri e centomeri, è possibile che le attuali tecnologie non siano
in grado di determinarne la sequenza. E anche se ogni base del genoma fosse
sequenziata, rimarrebbero da determinare le differenze fra individui.
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Sommario
- I genomi di organismi modello contengono milioni o miliardi di nucleotidi
- Anche se le teconologie di sequenziamento possono produrre solo 700
basi per volta, è lo stesso posibile determinare la sequenza di genomi
complessi
- Due diverse strategie sperimentali sono state messe a punto (più strategie
ibride)
- Il problema maggiore (l'assemblaggio) è di natura algoritmica
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Assemblaggio
- L'assemblaggio del genoma è il processo per il quale a partire da un elevato numero di
sequenze corte, generate da sequenziamento shotgun, vengono ricostruite le sequenze dei
cromosomi da cui queste originano;
- E' una struttura gerarchica: le reads formano i contigs, i contigs formano gli scaffolds;
- Un contig può essere visto come un allineamento multiplo di reads, e la loro sequenza
consenso;
- Uno scaffold definisce ordine e orientamento dei contigs, e la dimensione dei gaps fra
contigs adiacenti (gaps sono di solito riempiti da dequenze di N);
- La bontà di un assemblaggio può essere stimata da varie misure:
- lunghezza media e massima di contigs e scaffolds
- lunghezza totale combinata;
- N50 (lunghezza del contig più piccolo nell' insieme più piccolo dei contig che si può
creare la cui longhezza combinata rappresenti almeno il 50% dell'assemblaggio).
Es.:
Genoma di 1 Mbp
Contigs: 300k, 100k, 50k, 45k, 30k, 20k, 15k, 15k, 10k, ....
N50 = 30 kbp
(300k+100k+50k+45k+30k = 525k >= 500kbp)
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Assemblatori
L'assemblaggio di un genoma è un problema molto difficile da un punto di vista
computazionale, specialmente perchè molti genomi contengono un grande numero di
sequenze identiche dette ripetizioni, lunghe anche migliaia di nucleotidi, e che possono
essere trovate in migliaia di siti diversi.
I primi assemblatori vennero disegnati alla fine degli anni '80, inizio anni '90, ed erano
varianti di algoritmi di allineamento di sequenze. Algoritmi più evoluti vennero poi sviluppati
per gestire:
- terabytes di sequenze;
- ripetizioni;
- errori di sequenziamento.
Ci sono due classi di assemblatori:
1. de-novo: le reads sono assemblate a formare un sequenza sconosciuta a priori;
2. mapping: le reads sono assemblate su una impalcatura gia nota
Gli assemblatori de-novo sono di vari ordini di grandezza più lenti e bisognosi di memoria.
Questo è principalmente dovuto alla necessità di confrontare ogni possibile coppia di reads.
La complessità O(n2) può essere però ridotta a O(n log(n)).
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Assemblatori
Data la natura casuale della
frammentazione delle sequenze
genomiche iniziali, un buon
assemblaggio è possibile solo se il
numero di reads è tale da coprire il
genoma 8-10 volte.
C'è una correlazione fra il
coverage e il numero di contigs
che possono essere generati da un
assemblatore (modello di LanderWaterman).
Per un genoma di 1Mbp, il modello
prevede che il genoma può essere
assemblato in un numero piccolo
di contigs (circa 5) solo avendo
una coverage superiore a 8.
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Sequenze ripetute
Sequenze Ripetute: Un grosso problema per gli assemblatori
> 50% del genoma umano è costituito da ripetizioni:
- più di un milione di sequenze Alu repeats (di circa 300 bp)
- circa 200,000 sequenze LINE (1000 bp o più)
Due assemblaggi equivalenti
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Sequenze ripetute
Bacterial genomes:
Mammals:
5%
50%
Tipo di ripetizione:
DNA a bassa complessità
Microsatelliti
(ad es. ATATATATACATA…)
(a1…ak)N dove k ~ 3-6
(ad es. CAGCAGTAGCAGCACCAG)
Trasposoni
SINE
(Short Interspersed Nuclear Elements)
ad es. ALU: ~300-long, 106 copie
LINE
LTR retroposoni
Lezione 1
(Long Interspersed Nuclear Elements)
lunghezza ~4000, 200,000 copie
(Long Terminal Repeats (~700 bp))
simili a sequenze virali
Famiglie Geniche
geni che si duplicano, poi la sequenza diverge (paraloghi)
Duplicazioni recenti
mantengono alta similarità di sequenza
Genomica Computazionale, Laurea Magistrale A.A. 2009/2010
2010/2011
Sequenze ripetute
Esistono varie classi di ripetizioni. Il
numero di copie va da 2, come nel
caso di duplicazioni di geni, a circa
106 nel caso delle sequenze ALU
nel genoma umano.
La similarità di sequenza fra
membri della stessa classe può
essere intorno al 100%, o anche
molto bassa, come ad esempio in
famiglie di trasposoni molto antiche
che sono diventate inattive.
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Shortest common superstring problem
Dato un insieme di stringhe S={s1, s2, …,sn}, trovare la stringa T più corta tale che ogni
stringa s sia una sottostringa di T (NP-hard)
i
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Approccio Overlap-layout-consensus
Dato un set di reads da sequenziamento shotgun...
1. trovare l'overlap fra tutte le coppie
2. trovare l'ordine delle reads sul genoma
3. determinare una sequenza rappresentativa
Overlap: trovare tutti le reads con regioni di sovrapposizione (contigs)
Layout: determinare regioni discrete (scaffolds, o supercontigs) di cui si
può stimare l'orientamento e la posizione reciproca
Contig Layout: fondere reads sovrapposte identificando i confini di
ogni regione
Supercontig assembly: I contigs devono essere ordinati, e regioni di
separazione fra di loro devono essere riempite
Consensus: ottenere la sequenza di ogni scaffold
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Assemblatori
All'inizio, ogni centro di sequenziamento sviluppò i propri strumenti per assemblare le
sequenze da loro prodotte. Man mano che il numero di sequenze disponibili cresceva, e
si affrontavano genomi più complessi, si sono sviluppati strumenti più versatili e potenti
●
PHRAP
●
●
●
Celera
●
●
●
●
Overlap → clustering → PHRAP → assemblaggio → consensus
Euler
●
Lezione 1
Assemblatore WGS open source (topo, piante, funghi)
Overlap → layout → consensus
Phusion
●
●
Primo assemblatore WGS capace di gestire genomi grandi (drosophila,
uomo, topo)
Overlap → layout → consensus
Arachne
●
●
Uno dei primi assemblatori, molto usato per piccoli genomi, buon
trattamento degli errori nelle reads
Sovrapposizione O(n2) → layout (senza paired reads) → consensus
Indexing → Euler graph → layout (percorsi sul grafo) → consensus
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Assemblatori
Fase 1. Overlap
1. Pulizia del dataset di reads
2. Identificazione e rimozione delle regioni ripetute
3. Identificazione efficiente delle regioni di sovrapposizione
4. Allineamento delle reads sovrapposte
Fase 2. Layout
- Vari approcci tentati
1. Algoritmi greedy
3. Costruzione di grafi
4. Clustering
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Algoritmi greedy
Algoritmo greedy:
1. Calcola la sovrapposizione fra ogni coppia si e sj di S;
2. Assegna un punteggio ad ogni sovrapposizione;
La sovrapposizione è solitamente calcolata con versioni modificate dell'algoritmo di
Smith-Waterman, per consentire allineamenti imperfetti dovuti ad errori nel
sequenziamento;
3. Unisci coppie di stringhe in ordine decrescente di punteggio.
Le due reads con overlap migliore sono concatenate; si passa poi alla read con
overlap migliore con una delle due di partenza, e cosi via
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Overlap Graph
Grafo: è un'astrazione composta da un insieme di nodi (o vertici) uniti da lati (o archi);
Un grafo i cui i nodi possono essere attraverstai in una sola direzione è detto diretto;
Un "percorso" di lunghezza n nel grafo è dato da una sequenza di vertici v0,v1,..., vn
(non necessariamente tutti distinti) e da una sequenza di archi che li collegano (v0,v1),
(v1,v2),...,(vn-1,vn). I vertici v0 e vn si dicono estremi del percorso.
Un percorso con i lati a due a due distinti tra loro prende il nome di cammino.
Un cammino chiuso (v0 = vn) si chiama circuito o ciclo.
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Overlap Graph
[Schatz, 2010]
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Overlap Graph
[Schatz, 2010]
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Overlap Graph
Overlap graph: grafo dove i nodi rappresentano ogni read, e gli archi connettono due nodi
se le corrispondenti reads sono sovrapposte. In questa rappresentazione, il problema
dell'assemblaggio si riconduce al problema di trovare un percorso nel grafo contenente tutti
i nodi.
1. Costruisci un grafo con n vnodi rappresentanti le n stringhe s1, s2,…., sn
2. Inserisci archi di lunghezza pari all' overlap ( si, sj ) fra nodi si and sj
3. Trova il percorso più corto che visiti ogni nodo una volta sola (percorso Hamiltoniano,
NP-hard): questo è il problema del commesso viaggiatore (Traveling Salesman Problem)
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Overlap Graph
S = { ATC, CCA, CAG, TCC, AGT }
SSP
AGT
CCA
ATC
TCC
CAG
ATCCAGT
ATC
0
1
AGT
Inizio
1
2
1
1
2
CAG
CCA
2
2
1
TCC
ATCCAGT
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Allineamento di sequenze
X: AGGCTATCACCTGACCTCCAGGCCGATGCCC
Y: TAGCTATCACGACCGCGGTCGATTTGCCCGAC
Definizione
Date due stringhe
x = x1x2...xM,
y = y1y2…yN,
un allineamento consiste nell'assegnazione di gaps fra le posizioni 0,…,N
di x e 0,…,M di y, in modo da allineare ogni carattere in una delle
sequenze con un carattere, o un gap dell'altra sequenza.
X: -AGGCTATCACCTGACCTCCAGGCCGA--TGCCC--Y: TAG-CTATCAC--GACCGC--GGTCGATTTGCCCGAC
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Allineamento di sequenze
X: AGGCTATCACCTGACCTCCAGGCCGATGCCC
Y: TAGCTATCACGACCGCGGTCGATTTGCCCGAC
Definizione
Date due stringhe
x = x1x2...xM,
y = y1y2…yN,
un allineamento consiste nell'assegnazione di gaps fra le posizioni 0,…,N
di x e 0,…,M di y, in modo da allineare ogni carattere in una delle
sequenze con un carattere, o un gap dell'altra sequenza.
X: -AGGCTATCACCTGACCTCCAGGCCGA--TGCCC--Y: TAG-CTATCAC--GACCGC--GGTCGATTTGCCCGAC
Dato un sistema di punteggi, l'allineamento ottimale è quello che massimizza il punteggio
totale.
Scoring Function:
Match:
+m
Mismatch:
-s
Gap:
-d
Score F = (# matches) x m - (# mismatches) x s – (#gaps) x d
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Allineamento di sequenze
Algoritmo di Needleman-Wunsch
AGTGCCCTGGAACCCTGACGGTGGGTCACAAAACTTCTGGA
AGTGACCTGGGAAGACCCTGACCCTGGGTCACAAAACTC
Ogni percorso nella matrice, da (0,0) a (M, N),
corrisponde ad un diverso allineamento.
Il numero di possibili percorsi e' enorme,
22N / √πN (10149 per due sequenze di 250 basi)
Ma il problema può essere scomposto in
sottoproblemi: se l'allineamento ottimale fra x1…xi
e y1…yj è noto, allora l'allineamento ottimale fra
x1…xi+1 e y1…yj+1 è uguale all'allineamento fra x1…xi
e y1…yj e l'allineamento ottimale di xi+1 con yj+1
E' possibile trovare l'allineamento ottimale in
O(nm)
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Allineamento di sequenze
Algoritmo di Smith-Waterman
AGTGCCCTGGAACCCTGACGGTGGGTCACAAAACTTCTGGA
AGTGACCTGGGAAGACCCTGACCCTGGGTCACAAAACTC
Lezione 1
L'allineamento di Needleman-Wunsch è
globale, cioè trova l'allineamento ottimale delle
due sequenze dalla posizione 1 alla posizione
N o M.
In molti casi puo' essere utile trovare le regioni
più simili.
L'algoritmo di Smith-Waterman è una variante
del Needleman-Wuncsh per questo scopo,
cambiando l'inizializzazione della matrice e il
modo di gestire i punteggi.
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011
Allineamento di sequenze
Algoritmo FASTA
Smith-Waterman e Needleman-Wunsch
sono quadratici, rendendoli pratici solo
per allineare due sequenze ma non per
effettuare un numero elevato di
confronti.
FASTA si basa sulla divisione delle
sequenze in parole e sull'identificazione
di match perfetti fra parole delle due
sequenze.
L'allinamento finale e' effettuato con
programmazione dinamica.
Lezione 1
Genomica Computazionale, Laurea Magistrale A.A. 2010/2011