Identificazione reference-free e assembly-free di polimorfismi a singolo nucleotide con Prefix-Free Parsing

(1)

Universit`a di Pisa

Laurea Magistrale in Informatica

Data and Knowledge: Science and Technologies

Identificazione reference-free e

assembly-free di polimorfismi a singolo

nucleotide con Prefix-Free Parsing

Relatore:

Prof.ssa Nadia PISANTI

Candidato:

Riccardo MANETTI

(2)

(3)

Abstract

La presente tesi illustra una strategia che, senza la necessit`a di un genoma di riferimento (reference-free) e senza effettuare l’operazione di assemblaggio delle sequenze (assembly-(reference-free), identifica i po-limorfismi a singolo nucleotide (SNP) attraverso le informazioni calcolate dalla procedura di pre-processing denominata Prefix-Free Parsing (PFP). In letteratura gli eBWT cluster sono conosciuti come una tecnica di identificazione degli SNP basata sull’osservazione che i simboli che condivi-dono uno stesso contesto risultano contigui in una sottostringa della extended Burrows-Wheeler Transform (eBWT). Presentiamo due metodi in grado di identificare gli SNP elaborando gli eBWT cluster, uno che sfrutta le informazioni contenute nelle strutture dati del PFP, e l’altro che le ottiene effettuando query efficienti sui dati del PFP.

(4)

(5)

Indice

Abstract I

Indice III

1 Introduzione 1

1.1 Il DNA: scoperta, struttura e funzione . . . 2

1.2 Sequenziamento del genoma . . . 5

1.3 Progetto genoma umano . . . 8

1.4 Banche dati genomiche . . . 10

2 Background Biologico 13 2.1 Le mutazioni del DNA . . . 13

2.1.1 Mutazioni cromosomiche . . . 14

2.1.2 Mutazioni geniche . . . 15

2.2 Processo di identificazione delle mutazioni del DNA . . . 18

2.2.1 Assemblaggio del genoma . . . 19

2.2.2 Allineamento di sequenze . . . 20

2.2.3 Variant Calling . . . 21

3 Strutture algoritmiche 23 3.1 Suffix Tree, Suffix Array e LCP array . . . 24

3.2 La Burrows-Wheeler Transform e le sue propriet`a . . . 28

3.3 Strutture dati generalizzate . . . 31

4 Framework positional clustering 35 4.1 Il positional clustering . . . 36

4.1.1 Definizione dell’eBWT cluster . . . 36

4.1.2 Localizzazione dell’eBWT cluster . . . 38

4.1.3 Strutture dati compresse . . . 40

4.2 Variant calling per gli SNP e le INDEL . . . 40

4.3 Performance del framework . . . 43

5 Prefix-Free Parsing 45 5.1 Teoria del Prefix-Free Parsing . . . 46

5.2 Implementazione del Prefix-Free Parsing . . . 50

5.3 Prefix-Free Parsing come struttura dati . . . 52

(6)

6 Variant calling con il Prefix-Free Parsing 59

6.1 Fase di pre-processing . . . 62

6.2 Localizzazione degli eBWT cluster . . . 63

6.2.1 Localizzazione degli eBWT cluster attraverso il Metodo 1 . . . 63

6.2.2 Localizzazione degli eBWT cluster attraverso il Metodo 2 . . . 67

6.3 Identificazione degli SNP . . . 69

6.4 Considerazioni sulle prestazioni . . . 71

7 Conclusioni 75

Acronimi 79

(7)

(8)

(9)

CAPITOLO

1

Introduzione

La vita è caratterizzata da un’enorme diversità, ma in tutti gli esseri viventi le istruzioni che codi-ficano per la trasmissione dei caratteri genetici sono scritte nel medesimo linguaggio: quello degli acidi nucleici. Anche solo considerando gli esseri umani, è evidente che essi presentano allo stesso tempo molti aspetti in comune, ma anche enormi differenze. Alcune di queste differenze tra gli individui umani derivano dall’ambiente e dalle esperienze di vita, ma il nostro DNA gioca un ruolo importante determinando le nostre apparenze, i nostri tratti e la nostra salute.

Ancor prima che gli acidi nucleici fossero identificati come materiale genetico (genotipo), i bio-logi concordavano sul fatto che il materiale biobio-logico dovesse possedere quattro caratteristiche fondamentali: contenere informazioni complesse, replicarsi fedelmente, codificare per il fenotipo (ossia l’insieme di tutte le caratteristiche manifestate da un organismo vivente), ed infine avere la capacit`a di variare.

Immaginate di trovarvi faccia a faccia con uno sconosciuto qualsiasi. Quanta parte del vostro genoma avete in comune con lui? Studi sulla variabilità del genoma umano ci dicono che, in media, tra voi e lo sconosciuto il 99,9% delle sequenze di DNA è in comune. La differenza fra voi e lo sconosciuto può dunque apparire minima, ma poiché il genoma umano è molto grande (3,2 miliardi di paia di basi nella sua forma aploide), in media tra i vostri genomi sussiste una differenza di oltre tre milioni di paia di basi (ossia lo 0, 1% di 3, 2 miliardi di paia di basi). Anche se equivale a circa una differenza per gene in realtà queste differenze non sono distribuite in modo uniforme in tutta la regione di codifica, e rappresentano ciò che rende ognuno di noi unico, avendo effetti marcati sulle nostre caratteristiche fisiche, sulla nostra salute, e probabilmente anche sulla nostra intelligenza e personalità. Ad esempio, singoli geni mutati oppure l’interazione di multipli, possono determinare se svilupperemo o avremo una predisposizione a sviluppare malattie come l’anemia falciforme, la fibrosi cistica o il cancro, oppure determinare il colore dei capelli e della pelle, l’altezza, il peso, la pressione sanguigna, o ancora il rischio di sviluppare il diabete di tipo 2, depressione o altri disordini autoimmuni.

(10)

CAPITOLO 1. Introduzione 1.1. Il DNA: scoperta, struttura e funzione

1.1 Il DNA: scoperta, struttura e funzione

L’acronimo DNA (DeoxyriboNucleic Acid) definisce l’acido desossiribonucleico, un polimero or-ganico a doppia catena i cui monomeri sono chiamati desossiribonucleotidi (o più semplicemente nucleotidi, dNTP), che rappresentano la più piccola unità genetica.

Anche se la conoscenza su come il DNA codifichi le informazioni genetiche è relativamente recente, lo studio della sua struttura risale a più di cento anni fa. A partire dal 1880 circa, numerosi ricercatori giunsero alla conclusione che le informazioni dell’eredità erano contenute nel nucleo. Si dimostrò che la cromatina (meglio descritta in seguito) era composta da acido nucleico e proteine, ma non era ancora chiaro quale di queste sostanze costituisse realmente l’informazione genetica. Nei primi anni del ventesimo secolo fu poi scoperto che il DNA è composto da un gran numero di unità collegate che si ripetono, dette nucleotidi; ognuna delle quali è definita da uno zucchero, un gruppo fosfato e una delle quattro basi azotate: adenina (A), timina (T), guanina (G) e citosina (C). Al termine di ulteriori studi sulla chimica del DNA, fu scoperto che all’interno di ogni specie, esiste una sorta di regolarità nei rapporti fra le basi: la quantità di adenina è sempre uguale a quella di timina (A=T) e la quantità di guanina è sempre uguale a quella di citosina (G=C). Si appurò quindi che le proprietà chimiche dei nucleotidi consentono ai legami di formare un doppio filamento associando adenina e timina con due legami idrogeno oppure citosina e guanina con tre legami idrogeno.

Nel mentre i chimici si concentravano sulla struttura del DNA, i biologi tentavano di identificare la fonte dell’informazione genetica. Mendel aveva scoperto le regole di ereditariet`a nel 1866 [1], ma non aveva la minima idea riguardo la natura fisica dell’informazione ereditaria. Nei primi anni del Novecento i biologi giunsero alla conclusione che i geni erano posti sui cromosomi, di cui si sapeva che contenevano sia DNA che proteine. Furono due esperimenti, uno condotto sui batteri e l’altro sui virus, a fornire la prova definitiva che era il DNA a costituire il materiale genetico.

I primi esperimenti sulla natura del materiale genetico avviarono uno dei progressi più impor-tanti nella storia della biologia: la scoperta della struttura tridimensionale del DNA da parte di J. Watson e F. Crick avvenuta nel 1953 [2]. Watson e Crick non studiarono direttamente la struttura del DNA raccogliendo nuovi dati, ma utilizzarono le informazioni già disponibili, come le immagini della diffrazione a raggi X elaborate da R. Franklin e R. Gosling [3], per costruire i modelli delle strutture che il DNA avrebbe potuto assumere. L’utilizzo dei modelli ha permesso di valutare se una determinata struttura era compatibile sia con i principi della chimica che con le immagini a raggi X. Il modello messo a punto da Watson e Crick rivelò che il DNA è composto da due filamenti di nu-cleotidi orientati in direzione opposta che si avvolgono l’uno attorno all’altro per formare un’elica in cui esternamente lo zucchero e il gruppo fosfato formano lo scheletro strutturale e le basi azota-te, all’interno, determinano la sequenza del DNA. La direzione di ogni filamento polinucleotidico è stabilita da un’estremità 5’ a un’estremità 3’ (l’indice 5’ e 3’ sono dati dalle caratteristiche chimiche dei nucleotidi), ed avvolgendosi in direzioni opposte, i due filamenti di DNA, sono antiparalleli, il che significa che l’estremità 5’ di un filamento si trova di fronte a quella 3’ dell’altro filamento.

Se il DNA fosse disteso, raggiungerebbe una lunghezza di circa due metri, quindi, per rientrare in cellule di soli 10 micrometri di diametro, deve essere estremamente condensato. Per compattare la sua lunghezza e farla entrare nel ridotto volume disponibile nel nucleo di una cellula eucariota(1),

(11)

CAPITOLO 1. Introduzione 1.1. Il DNA: scoperta, struttura e funzione ogni molecola di DNA viene attorcigliata e strettamente condensata intorno alle proteine istoniche, con le quali il DNA forma un complesso chiamato cromatina, materiale che costituisce i cromosomi. Le proteine istoniche permettono quindi al materiale genetico di risiedere all’interno del nucleo, limitando però la possibilità di accesso di enzimi e altre proteine al DNA. Pertanto, l’informazione genetica è accessibile solo a seguito della separazione del DNA dagli istoni.

La cromatina ha una struttura altamente complessa con vari livelli di organizzazione (Figura 1.1). Il livello più semplice è la struttura a doppia elica del DNA. La molecola di DNA si associa poi a proteine e fortemente ripiegata su se stessa forma un livello strutturale maggiore di forma sferi-ca, denominato nucleosoma. I nucleosomi si ripiegano ulteriormente su se stessi a formare una struttura densa e strettamente compatta. Il livello più elevato di complessità della cromatina è ca-ratterizzato da una serie di anse che si avvolgono fino a formare la fibra di cui un cromatidio, e di conseguenza un cromosoma, è composto.

nucleosoma

cromatidio cromosoma DNA a doppia elica istone

Figura 1.1: Livelli di organizzazione della struttura complessa della cromatina.

La cellula di ogni specie eucariota possiede un numero di cromosomi caratteristico, detto ca-riotipo, e quello dell’uomo corrisponde a 46. Come conseguenza della riproduzione sessuata, nella maggior parte delle cellule eucarioti sono presenti due serie di cromosomi: una serie viene ereditata dal genitore di sesso maschile e l’altra da quello di sesso femminile. Ogni cromosoma di una serie ha un cromosoma corrispondente e insieme costituiscono una coppia omologa; le cellule umane, per esempio, hanno 46 cromosomi, che formano 23 coppie omologhe (Figura 1.2). I due cromosomi di una coppia omologa di solito sono simili per struttura e dimensioni e ciascuno di loro trasporta le informazioni genetiche relative alla stessa serie di tratti ereditari. Ad esempio, se un gene di un particolare cromosoma codifica per il colore dei capelli, anche l’altra copia del gene, cio`e il suo al-lele, posizionato nello stesso punto sul cromosoma omologo, codifica per il colore dei capelli. Sono denominate diploidi le cellule che trasportano due serie di informazioni genetiche e aploidi quelle che contengono un’unica serie di cromosomi (come il gamete femminile, cellula uovo, oppure il gamete maschile, spermatozoo).

La genomica `e il campo della genetica che si occupa di studiare il contenuto, l’organizzazione, la funzione e l’evoluzione dell’informazione genetica contenuta in genomi completi. Le informazioni derivanti da questo ambito hanno fornito notevoli contributi non solo alla salute umana, ma anche

Le cellule eucarioti sono invece pi`u complesse, possiedono un nucleo ben definito, isolato dal resto della cellula tramite una membrana e contenente la maggior parte del DNA.

(12)

CAPITOLO 1. Introduzione 1.1. Il DNA: scoperta, struttura e funzione

Figura 1.2: Cariotipo umano (femmina) composto da 46 cromosomi in 23 coppie omologhe. all’agricoltura e numerosi altri settori. Il dottor P. Vezzoni, responsabile dei Laboratori di Biotecno-logie Mediche in Humanitas e dirigente di ricerca del Consiglio Nazionale delle Ricerche (CNR) ha utilizzato un’analogia che abbraccia il mondo informatico per definire il genoma: “Il genoma può essere paragonato al software di un computer e i singoli geni alle istruzioni necessarie per costruire e far funzionare la macchina (ovvero l’organismo). Quindi il genoma può essere rappresentato come un manuale di istruzioni che dirige prima lo sviluppo del nostro organismo e poi il funzionamento dell’organismo stesso.” [4]. È quindi facile da comprendere come anche una singola istruzione erra-ta presente all’interno di un gene, ovvero una muerra-tazione genetica, possa gravemente danneggiare il buon funzionamento dell’organismo e causare quella che viene chiamata una malattia genetica.

Il genoma umano, in particolare, `e l’insieme completo delle sequenze di acidi nucleici codificate nel DNA umano all’interno delle 23 coppie di cromosomi presenti nel nucleo delle cellule. Il genoma umano presenta un corredo di circa 3, 2 miliardi di paia di basi (abbreviato “bp”, dall’inglese base pair) di DNA contenenti circa20 000 geni, ossia porzioni di genoma localizzate in precise posizioni all’interno della sequenza di DNA, codificanti per proteine [5].

L’importanza che riveste il DNA `e quella di memorizzare le informazioni genetiche necessarie alla sintesi di proteine e di RNA (RiboNucleic Acid - acido ribonucleico - molecola polimerica im-plicata in vari ruoli biologici di codifica, decodifica, regolazione ed espressione dei geni), molecole indispensabili per lo sviluppo ed il corretto funzionamento di tutti gli organismi viventi.

La maggior parte degli organismi eucarioti contiene grandi quantità di DNA che non codifica per proteine. Per esempio, indagini genomiche su larga scala suggeriscono che fino all’80% del geno-ma ugeno-mano potrebbe essere coinvolto nella regolazione genica, mentre solo il 2% circa del genogeno-ma umano è composto da DNA che codifica direttamente per gli aminoacidi delle proteine necessarie alla funzionalità e vitalità dell’organismo [6, 7]. La funzione delle restanti sezioni di DNA, chia-mate nel loro complesso DNA non codificante, è da tempo in discussione. Alcuni ricercatori hanno osservato che, la rimozione di vaste regioni del genoma dei mammiferi non ha provocato rilevanti effetti fenotipici, concludendo che tali regioni si possono considerare di fatto superflue. Tuttavia altri ricercatori hanno suggerito che il DNA non codificante può contenere sequenze che possiedo-no un ruolo funzionale fornendo informazioni sulla regolazione su cui si basa il processo biologico. Per stabilire la funzione di tutte le regioni del genoma, e quindi stabilire se il DNA non codifican-te abbia qualche funzione, nel 2003 è stato lanciato il progetto ENCODE(2)_{(Encyclopedia of DNA}

Elements). I ricercatori hanno catalogato tutti i nucleotidi che nel genoma sono responsabili di

(13)

CAPITOLO 1. Introduzione 1.2. Sequenziamento del genoma qualche funzione, a partire dalle sequenze che codificano per proteine e molecole di RNA, fino a quelle che servono da siti di controllo per l’espressione genica. Al termine dello studio di ENCODE si ha ragione di ritenere che il DNA non funzionale rappresenti solo una parte del genoma umano.

1.2 Sequenziamento del genoma

Il sequenziamento del DNA è una potente tecnica molecolare per analizzare il DNA e determinare la sequenza di basi che lo compone. Il sequenziamento permette la lettura delle informazioni con-tenute nel DNA, fornendo un’enorme quantità di dati su struttura e funzione dei geni. Intorno alla metà degli anni settanta A. Maxam e W. Gilbert [8] svilupparono un metodo di sequenziamento del DNA basato sulla degradazione chimica del DNA stesso; mentre poco prima, Sanger [9] presentò un metodo di sequenziamento basato sull’allungamento del DNA ad opera delle DNA polimera-si(3). Sebbene il metodo Maxam-Gilbert divenne da subito popolare e preferito rispetto ai metodi concorrenti, con il successivo miglioramento del metodo Sanger, il metodo Maxam-Gilbert venne progressivamente accantonato a causa della complessità tecnica e dell’uso estensivo di sostanze tossiche, oltre al fatto che si è dimostrato piuttosto difficile poter sviluppare un kit da laboratorio pronto all’uso.

Il metodo Sanger (Figura 1.3), chiamato anche metodo didesossi o metodo dei terminatori di cate-na, consiste nell’utilizzo di un frammento di DNA come stampo per realizzare una serie di nuove molecole di DNA. Solitamente il DNA viene sintetizzato a partire da nucleotidi dNTP (desossiribo-nucleosidi), questo metodo richiede per`o l’utilizzo di uno speciale substrato caratterizzato da speci-fici nucleotidi, uno per ciascuna base, chiamati ddNTP (didesossiribonucleosidi). Senza scendere nei dettagli chimici `e sufficiente comprendere che durante il processo, la replicazione si arresta quan-do incontra una base specifica delle ddNTP, producenquan-do filamenti di DNA di diversa lunghezza, ciascuno dei quali termina con la medesima base ddNTP.

Stampo Primer CTAAGCTCGACT5' 3' -OH 5' 3'

Aggiunta dei quattro nucleotidi dNTP, uno per ciascuna base, e della DNA polimerasi dATP dCTP dGTP dTTP + DNA polimerasi Aggiunta di un “terminatore” ddNTP per ciascuna base separatamente

ddATP ddCTP ddGTP ddTTP

+ + + +

Filamenti

di DNA sintetizzati per ciascuna base e di lnghezza diversa

CTAAGCTCGACT GATTCGAGCTG GATTCG G A A A CTAAGCTCGACT GATTCGAG GATTC C CTAAGCTCGACT GATTCGAGCT GATTCGA GATTC G G G G CTAAGCTCGACT GATTCGAGC GAT GA T T T Autoradiogramma del gel dell’elettroforesi

A C G T Sequenza complementare allo stampo 5' 3' GA T T C GA GC T GA 5' 3' CT A A G CT C G A CT

Figura 1.3: Schema del metodo Sanger per il sequenziamento del DNA.

(3)_{Le DNA polimerasi sono enzimi che, utilizzando come stampo un filamento di DNA, sono in grado di sintetizzare un}

(14)

CAPITOLO 1. Introduzione 1.2. Sequenziamento del genoma Anche se `e tecnicamente possibile ottenere una sequenza da una singola molecola di DNA, molte delle attuali procedure di sequenziamento richiedono un notevole quantitativo di DNA; ogni fram-mento, per poter essere sequenziato, deve essere prima amplificato con la reazione a catena della polimerasi (PCR - Polymerase Chain Reaction) o tramite clonaggio in batteri.

In un primo passaggio, molte copie del DNA stampo e di un primer complementare a un’estremità del filamento del DNA stampo, vengono addizionate con i quattro tipi di dNTP, la DNA polimerasi. Il metodo procede poi isolando il materiale in quattro provette distinte, in ognuna delle quali viene aggiunta una piccola quantità di uno solo dei quattro tipi di ddNTP. All’interno di ognuna delle pro-vette, partendo dal primer la DNA polimerasi allunga il filamento sintetizzato di DNA aggiungendo casualmente un dNTP o un ddNTP, della specifica base inserita in provetta, dovunque incontri un nucleotide complementare sul filamento stampo (per esempio nel nuovo filamento verrà inserito un dATP o un ddATP qualvolta si incontri una T sul filamento stampo). L’inserimento casuale delle ddNTP produce quindi catene di DNA di varie lunghezze.

Quando le reazioni di polimerizzazione sono concluse, il DNA contenuto in ciascuna provetta viene denaturato e i prodotti a singolo filamento vengono separati tramite elettroforesi su gel. A seguito dell’elettroforesi, la sequenza di DNA si pu`o leggere direttamente dalle bande che compa-iono nell’autoradiografia del gel, a partire dal fondo e tenendo presente che la sequenza ottenuta non `e quella del DNA bersaglio ma quella complementare.

Per molti anni il sequenziamento del DNA `e stato effettuato soprattutto manualmente, con una procedura particolarmente laboriosa e costosa. Oggi si sequenziano migliaia di basi in poche ore grazie a sequenziatori automatici che utilizzano coloranti fluorescenti e scanner laser. Marcando i ddNTP con coloranti diversi per ogni base, `e possibile ottenere quattro reazioni di sequenziamento nella stessa provetta durante l’elettroforesi. Al passaggio dei frammenti davanti al laser, i coloranti si eccitano ed emettono una fluorescenza ad una lunghezza d’onda caratteristica che viene letta da uno scanner ottico. I dati vengono quindi inviati a un computer per essere interpretati e i risultati espressi sotto forma di grafico. I sequenziatori automatici permettono, in poche ore, di leggere da 50 000 a 60 000 bp di sequenza.

Le tecnologie di sequenziamento di ultima generazione, chiamate Next-Generation Sequencig (NGS), sono nuove metodiche che hanno reso questa procedura centinaia di volte più veloce e meno costosa del tradizionale metodo Sanger. Nella maggior parte dei casi, le NGS sequenziano in parallelo: milioni di frammenti di DNA vengono sequenziati simultaneamente. Nonostante il costo del sequenziamento di un genoma umano completo è nettamente diminuito e continua e scendere man mano che la tecnologia per tale scopo si perfeziona; uno degli obiettivi delle tecnologie di se-quenziamento di terza generazione è sviluppare un metodo che possa consentire il sese-quenziamento di un intero genoma umano a un costo inferiore a 1 000 euro.

Il sequenziamento Illumina(4)[10] impiega una tecnica simile a quella del metodo di Sanger. Si utilizzano nucleotidi speciali, ciascuno dei quali è legato a un marcatore fluorescente di colore diverso. Ogni nucleotide possiede anche un gruppo chimico (il terminatore) che, una volta incorpo-rato nella catena di DNA sintetizzata, evita la concatenazione di qualsiasi altro nucleotide. Questa situazione è simile alla terminazione causata dai ddNTP nel sequenziamento di Sanger, ma differi-sce in quanto il terminatore è reversibile, ossia può essere rimosso chimicamente.

(15)

CAPITOLO 1. Introduzione 1.2. Sequenziamento del genoma Per effettuare il sequenziamento, il DNA viene prima frammentato in milioni di frammenti sovrap-posti, i quali vengono poi attaccati ad un vetrino e amplificati, creando cluster di più di mille copie di ogni frammento. In seguito i frammenti vengono denaturati e si aggiunge una soluzione compo-sta da primer, DNA polimerasi ed i nucleotidi speciali. I primer si attaccano ad ogni DNA compo-stampo e al filamento sintetizzato viene concatenato il primo nucleotide. La soluzione viene poi rimossa con un lavaggio e il marcatore sul nucleotide viene eccitato da un laser emettendo fluorescenza. Come detto in precedenza, ogni tipo di nucleotide (A, T, G o C) ha un marcatore fluorescente di colore di-verso, perciò il colore della luce prodotta rivela quale nucleotide sia stato aggiunto. Il terminatore e il marcatore fluorescente vengono infine rimossi chimicamente e il processo si ripete nuovamente. Man mano che, uno alla volta, si aggiungono i nucleotidi, la sequenza viene letta sotto forma di una serie di lampi di luce colorata provenienti da ogni cluster di DNA. Le tecniche NGS leggono fram-menti di DNA generalmente più corti di quanto facciano le reazioni di sequenziamento di Sanger, ma dato che il sequenziamento avviene simultaneamente per milioni di frammenti, questi metodi sono molto più veloci della tradizionale tecnica Sanger.

Dal 2010 circa ad oggi, sono in fase di sviluppo metodiche ancora pi`u avanzate e rapide, chiamate sequenziamenti di terza generazione, tra cui la tecnologia a nanopori di Oxford e la single-molecule real-time (SMRT) di Pacific Biosciences(5)(PacBio).

La tecnologia a nanopori di Oxford [11] si basa sul passaggio di un singolo filamento di DNA at-traverso un minuscolo foro in una membrana. Quando la molecola passa atat-traverso il nanoporo, altera il campo elettrico nella membrana stessa e la natura dell’alterazione dipende dalla forma del-la molecodel-la. Ciascuna delle quattro basi di DNA determina un’alterazione elettrica caratteristica, perciò è possibile leggere la sequenza di DNA semplicemente analizzando l’alterazione elettrica della membrana mentre il filamento passa attraverso il nanoporo, un nucleotide alla volta. Su un singolo chip si possono creare centinaia di migliaia di nanopori e ciò rende possibile la lettura di molti frammenti di DNA contemporaneamente.

La single-molecule real-time (SMRT) di PacBio [12, 13], invece, è una tecnica di sequenziamento in tempo reale di una singola molecola che utilizza una zero-mode waveguide (ZMW), ossia una struttura fisica (guida d’onda ottica) che guida l’energia luminosa in un volume piccolo e in tutte le dimensioni. Un singolo enzima DNA polimerasi è apposto sul fondo di una ZMW con una singola molecola di DNA come stampo. Lo ZMW è una struttura che crea un volume di osservazione illu-minato abbastanza piccolo da poter esaminare solo un singolo nucleotide di DNA incorporato dalla DNA polimerasi. Ogni base azotata ha attaccato un marcatore fluorescente, di un colore specifico, che si dissocia una volta che nucleotide viene incorporato dalla DNA polimerasi. Un rilevatore cat-tura la fluorescenza emessa dal marcatore, identificando la base azotata secondo la corrispondenza con il colore rilevato.

Entrambe le tecnologie possiedono il vantaggio di sequenziare ed analizzare sequenze con lun-ghezze maggiore, ma i tassi di errore sono dell’ordine del 5-15% e la produttivit`a del campione sia inferiore rispetto alle piattaforme di sequenziamento Illumina[14]. Inoltre, uno degli svantaggi della tecnologia di PacBio `e il suo throughput, ovvero il numero di campioni che possono essere eseguiti sulla piattaforma simultaneamente.

Il primo genoma ad essere stato sequenziato `e quello del batterio Haemophilus influenzae nel

(16)

CAPITOLO 1. Introduzione 1.3. Progetto genoma umano 1995 da C. Venter e dal suo team del The Institute for Genomic Research [15]. L’ostacolo principa-le nel sequenziare interi genomi è la loro dimensione: i genomi dei batteri sono lunghi parecchi milioni di paia di basi, mentre molti genomi eucarioti sono lunghi miliardi di paia di basi e sono distribuiti in decine di cromosomi. Inoltre, per motivi tecnici, il sequenziamento non può iniziare da un’estremità del cromosoma e continuare linearmente fino all’altra estremità, quindi si possono sequenziare di volta in volta solo piccoli frammenti di DNA, di solito non più di 500-700 nucleotidi. Determinare l’intera sequenza di un intero genoma richiede perciò che il DNA venga spezzato in migliaia o milioni di frammenti più piccoli che successivamente possono essere sequenziati e infine sovrapposti. La difficoltà consiste appunto nel porre queste brevi sequenze una di seguito all’altra nel giusto ordine. Ad oggi sono stati usati due diversi approcci per assemblare i brevi segmenti sequenziati in un genoma completo: il sequenziamento basato sulla mappa e il sequenziamento shotgun del genoma.

1.3 Progetto genoma umano

Il Progetto Genoma Umano [5] (Human Genome Project - HGP) `e nato da una collaborazione inter-nazionale con lo scopo di sequenziare l’intero genoma umano, e le cui stime iniziali prevedevano la necessit`a di 15 anni e 3 milioni di dollari per portare a termine l’impresa. Il Progetto Genoma Umano ha avuto inizio ufficialmente nell’ottobre del 1990. Gli sforzi iniziali erano centrati sullo sviluppo di nuovi metodi automatizzati per clonare e sequenziare il DNA e per generare mappe fisiche e genetiche dettagliate di tutto il genoma umano. Si trattava di un progetto finanziato con fondi pubblici che prevedeva la collaborazione di 20 gruppi di ricerca internazionali e di centinaia di ricercatori, associati nel Consorzio per il Sequenziamento del Genoma Umano (IHGSC, Interna-tional human genome sequencing consortium). Per sequenziare il genoma umano, questo gruppo ha adottato una strategia basata sulle mappe.

Nel sequenziamento basato sulle mappe, brevi frammenti sequenziati vengono assemblati nella sequenza del genoma completo, creando prima di tutto mappe fisiche e genetiche dettagliate, che forniscono posizioni note di marcatori genetici per intervalli regolari lungo ciascun cromosoma. Questi marcatori vengono poi utilizzati per facilitare l’allineamento nel giusto ordine dei frammenti sequenziati. Una volta che le mappe genetiche e fisiche sono disponibili, i cromosomi, o larghe porzioni di essi, vengono separati tramite elettroforesi su gel a campo pulsato (PFGE, Pulsed-Field Gel Electrophoresis). Ogni cromosoma viene quindi sottoposto ad una digestione parziale in modo che in ogni molecola di DNA non vengano tagliati tutti i siti di restrizione. Questi siti di restrizione ancora intatti permettono di ottenere una serie di grandi frammenti sovrapponibili di DNA, che vengono poi clonati e posizionati sul cromosoma nell’ordine corretto.

Nel 1998 la società Celera Genomics, guidata da C. Venter, annunciò di voler tentare, con un’i-niziativa privata di sequenziare il genoma umano, utilizzando però l’approccio basato sul sequen-ziamento shotgun, più rapido rispetto a quello basato sulle mappe. Nel sequensequen-ziamento shotgun dell’intero genoma i cloni di piccole dimensioni vengono preparati direttamente dal DNA del ge-noma e sequenziati. Un vantaggio del sequenziamento shotgun consiste nel fatto che i cloni di piccole dimensioni possono essere inseriti nei plasmidi (piccoli filamenti circolari di DNA super-avvolto a doppia elica di ridotte dimensioni), che sono semplici e facili da manipolare. Per essere

(17)

CAPITOLO 1. Introduzione 1.3. Progetto genoma umano ordinati, è necessario che i cloni siano sovrapposti, il che comporta che la maggior parte del geno-ma sia sequenziato molte volte (spesso da 10 e 15). Il numero medio di volte in cui un nucleotide viene sequenziato nel genoma è definito copertura del sequenziamento. Per esempio, copertura 10× significa che ciascun nucleotide è stato sequenziato nel genoma in media 10 volte.

Quando la Celera Genomics ha proposto l’impiego del sequenziamento shotgun per l’analisi del genoma umano non era sicuro se questo metodo avrebbe permesso di assemblare con successo un genoma complesso, costituito da miliardi di paia di basi come quello umano. Oggi, in pratica, tutti i genomi vengono sequenziati utilizzando l’approccio shotgun per l’intero genoma.

Nell’estate del 2000, cinque anni prima del previsto, il progetto pubblico e quello privato annun-ciarono il completamento di una prima bozza che comprendeva la maggior parte della sequenza del genoma umano. Nella primavera del 2003 la sequenza del genoma umano fu dichiarata completata, anche se alcuni vuoti permangono tuttora. Per la maggior parte dei cromosomi la sequenza com-pletata `e precisa al 99,999% [16], con un errore inferiore a un paio di basi ogni 100 000, un livello di precisione superiore all’obiettivo iniziale.

Avere a disposizione la sequenza completa del genoma umano si sta dimostrando di grande uti-lità. La sequenza ha fornito strumenti per osservare e mappare varianti genetiche (tratte nella Sezione 2.1.2), facilitando enormemente la mappatura genica dell’uomo, ovvero il processo con cui i geni vengono attribuiti ai cromosomi e le loro distanze genetiche rispetto a geni più noti vengono determinate. Per esempio, sono stati identificati parecchi milioni di siti in cui gli individui si diffe-renziano per un singolo nucleotide, chiamati polimorfismi di singolo nucleotide (NGS, trattati più nel dettaglio in seguito), siti che sono ampiamente utilizzati negli studi di associazione genomewide per localizzare geni legati all’insorgenza di malattie, o che contribuiscono alla normale diversità umana.

Le NGS, che consentono un sequenziamento rapido ed economico del DNA genomico, vengono utilizzate per rispondere a domande in molti campi. Per esempio, sono stati completamente se-quenziati i genomi di un certo numero di tessuti cancerosi e confrontati con le sequenze di cellule sane della stessa persona, permettendo di catalogare tutte le mutazioni associate alla formazione del tumore e alla progressione del cancro. Il 1 000 Genomes Project (1KGP - Progetto 1 000 genomi) [17–19] consiste nel sequenziare e nel confrontare i genomi di diverse migliaia di individui di diffe-renti popolazioni allo scopo di scoprire nel maggior dettaglio possibile le somiglianze e le differenze fra i membri della specie umana. Il sequenziamento dei genomi completi di genitori e figli, invece, ha consentito di stimare direttamente i tassi di mutazione.

Prima del Progetto Genoma Umano si ipotizzava l’esistenza di 80 000 geni all’interno del genoma Homo sapiens, ognuno dei quali codificava per una singola proteina, ed uno degli obiettivi del HGP era appunto quello di identificare tutti gli 80 000 geni. Solamente al termine del progetto e dall’a-nalisi delle informazioni ottenute è emerso che i geni umani sono “solo” 20 000, ognuno dei quali garantisce la sintesi di più proteine. La discrepanza, tra le aspettative e gli effettivi risultati del pro-getto, non ha permesso una rivoluzione imminente delle pratiche mediche e un’applicazione diretta delle informazioni ottenute cos`ı come si era previsto. Inoltre, anche se la disponibilità di sequenze genomiche complete ha prodotto un numero significativo di risultati positivi, determinando una miglior conoscenza di molte malattie, nella pratica medica questi dati sono ancora poco utilizzati per la cura dei pazienti. Senza dubbio, in futuro l’informazione genetica in medicina sarà

(18)

fonda-CAPITOLO 1. Introduzione 1.4. Banche dati genomiche mentale sia per mettere a punto cure su misura per il singolo paziente (medicina personalizzata), sia per la scoperta di nuovi farmaci.

La conoscenza della sequenza genomica completa, oltre ai numerosi benefici, comporta anche alcune preoccupazioni etiche riguardo il cattivo uso che se ne potrebbe fare. Con le conoscenze ricavate dal sequenziamento genomico saranno identificati molti più geni responsabili di malattie, disturbi, comportamenti e caratteri fisici, favorendo la diffusione di test che possono permettere in qualche modo di prevedere il fenotipo futuro e le condizioni di salute delle persone. La pre-occupazione è che l’informazione derivante dai test genetici possa essere usata per discriminare gli individui portatori di geni che causano malattie o che potrebbero causarle in futuro. Questa preoccupazione negli Stati Uniti è giunta al punto che, con l’approvazione del Genetic Information Nondiscrimination Act, si proibisce agli assicuratori e ai datori di lavoro di fare uso di informazioni genetiche per decidere premi di assicurazione sulla salute e assunzioni.

1.4 Banche dati genomiche

Quante sono le sequenze di DNA ad oggi sequenziate e dove possiamo reperirne i dati? I tre siti principali, coordinati dalla International Nucleotide Sequence Database Collaboration (INSDC), responsabili della memorizzazione dei dati delle sequenze nucleotidiche dal 1982 ad oggi sono: (1) GenBank(6)_{fondato dal National Institutes of Health (NIH) e gestito dal National Center for}

Biotechnology Information (NCBI), negli Stati Uniti d’America; (2) l’European Nucleotide Archive(7) (ENA) gestito dall’European Molecular Biology Laboratory (EMBL) e dall’European Bioinformatics Institute (EBI), nel Regno Unito; (3) il DNA Database of Japan(8)_{(DDBJ) presso il National Institute}

of Genetics (NIG), in Giappone.

INSDC - International Nucleotide Sequence Database Collaboration

ENA - European Nucleotide Archive EMBL - European Molecular

Biology Laboratory GenBank

NCBI - National Center for Biotechnology Information

DDBJ - DNA Data Bank of Japan NIG - National Institute of Genetics

L’International Nucleotide Sequence Database Collaboration (INSDC) consiste appunto in uno sforzo congiunto per raccogliere e diffondere database contenenti sequenze di DNA e RNA. I dati nuovi e aggiornati sulle sequenze nucleotidiche fornite dai gruppi di ricerca a ciascuno dei tre database vengono sincronizzati quotidianamente attraverso l’interazione continua tra il personale di ciascuna delle organizzazioni che collaborano. La sincronizzazione viene mantenuta in base a una serie di linee guida che consistono in una definizione comune delle caratteristiche delle tabelle per i database.

La crescita delle basi sequenziate dal DNA nei database `e mostrata in Figura 1.4. GenBank, ENA e DDBJ accettano dati di sequenza che consistono in genomi completi o incompleti, derivanti da un’analisi con strategia di sequenziamento shotgun dell’intero genoma (Whole-Genome Sequencing

(6)_{Sito web di GenBank - www.ncbi.nlm.nih.gov/genbank/} (7)_{Sito web di ENA - www.ebi.ac.uk/ena/browser/home} (8)_{Sito web di DDBJ - www.ddbj.nig.ac.jp/index-e.html}

(19)

CAPITOLO 1. Introduzione 1.4. Banche dati genomiche 1985 1990 1995 2000 2005 2010 2015 2020 Anno 107 109 1011 1013 1015 1017 Ba si se qu en zia te (s ca la log10 ) GenBank WGS SRA SRA Open Access

Figura 1.4: Crescita delle basi sequenziate dal DNA contenute nei database. In figura vengono riportati: (1) i dati di GenBanka_{, con riferimento alle release comprese tra dicembre 1982 e}

feb-braio 2020; (2) i dati sulle sequenze ottenute dai progetti di sequenziamento shotgun dell’intero genoma (WGS), iniziati nel 2002; e (3) i dati derivanti dal Sequence Read Archive (SRA)b_,

inclu-dendo sia le basi totali che il sottoinsieme di basi con accesso pubblico contenute nelle release dal maggio 2007 a febbraio 2021.

a_{Le statistiche delle release di GenBank e WGS sono state ricavate dal sito www.ncbi.nlm.nih.gov/genbank/statistics/.} b_{Le statistiche delle Sequence Read Archive (SRA) sono state ricavate dal sito https://trace.ncbi.nlm.nih.gov/Traces/sra/.}

- WGS). La divisione WGS consiste in sequenze generate attraverso sequenziamenti con alto rendi-mento e le sequenze WGS sono disponibili dal 2002, ma non vengono sono considerate parte delle release di GenBank, ENA e DDBJ. Il grafico di Figura 1.4 rivela inoltre che il Sequence Read Archive (SRA) contiene molti più dati di sequenziamento rispetto alla somma dei dati di GenBank e WGS. L’SRA fa sempre parte dell’INSDC, ed è l’archivio principale di NIH dei dati di sequenziamento ad alto rendimento. I dati grezzi di sequenziamento e le informazioni di allineamento archiviate deri-vano da piattaforme NGS, come Illumina Genome Analyzer. Ogni sequenza di SRA è relativamente breve, riflettendo la particolarità delle tecnologie di sequenziamento di ultima generazione. Infine, per la maggior parte dei dati di SRA è permesso l’accesso pubblico, mentre per il resto dei dati è necessario richiedere un permesso specifico aderendo a specifiche linee guida relative all’etica sul-l’utilizzo di dati a cui si vuole accedere. Si consideri che le 5, 1 × 1016_{basi sequenziate nella release}

corrente (febbraio 2021) di SRA corrispondono a 1, 8 × 1016_{byte di dati.}

Negli ultimi anni, sempre più progetti ed iniziative si stanno spingendo verso l’utilizzo del se-quenziamento dell’intero genoma, e di conseguenza verso lo studio dei suoi risultati. Ad esempio, GenomeTrakr è la prima rete distribuita di laboratori a utilizzare il WGS per l’identificazione dei patogeni. La rete è costituita da laboratori di sanità pubblica e universitari che raccolgono e con-dividono dati genomici e geografici da patogeni di origine alimentare. I dati, che sono ospitati in database pubblici presso l’NCBI, possono essere consultati da ricercatori e funzionari della sanità pubblica per confronti e analisi in tempo reale che promettono di accelerare le indagini su epidemie di malattie di origine alimentare e ridurre malattie e decessi di origine alimentare.

Questi database pubblici vengono utilizzati in varie applicazioni, ad esempio per rilevare le va-riazioni genetiche all’interno degli individui, determinare la storia evolutiva all’interno di una po-polazione e assemblare i genomi di nuove specie o geni. Specifiche operazioni all’interno di questi database di grandi dimensioni sono fondamentali per le applicazioni appena citate, tuttavia tali

(20)

CAPITOLO 1. Introduzione 1.4. Banche dati genomiche calcoli devono considerare il fatto che la scansione ripetuta di questi database, anche compressi, non è fattibile. Solitamente, per rimediare si cerca di utilizzare indici creati a partire dai dati conte-nuti nel database. Molti degli indici popolari in bioinformatica sono basati sulla Burrows-Wheeler Transform (BWT) (trattata in seguito) e sono stati pubblicati numerosi articoli sulla creazione della BWT per database genomici. In ogni caso, con le tecniche e le tecnologie attuali, risulta ancora oggi una sfida elaborare qualcosa partendo da poco più di un terabyte di dati grezzi a causa della difficoltà di lavorare sulla memoria esterna. Con lo scopo di trovare una soluzione che permetta di superare questa sfida, il Capitolo 3 vuole gettare le basi dell’informatica, con alcune strutture dati ed algoritmi, che sono solitamente applicati per risolvere specifici problemi biologici.

(21)

CAPITOLO

2

Background Biologico

2.1 Le mutazioni del DNA

Il DNA è una molecola molto stabile che si replica con sorprendente accuratezza, ma mutazioni nella struttura del DNA ed errori di replicazione possono sempre verificarsi. Definiamo mutazione una modifica dell’informazione genetica che viene trasmessa ereditariamente da cellule o da or-ganismi. Numerosi studi di genetica attuali si concentrano difatti su come vengono ereditate le varianti prodotte per mutazione. Le mutazioni possono, allo stesso tempo, contribuire a mantenere la varietà tra gli individui, in quanto sono alla base sia della capacità degli organismi di adattarsi ai mutamenti ambientali, ma anche causare grandi sofferenze, essendo all’origine degli effetti nocivi di molte malattie.

Negli organismi multicellulari possiamo distinguere fra due grandi categorie di mutazioni: le mutazioni somatiche e quelle della linea germinale.

Le mutazioni somatiche sono quelle che avvengono nei tessuti somatici che non producono ga-meti. Quando una cellula somatica con una mutazione si divide (mitosi(9)_{), la mutazione viene}

trasmessa alle cellule figlie; quindi, quanto prima nello sviluppo si verifica una mutazione somati-ca, tanto più saranno i cloni contenenti la mutazione. Di solito una mutazione si verifica una volta ogni milione di divisioni cellulari, perciò in ogni individuo si verificano centinaia di milioni di mu-tazioni somatiche. Molte di queste non hanno effetti evidenti sul fenotipo dell’organismo, poiché la funzione della cellula mutante è sostituita da quella delle cellule normali. Tuttavia, cellule con una mutazione somatica che ne stimola la divisione possono crescere di numero e diffondersi; questo tipo di mutazione è all’origine dei tumori.

Le mutazioni della linea germinale sono invece quelle che si verificano nelle cellule che produ-cono gameti. Una mutazione della linea germinale pu`o essere trasmessa alle generazioni future,

(9)_{La mitosi `e un processo che consiste in una singola divisione nucleare, di solito accompagnata da un’unica divisione}

cellulare, a seguito della quale il numero dei cromosomi nelle nuove cellule `e uguale a quello della cellula originale. La mitosi produce cellule geneticamente identiche.

(22)

CAPITOLO 2. Background Biologico 2.1. Le mutazioni del DNA dando origine a organismi che contengono la mutazione in tutte le cellule somatiche e della linea germinale. Quando parliamo di mutazioni in organismi cellulari, intendiamo di solito mutazioni della linea germinale.

Storicamente le mutazioni sono state divise in quelle che influiscono su numero o struttura dei cromosomi, chiamate mutazioni cromosomiche, e quelle che influenzano un singolo gene, chiamate mutazioni geniche. Venne stabilita questa distinzione avvenne poich´e le mutazioni cromosomiche potevano essere osservate direttamente, esaminando i cromosomi con un microscopio, mentre le mutazioni geniche erano osservabili solo nei loro effetti fenotipici. Oggi, il sequenziamento del DNA permette l’osservazione diretta delle mutazioni geniche, e le mutazioni cromosomiche sono distinte da queste ultime in base alle dimensioni della lesione del DNA. `E pratico utilizzare il ter-mine mutazione cromosomica per una alterazione genetica su larga scala che influenza la struttura cromosomica o il numero di cromosomi, e usare invece il termine mutazione genica per una lesione del DNA che influenza un unico gene.

2.1.1 Mutazioni cromosomiche

Le mutazioni cromosomiche, o riarrangiamenti cromosomici, sono mutazioni che cambiano le strut-ture dei singoli cromosomi e i quattro tipi fondamentali sono le duplicazioni, le delezioni, le inver-sioni e le traslocazioni. Le variazioni messe in evidenza dagli studi sulle mutazioni cromosomiche sono dette variazioni del numero di copie (CNV - Copy Number Variation).

Duplicazioni. La duplicazione cromosomica è una mutazione in cui una porzione del cromoso-ma è stata raddoppiata (Figura 2.1(a)). Nel caso in cui la regione duplicata è immediatamente adiacente al segmento originale si chiama duplicazione in tandem; se invece si trova a una certa distanza da quello originale, sullo stesso cromosoma o su un altro, prende il nome di duplicazio-ne con spostamento. Una duplicazioduplicazio-ne può avvenire manteduplicazio-nendo lo stesso orientamento della sequenza originale oppure invertendolo, prendendo il nome di duplicazione inversa.

Le duplicazioni possono mostrare notevoli effetti sul fenotipo. Una delle patologie associata alla duplicazione cromosomica `e la sindrome di Rett, una grave malattia neurologica, che causa gravi ritardi nell’acquisizione del linguaggio e della coordinazione motoria.

(a) Duplicazioni (b) Delezioni (c) Inversioni (d) Traslocazioni

(23)

CAPITOLO 2. Background Biologico 2.1. Le mutazioni del DNA Delezioni. La delezione cromosomica consiste nella perdita di un segmento cromosomico (Figu-ra 2.1(b)). Delezioni estese possono essere scoperte perch´e il cromosoma risulta visibilmente accorciato.

Nell’uomo una delezione sul braccio corto del cromosoma 5 `e responsabile della sindrome cri-du-chat (dal francese “lamento del gatto”, suono a cui viene associato il pianto dei neonati affetti da tale sindrome), i cui effetti sono una testa piccola, occhi molto distanziati fra loro e un ritardo mentale.

Inversioni. Nell’inversione cromosomica si ha quando un segmento di un cromosoma viene in-vertito, cio`e ruotato di 180◦_{(Figura 2.1(c)). Perch´e possa verificarsi un’inversione, il cromosoma}

deve spezzarsi in due punti. Le inversioni che non includono il centromero sono dette inversio-ni paracentriche, mentre quelle che includono il centromero sono dette inversioinversio-ni pericentriche. Gli organismi che hanno subito delle inversioni non hanno perso né guadagnato materiale ge-netico; si è solo alterata la loro sequenza di DNA. Ciò nonostante queste mutazioni producono marcati effetti fenotipici, in quanto la regolazione di molti geni dipende dalla loro posizione. Traslocazioni. Una traslocazione comporta lo spostamento di materiale genetico fra cromosomi

non omologhi (Figura 2.1(d)) o all’interno dello stesso cromosoma. La traslocazione non deve essere confusa con il crossing-over, in cui ha luogo uno scambio di materiale genetico fra cro-mosomi omologhi. Se il materiale genetico si sposta solo da un cromosoma ad un altro, si dice traslocazione non reciproca, mentre se lo spostamento `e in entrambi i sensi, si ha una trasloca-zione reciproca.

Particolari traslocazioni possono causare ai soggetti affetti un’alta probabilit`a di generare figli soggetti alla sindrome di Down, oppure disturbi come il cancro e l’infertilit`a.

I riarrangiamenti cromosomici sono stati scoperti attraverso esami visivi della dimensione ge-nerale dei cromosomi oppure del loro comportamento durante la meiosi. Tuttavia il microscopio pu`o rivelare solo grandi mutazioni cromosomiche (di almeno 5 milioni di paia di basi), e solamen-te al solamen-termine del HGP, le informazioni dettagliasolamen-te relative a singoli cromosomi, hanno permesso ai genetisti di esaminare il numero di copie di specifiche sequenze di DNA e scoprire ulteriori riarrangiamenti cromosomici che sfuggono al microscopio.

2.1.2 Mutazioni geniche

Esistono molti schemi di classificazione per le mutazioni geniche, alcuni basati sulla natura dell’ef-fetto fenotipico, altri sull’agente causale della mutazione e altri ancora sulla natura molecolare del difetto. Di seguito si classificano le mutazioni prevalentemente in base alla loro natura molecolare. Le principali mutazioni geniche sono le sostituzioni, le inserzioni/delezioni, l’espansioni delle ripeti-zioni nucleotidiche e i polimorfismi a singolo nucleotide (trattati pi`u approfonditamente essendo una delle forme di mutazioni pi`u studiate ad oggi).

Sostituzioni. Il tipo più semplice di mutazione genica è la sostituzione di basi, ossia l’alterazione di un singolo nucleotide nel DNA. Esistono due tipi di sostituzioni di basi: le transizioni e le trasversioni. Nella transizione, una purina (A o G) viene sostituita da una purina diversa o, in alternativa, una pirimidina (C o T) è sostituita da una pirimidina diversa. Nella trasversione una purina è sostituita da una pirimidina o una pirimidina da una purina. Il numero di possibili

(24)

CAPITOLO 2. Background Biologico 2.1. Le mutazioni del DNA trasversioni è il doppio del numero di possibili transizioni, ma le transizioni si verificano più frequentemente perché la trasformazione di una purina (risp. pirimidina) in una purina (risp. pirimidina) diversa è più comune della trasformazione di una purina (risp. pirimidina) in una pirimidina (risp. purina).

Adenina Citosina Guanina Timina Transizioni Trasversioni

Figura 2.2: Sostituzioni geniche: le transizioni e le trasversioni.

Inserzioni/delezioni. Nelle inserzioni e le delezioni, chiamate collettivamente mutazioni indel, si ha l’aggiunta o la rimozione di una o più coppie di nucleotidi. Anche se la sostituzione di basi viene spesso considerata come il tipo più comune di mutazione, l’analisi molecolare ha rivelato che le indel sono più frequenti. Questo tipo di eventi all’interno di sequenze che codificano per proteine possono portare a mutazioni frameshift, che modifica la fase di lettura di un gene. Le mutazioni frameshift generalmente alterano tutti gli amminoacidi la cui codifica inizia da nucleotidi antecedenti al punto in cui è avvenuta la mutazione. Le mutazioni di questo tipo possono causare la terminazione precoce della sintesi proteica. Nel caso in cui le indel sono a multipli di tre nucleotidi e lasciano intatta la fase di lettura non si ha una mutazione frameshift; anche se l’aggiunta o la rimozione di uno o più amminoacidi può comunque influire sul fenotipo. Espansioni delle ripetizioni nucleotidiche. Le espansioni delle ripetizioni nucleotidiche so-no mutazioni in cui aumenta il numero di copie di un insieme di nucleotidi adiacenti. Questa tipologia di mutazione è stata individuata in almeno 30 malattie umane e nonostante la mag-gior parte di esse è causata dall’espansione di un insieme di tre nucleotidi, altre sono associate persino a ripetizioni di dodici nucleotidi. L’associazione fra il numero di copie di ripetizio-ni nucleotidiche, la gravità della malattia e la probabilità di espansione porta a un fenomeno conosciuto come anticipazione, nel quale i sintomi delle malattie causate da espansioni di ripe-tizioni nucleotidiche diventano più gravi e precoci con il passare delle generazioni.

L’aumento del numero di queste ripetizioni pu`o produrre sintomi di malattia in modi diversi, come la produzione di una proteina tossica che presenta copie aggiuntive di glutammina (l’am-minoacido codificato da CAG) nel morbo di Huntington, oppure il blocco della trascrizione di un gene essenziale nella sindrome dell’X fragile (la “X” fa riferimento al cromosoma omonimo).

Polimorfismi a singolo nucleotide

Fin dal momento in cui `e stato completato il sequenziamento del genoma umano, molti sforzi si sono concentrati sulla mappatura delle differenze fra le sequenze genomiche di individui diversi. Nel genoma, i siti in cui si osservano differenze in una singola base fra individui della stessa specie sono chiamati polimorfismi di singolo nucleotide (SNP, dall’inglese Single Nucletide Polimorphism e pronunciati “snip”). Dal momento che hanno origine da mutazioni, gli SNP vengono ereditati come

(25)

CAPITOLO 2. Background Biologico 2.1. Le mutazioni del DNA varianti alleliche. Gli SNP sono numerosi e sono largamente presenti nei genomi, più precisamente sono varianti di singolo nucleotide (SNV, dall’inglese Single Nucletide Variants) che si verificano in più dell’1% della popolazione. Nell’uomo, confrontando lo stesso cromosoma di due individui differenti si può trovare uno SNP all’incirca ogni 1 000 bp.

La maggior parte degli SNP presenti nelle popolazioni hanno avuto origine in passato da una sin-gola mutazione che si è verificata su un particolare cromosoma, e che in seguito si è diffusa nella popolazione. L’insieme specifico di SNP e altre varianti genetiche osservate su un singolo cromo-soma o su una parte di un cromocromo-soma, prende il nome di aplotipo (Figura 2.3). Gli SNP presenti nello stesso aplotipo sono fisicamente associati e per questo tendono ad essere trasmessi insieme. Nuovi aplotipi possono avere origine attraverso mutazione, oppure in seguito a un crossing-over (processo che determina la ricombinazione rompendo l’associazione fra geni che si trovano vicini sullo stesso cromosoma), che separa quello specifico insieme di SNP contenuti nell’aplotipo. Poiché la frequenza di crossing-over è proporzionale alle distanze fra i geni, gli SNP e le altre varianti ge-netiche che sono localizzate insieme e si trovano vicine sul cromosoma, risulteranno strettamente associate negli aplotipi. L’associazione non casuale tra varianti geniche in un aplotipo è chiamata linkage disequilibrium. Sono noti oltre cento milioni di SNP nella popolazione umana ma, a cau-sa del linkage disequilibrium, questi SNPNP in realtà formano un numero molto più piccolo di aplotipi. Perciò, per identificare la maggior parte degli aplotipi umani basta studiare un numero relativamente piccolo di polimorfismi a singolo nucleotide.

1a AACACGCCA...TTCGGGGTC...AGTCGACCG...

1b AACACGCCA...TTCGAGGTC...AGTCAACCG...

1c AACATGCCA...TTCGGGGTC...AGTCAACCG...

1d AACACGCCA...TTCGGGGTC...AGTCAACCG...

a C G G b C A A c T G A d C G A SNP SNP SNP Cromosoma Aplotipo

Figura 2.3: Un aplotipo `e una serie specifica di SNP e di altre varianti genetiche osservate in un singolo cromosoma o su una parte di cromosoma.

A causa della loro variabilità e della loro larga diffusione su tutto il genoma, gli SNP sono preziosi come marcatori negli studi di linkage. Quando uno SNP si trova in prossimità di una posizione responsabile di una specifica malattia, tenderà a essere ereditato insieme all’allele che provoca la malattia. Dal momento in cui gli individui malati e quelli sani hanno degli SNP diversi, un confronto tra gli aplotipi SNP negli individui con la malattia e negli individui sani può rivelare la presenza di geni coinvolti all’origine della malattia stessa. Pertanto, si può determinare la localizzazione del gene che causa la malattia partendo dalla localizzazione degli SNP associati.

Un progetto di ricerca internazionale, chiamato International HapMap Project [20], `e stato avvia-to nel 2002 con lo scopo di catalogare e mappare gli SNP e le altre varianti genetiche che potrebbero essere utilizzate per identificare aplotipi comuni nelle popolazioni umane. La prima fase del pro-getto, completata nel 2005, ha catalogato pi`u di un milione di SNP nei genomi di 269 individui provenienti da diverse popolazioni umane (africani, giapponesi, cinesi ed europei). Questi SNP so-no diffusi in tutti i 23 cromosomi umani, separati fra loro da distanze di circa 5 000 bp. La seconda fase del progetto, completata nel 2006, ha catalogato un totale di 4,6 milioni di SNP.

(26)

CAPITOLO 2. Background Biologico 2.2. Processo di identificazione delle mutazioni del DNA La maggior parte degli alleli degli SNPNP comuni si trovano in tutte e quattro le popolazioni, sebbene a frequenze alleliche significativamente diverse. La più grande diversità degli SNP si trova negli africani e ciò è coerente con molti altri studi che sostengono che l’inizio dell’evoluzione umana vada collocato in Africa. I dati ottenuti dal Progetto HapMap hanno fornito importanti informazioni circa la funzione e l’evoluzione del genoma umano.

Molte malattie comuni sono causate da interazioni complesse fra molti geni: la disponibilit`a de-gli SNP ha notevolmente facilitato la ricerca di questi geni. In un’applicazione di SNP finalizzata alla scoperta di geni associati a malattie, i ricercatori nel 2007 hanno genotipizzato 17 000 persone nel Regno Unito per 500 000 SNP [21]. Lo studio ha condotto i ricercatori alla scoperta di un’asso-ciazioni fra 24 geni, o segmenti cromosomici, alla base di sette malattie comuni fra cui il morbo di Crohn, l’artrite reumatoide, il disturbo bipolare, l’ipertensione e due tipi di diabete. L’importanza di questa ricerca consiste nella dimostrazione che gli studi di associazione genomewide basati su SNP possono localizzare con successo i geni che concorrono all’insorgenza di malattie complesse, causate da molteplici fattori genetici e ambientali.

Negli ultimi cinque anni gli SNP sono stati utilizzati con successo in differenti studi di associa-zione genomewide con lo scopo di localizzare i geni che possono influenzare molti altri caratteri, come l’età della pubertà e della menopausa nelle donne, la forma dei lineamenti del viso, la pig-mentazione della pelle, il colore degli occhi, il peso corporeo, la densità ossea, il glaucoma e perfino la predisposizione a malattie infettive come la meningite e la tubercolosi. I geni identificati da-gli attuali studi di associazione genomewide, spesso descrivono solo una piccola parte dell’effetto genetico sui caratteri, risultando di per sé non utilizzabili per predire con sicurezza il rischio di ereditare una malattia o un determinato carattere. Nonostante ciò, l’identificazione di geni speci-fici che influenzano una malattia o un carattere può determinare una migliore comprensione dei processi biologici che producono il fenotipo.

2.2 Processo di identificazione delle mutazioni del DNA

Per gli studenti di oggi è facile credere che la bioinformatica moderna sia emersa recentemente per assistere l’analisi dei dati di sequenziamento di nuova generazione. Tuttavia, la bioinforma-tica ha avuto inizio più di 50 anni fa, quando i computer erano ancora un’ipotesi e il DNA non poteva ancora essere sequenziato. Le basi della bioinformatica furono gettate all’inizio degli anni ’60 con l’applicazione di metodi computazionali all’analisi di sequenze proteiche. A seguito della progettazione di computer più potenti e lo sviluppo di software più adatti alle attività di bioin-formatica, il sequenziamento del DNA, l’analisi dei processi biologici e lo studio delle mutazioni sono divenute attività sempre più presenti. Negli anni ’90, la combinazione dei notevoli migliora-menti nella tecnologia di sequenziamento e la riduzione dei costi, hanno dato luogo a un aumento esponenziale dei dati. Ad oggi sono state poste nuove sfide in termini di gestione, elaborazione e data mining dell’enorme quantità di dati generati non solo dal sequenziamento del DNA, ma anche dall’assemblaggio del genoma, dall’allineamento di sequenze e dal processo di variant calling.

Quando le tecniche di NGS vengono eseguite su un genoma precedentemente assemblato, viene eseguito l’allineamento al genoma di riferimento, il quale deve essere gi`a stato precedentemente assemblato. Mentre, quando sequenziamo il genoma di una specie che non `e stata

(27)

precedentemen-CAPITOLO 2. Background Biologico 2.2. Processo di identificazione delle mutazioni del DNA te caratterizzata, `e richiesto l’assemblaggio de novo (“da nuovo”). Con variant calling si intende invece il processo di analisi che (solitamente) segue la fase di allineamento e il cui scopo `e quello di identificazione le varianti associate a un individuo, o a una popolazione.

2.2.1 Assemblaggio del genoma

L’assemblaggio dell’intero genoma comporta la frammentazione del DNA genomico di un organi-smo, per la successiva costruzione di librerie di varie dimensioni ed infine l’allineamento del ge-noma stesso. Man mano che le letture sono allineate, vengono organizzate in contig, ossia insiemi di segmenti di DNA sovrapposti che rappresentano una regione di consensus (consenso) del DNA. La sequenza di consensus `e l’ordine calcolato dei residui pi`u frequenti, nucleotidi o amminoacidi, trovati in ciascuna posizione in un allineamento di sequenza.

Due metodi principali sono usati dagli assemblatori: l’approccio dei grafi di sovrapposizione (overlap) e quello dei grafi di de Bruijn. Un grafo di sovrapposizione rappresenta ogni read (sequen-za letta) come un nodo e gli archi corrispondono alle sovrapposizioni (Figura 2.4(b)) dei caratteri nei read. Gli archi sono transitivi, ossia le sovrapposizioni pi`u grandi possono comprendere un insieme di sovrapposizioni pi`u brevi; gli assemblatori che utilizzano questo approccio eseguono allineamenti a coppie di tutte i read per determinare la sovrapposizione.

In un grafo di de Bruijn, invece, le sequenze sono tutte suddivise in stringhe (“𝑘-meri”) di una lun-ghezza fissa 𝑘 (Figura 2.4(c)). Ogni nodo corrisponde a un 𝑘-mero e un arco (diretto) separa una coppia di 𝑘-meri se si ha una perfetta sovrapposizione di 𝑘 − 1 nucleotidi e il (𝑘 + 1)-mero corri-spondente alla concatenazione dei due nodi `e presente nell’insieme dei read (solitamente con una frequenza minima prefissata). L’assemblaggio del genoma corrisponde a un percorso attraverso i nodi e gli assemblatori lo perfezionano, ad esempio, rifiutato percorsi che non raggiungono una soglia minima della copertura di lettura. L’approccio del grafo di de Bruijn `e particolarmente utile nell’assemblaggio del DNA con regioni ripetitive, come accade comunemente negli eucarioti.

1 ACCTGATC 2 CTGATCAA 3 ACCTGATCAAT 4 AGCGATCA 5 CGATCAAT 6 GATCAATG 7 TCAATGTG 8 CAATGTGA (a) Read. 1 2 3 4 5 6 7 8

(b) Allineamento con grafo di sovrapposizione.

ACCTG CCTGA CTGAT TGATC

AGCGA GCGAT CGATC

GATCA ATCAA TCAAT CAATG AATGT ATGTG TGTGA

(c) Allineamento tramite grafo di de Bruijn.

Figura 2.4: Metodi di assemblaggio del genoma per read corti. (a) Esempio di 8 read allineati (notare che i read 4 e 5 hanno un match parziale sui read 1-3) in cui i nucleotidi colorati sono uguali per le sequenze allineate. (b) Rappresenta una soluzione dell’assmblaggio tramite un grafo di sovrapposizione in cui le sovrapposizioni sono di almeno 5 basi (𝑘 = 5). (c) Mostra l’assemblaggio attraverso un grafo di de Bruijn in cui i read vengono suddivisi in stringhe di 5 nucleotidi (𝑘-meri con 𝑘 = 5).

(28)

CAPITOLO 2. Background Biologico 2.2. Processo di identificazione delle mutazioni del DNA L’assemblaggio del genoma è facilitato da letture di sequenziamento più lunghe. La Figura 2.5, ottenuta da uno studio svolto da Koren et al. [22], mostra tre grafi di de Bruijn per l’assemblaggio del genoma di Escherichia coli da 4, 2 megabasi. A 𝑘 = 50 il grafo è decisamente intricato; a 𝑘 = 1 000 è notevolmente semplificato; e per 𝑘 = 5 000 il grafo è completamente risolto in un unico contig che racchiude l’intero genoma. I ricercatori sono stati in gradi di produrre un valore 𝑘 cos`ı grande grazie al tecniche di sequenziamento a lunga lettura di PacBio.

(a) 𝑘 = 50

(b) 𝑘 = 1 000

(c) 𝑘 = 5 000

Figura 2.5: Assemblaggio del genoma di Escherichia coli con il metodo dei grafi di de Bruijn per differenti valori di 𝑘. L’immagine `e stata ottenuta dallo studio di Koren et al. [22].

2.2.2 Allineamento di sequenze

Quando sequenziamo un singolo genoma umano aploide, che ha circa 3 miliardi di basi di DNA, è necessario avere un’adeguata profondità di copertura (come una ridondanza media di 30 volte per ciascuna base) sia per ottenere un’affidabile identificazione delle basi, che per sopperire alla non uniformità della distribuzione delle letture nel genoma. Generalmente, il genoma di riferimento, su cui vengono allineate le sequenze, è disponibile in un formato FASTA(10)_{e l’output desiderato}

dall’allineamento è un insieme di coordinate genomiche per ogni read. Una sfida è che i read sono spesso brevi (< 100 − 400 bp, a seconda della tecnologia) e possono quindi allinearsi a più posizioni genomiche. Ci sono spesso regioni ripetitive e ogni allineatore deve adottare una strategia per assegnare posizioni genomiche. Infine ogni genoma può avere delle Single Nucletide Variants (SNV), dovute anche da errori tecnici, e ogni tecnologia ha un certo tasso di errore che complica l’allineamento.

Due dei principali approcci all’allineamento di sequenze sono quello basato su tabelle hash e quello sulla Burrows-Wheeler Transform (BWT), entrambi consideranti due input: un genoma di riferimento e un’ampia serie di brevi read.

Nell’indicizzazione attraverso la tabella hash le posizioni dei 𝑘-meri del genoma vengono memo-rizzate in una tabella hash, successivamente scansionata per creare delle corrispondenze esatte con i cosiddetti seed, 𝑘-meri estratti dai read utilizzando la programmazione dinamica. Uno dei primi programmi a utilizzare questo approccio `e stato MAQ [23]; il quale crea pi`u tabelle hash per indi-cizzare i read, ed esegue la scansione del database di riferimento con le tabelle hash per identificare

(10)_{Il formato FASTA `e un formato basato su testo per rappresentare sequenze nucleotidiche o sequenze di amminoacidi}

(proteine), in cui i residui sono rappresentati utilizzando codici a una sola lettera. Il formato proviene dal pacchetto software FASTA, ma ora `e diventato uno standard quasi universale nel campo della bioinformatica.

(29)

CAPITOLO 2. Background Biologico 2.2. Processo di identificazione delle mutazioni del DNA i risultati. Una delle limitazioni degli strumenti che utilizzano questo approccio `e per`o la possibile richiesta di decine di gigabyte di memoria per memorizzare le letture indicizzate.

La seconda tipologia di allineatori utilizzano la Burrows-Wheeler Transform (BWT) per com-primere la sequenza del genoma di riferimento, permettendo cos`ı di indicizzare un genoma di riferimento grande quanto il genoma umano in meno di 2 Gb di memoria. Data una stringa di caratteri, viene costruita una matrice ordinata lessicograficamente in cui ogni riga corrisponde a una rotazione della sequenza. Questa matrice può essere compressa efficacemente e può essere ri-costruita utilizzando solo le informazioni nelle stringhe ottenute dalla concatenazione dei caratteri della prima e dell’ultima colonna (la BWT sarà approfondita nel Capitolo 3). Due degli allineato-ri più popolaallineato-ri, che utilizzano l’indicizzazione con la BWT, sono BWA e Bowtie2. BWA utilizza BWA-backtrack per letture di sequenza breve (fino a 100 coppie di basi), mentre BWA-MEM è più preciso per letture più lunghe. Bowtie2 è invece un allineatore ultraveloce ed efficiente in termini di memoria; si consideri che Bowtie è 30 volte più veloce di MAQ. Sia BWA che Bowtie prendono in considerazione le lunghezze dei read, i tassi di errore di sequenziamento e l’allineamento locale rispetto a quello globale(11)_{dei read.}

2.2.3 Variant Calling

Come precedentemente accennato, con il termine variant calling si intende il processo di analisi delle sequenze con l’obiettivo di identificare le variazioni. Solitamente la procedura di analisi, a seguito di un sequenziamento, inizia con una mappatura dei read su un genoma di riferimento mediante uno strumento di allineamento per poi evidenziare le basi che differiscono dal riferimento. Uno dei workflow più utilizzati per l’analisi delle sequenze NGS coinvolge l’utilizzo del Genome Analysis Toolkit (GATK). GATK indicizza il genoma di riferimento attraverso la BWT e prima di eseguire l’allineamento include i metadati del sequenziamento (come il nome di ciascun campione di DNA o altre informazioni), cos`ı da garantirgli la capacità di effettuare la variant calling con elevata sensibilità e specificità.

La procedura di allineamento delle sequenze, oltre ad essere soggetta ad errori e perdite di da-ti, richiede del tempo e può essere irrealizzabile nel caso in cui un genoma di riferimento non è disponibile. Per queste ragioni sta crescendo l’interesse verso metodi di variant calling che elabo-rano direttamente i dai grezzi [24], senza la necessità di un genoma di riferimento (reference-free) e senza effettuare l’operazione di assemblaggio delle sequenze (assembly-free). Uno dei metodi con performance più elevate è DiscoSNP++ [25, 26], in grado di rilevare SNP isolati da una collezione di read, senza un genoma di riferimento e con una richiesta di memoria e tempo molto bassa. Rispetto alla ricerca di SNP isolati che utilizzano un approccio di assemblaggio e mappatura all’avanguardia, DiscoSNP++ richiede risorse di calcolo significativamente inferiori, mostrando valori di precisione simili e le previsioni classificate hanno una probabilità ridotta di essere falsi positivi.

In particolare, DiscoSNP++ `e una pipeline, di diversi tool indipendenti, in cui nella prima fase co-struisce il grafo di de Bruijn della collezione di dati in input, tenendo conto sia della dimensione dei 𝑘-meri che della copertura minima 𝑐, e rimuovendo i 𝑘-meri ritenuti errati in base alla loro frequen-za. Il passo successivo ha lo scopo di rilevare le cosiddette “bolle”, definite nel paragrafo successivo,

(11)_{L’allineamento globale `e un’ottimizzazione che cerca di estendere l’appaiamento delle basi lungo le intere sequenze,}

mentre l’allineamento locale cerca di identificare regioni di similarit`a all’interno di sequenze che possono essere molto diverse.

(30)

CAPITOLO 2. Background Biologico 2.2. Processo di identificazione delle mutazioni del DNA generate nel grafo dalla presenza di SNP e INDEL, generando infine un file FASTA contenente le sequenze contenenti le varianti individuate. Il passaggio seguente mappa i read della collezione in input sulle sequenze contenenti le varianti, al fine di determinare la copertura di lettura; mentre l’ultimo modulo genera un file VCF(12)delle varianti individuate. Nel caso in cui non sia disponibile il genoma di riferimento, la pipeline semplifica gli ultimi passaggi variando il formato da del file FASTA al formato del file VCF.

La maggior parte degli strumenti che condividono il concetto di operare direttamente sui dati grezzi utilizzano un grafo di de Bruijn dei 𝑘-meri dei read [24, 27]. Questo approccio ha il vantag-gio di includere diverse caratteristiche biologiche direttamente all’interno della sua struttura. Pi`u precisamente, la rilevazione e l’analisi delle cosiddette “bolle” [28] (bubble, vedi Figura 2.6) nel gra-fo, ossia coppie di percorsi disgiunti che condividono lo stesso nodo sorgente e nodo destinazione, permettono di identificare varianti come SNP, INDEL oppure errori di sequenziamento. Di contro per`o, le rappresentazioni con i grafi di de Bruijn hanno lo svantaggio della decisione del parametro 𝑘, e, di conseguenza, la limitazione a considerare solo 𝑘-meri piuttosto che l’effettiva collezione dei read. Informazioni sulla copertura di ogni 𝑘-mero o sull’appartenenza di due 𝑘-meri allo stesso read (e quindi adiacenti nel genoma) vengono quindi perse.

La limitazione causata dai 𝑘-meri e dalla scelta del parametro 𝑘 `e presente anche in tool dove i 𝑘-meri vengono indicizzati, come nei Gk-arrays dedicati a query su un’ampia raccolta di read pro-dotti da sequenziatori ad alto rendimento; e nei metodi che utilizzano strutture dati basate sugli array dei suffissi come PgSA [29], in grado di contare e localizzare 𝑘-meri, di dimensione variabile, nei read di sequenziamento attraverso una struttura “leggera”.

L’utilizzo invece di un metodo di indicizzazione basato sulla BWT per le collezioni di read ha il vantaggio di essere allo stesso tempo facilmente comprimibile ed evita la perdita di dati, gli indi-ci derivanti dalla BWT supportano query di 𝑘-meri senza la necessit`a di costruire inidiindi-ci diversi per valori diversi di 𝑘. Grazie all’estensione della BWT [30, 31], denominata extended Burrows-Wheeler Transform (eBWT), `e possibile operare su raccolte di stringhe derivanti da sequenziamenti WGS (Whole-Genome Sequencing).

CATCT

ATCTA TCTAC CTACG TACGC ACGCA ATCTC TCTCC CTCCG TCCGC CCGCA

CGCAG

Figura 2.6: Esempio di una “bolla” nel grafo di de Bruijn. La bolla `e stata generata da un polimorfismo a singolo nucleotide (evidenziato con i colori) presente nei read di esempio . . . CATCTACGCACGCAG. . . e . . . CATCTCCGCACGCAG. . . . I due read condividono il nodo sorgente CATCT e il nodo destinazione CGCAG.

(12)_{Il Variant Call Format (VCF) `e un formato di file testuale di tipo tab-separated usato in bioinformatica per permette di}