Ricerca di bubbles nei grafi di de Bruijn e applicazione all'analisi di RNA-seq data

Università degli studi di Pisa

TESI DI LAUREA

Ricerca di bubbles nei grafi di

de Bruijn ed applicazione

all’analisi di dati RNA-seq

Relatore:

Nadia Pisanti

Autore:

Paolo Cois

Sessione di laurea 12 Ottobre 2012 Anno Accademico 2011/2012

1 Introduzione 6

1.1 Obiettivi . . . 7

1.2 Schema della tesi . . . 8

2 Nozioni preliminari 10 2.1 Richiami di Biologia . . . 10

2.1.1 DNA . . . 10

2.1.2 La sintesi proteica . . . 12

2.1.3 Dogma centrale ed eccezioni . . . 14

2.1.4 Mutazioni genetiche e polimorfismi . . . 15

2.1.5 Alternative Splicing . . . 17

2.2 Il sequenziamento . . . 19

2.2.1 Confronto Tecnologie Sanger e NGS . . . 21

2.2.2 Applicazioni NGS . . . 22

2.2.3 RNA-seq . . . 23

3 Polimorfismi ed ASE nei dati RNA-seq 25 3.1 Il grafo di de Bruijn . . . 25 3.1.1 Modello Pevzner . . . 27 3.1.2 Modello Medvedev . . . 28 3.1.3 Da Medvedev a Pevzner . . . 29 3.1.4 DBG compresso . . . 30 3.1.5 Potenziali problemi . . . 31

3.2 Modello di analisi dei dati RNA-seq . . . 32

3.2.1 Caratterizzazione polimorfismi ed ASE nel DBG . . . 32

3.2.2 Eventi di Alternative Splicing . . . 34

3.2.3 Single Nucleotide Polimorphism . . . 35

3.2.4 Approximate Tandem Repeat . . . 36 4

INDICE 5

3.2.5 Limiti del modello . . . 36

3.3 Metodo per rilevare polimorfismi ed ASE nel DBG: KisSplice . . 37

3.4 Identificare bubbles in un grafo orientato: MouthCycle . . . 39

3.4.1 Descrizione metodologia . . . 40 3.4.2 Dettagli algoritmo . . . 42 3.4.3 Possibili varianti . . . 47 4 Un’applicazione di MouthCycle 50 4.1 Implementazione MouthCycle . . . 51 4.1.1 Progettazione . . . 52 4.1.2 Dettagli dell’implementazione . . . 52

4.2 Integrazione MouthCycle in KisSplice . . . 56

4.3 Sperimentazione . . . 59

Introduzione

Il lavoro di tesi presentato ha le sue radici nell’algoritmica e trova applicazione nel ramo della bioinformatica, un campo di studi che, particolarmente in questi ultimi anni, esige la collaborazione di un gran numero di studiosi di diverse discipline, il cui comune obiettivo è prestare le proprie conoscenze ed abilità per far luce su quello che, certamente, è il linguaggio di programmazione più antico, criptico e complesso esistente: il genoma degli esseri viventi. L’enorme interesse per il tema è decisamente aumentato grazie alle grandi innovazioni tecnologiche, che negli ultimi tempi hanno segnato la storia della biologia mole-colare, la quale, allineandosi all’era digitale, è in grado oggi di trattare il DNA e l’RNA attraverso comuni file di caratteri su disco. Gran parte dei meriti di questa rivoluzione è dovuta all’avvento dei nuovi dispositivi di sequenziamento conosciuti come Next Generation Sequencing (NGS), i quali hanno contribuito ad un costante decremento dei costi e dei tempi delle sperimentazioni che anco-ra oggi non vede fine. La nuova possibilità offerta dai dispositivi NGS ha posto solide fondamenta per la nascita e lo sviluppo di discipline che basano i propri studi su analisi automatizzate, ma allo stesso tempo continua a far emergere ulteriori esigenze e problemi ai quali l’informatica, in modo particolare, è chia-mata a dare una risposta. Così intorno alle tecnologie NGS gravitano oltre la bioinformatica, numerose discipline scientifiche, tra cui la biotecnologia e la biologia computazionale, i cui sviluppi a loro volta hanno un grande impatto sulla moderna medicina, la diagnostica, la biologia forense, la sistematica e numerosi altri ambiti applicativi.

Processi di ricostruzione dell’intera molecola di DNA/RNA, algoritmi di al-lineamento e di ricerca di stringhe sono solo alcuni fra i problemi che hanno richiesto enormi sforzi da parte della comunità scientifica, per la ricerca di

1.1 Obiettivi 7

efficienti soluzioni, grazie alle quali sono stati realizzati strumenti di analisi, memorizzazione e recupero dati, non solo di quotidiano impiego da parte dei biologi moderni, ma addirittura compresi nel bagaglio delle loro competenze tecniche. Mi riferisco, solo per citare alcuni esempi, a strumenti di information retrieval quali UCSC Genome Browser, in grado di aggregare dati provenienti dai tanti laboratori che compiono esperimenti NGS e ne consentono l’accesso pubblico, o a diffusissimi strumenti di allineamento, come BLAST.

Alla base del grande interesse suscitato dalla diffusione di queste nuove tecno-logie vi è, inoltre, l’idea che la diversità tra individui della stessa specie o di specie diverse debba in qualche modo rispecchiarsi in diversità a livello gene-tico, intendendo per diversità, in questo contesto, tanto l’apparenza esteriore quanto, ad esempio, la presenza o meno di malattie genetiche in un individuo. Pertanto la possibilità di poter confrontare ed analizzare il genoma dei tanti or-ganismi che popolano il nostro pianeta, mediante potenti strumenti hardware e software, è di grande aiuto per la ricerca scientifica ed apre la strada a pro-spettive future, i cui contorni non sono ancora ben definiti. Un domani ormai prossimo, al pari di un esame del sangue o di una radiografia, un paziente potrà permettersi di far analizzare anche il proprio DNA, aprendo così una finestra temporale che dal passato, infatti già esistono aziende private che prometto-no di ricostruire parentele lontane anni e chilometri, passando per il presente, arriverà ad osservare persino aspetti futuri del proprio organismo, scoprendo ad esempio la propria propensione a determinate malattie. Uno scenario tanto entusiasmante quanto spaventoso che sembra destinato a concretizzarsi.

1.1

Obiettivi

In primo luogo lo scopo della tesi è quello di realizzare un’implementazio-ne efficiente dell’algoritmo MouthCycle per la ricerca di bubble in un grafo direzionato e verificare la sua effettiva efficienza applicato a problemi reali. L’applicazione dell’algoritmo ci porterà allo studio ed alla modifica di un soft-ware di analisi dati RNA-seq, chiamato KisSplice e presentato alla conferenza internazionale di Bioinformatica RECOMB 2012 come metodo rivoluzionario per la ricerca di polimorfismi ed eventi di alternative splicing. In KisSplice un preciso modulo software si occupa esattamente del rilevamento di bubble in un grafo generato a partire dai dati provenienti da un sistema NGS. La modifica che apporteremo conisisterà nella sostituzione di tale modulo con

MouthCy-cle. In questo modo miriamo a raggiungere due obiettivi importanti: in primo luogo vogliamo essere in grado di confrontare i tempi di esecuzione fra i due moduli e quindi verificare le performance di MouthCycle al lato pratico; in secondo luogo mostreremo come il software di analisi risultante, con i dovuti accorgimenti, possa essere in grado di rilevare delle bubble interessanti che nel-la versione originale di KisSplice non sono prese in considerazione, proprio a causa dei limiti computazionali intrinsechi dello specifico modulo che andremo a sostituire.

1.2

Schema della tesi

Capitolo 2

Nel capitolo 2 vengono trattati argomenti di Biologia, senza minuzia di parti-colari ne pretesa di completezza, con l’intento di fornire le conoscenze minime necessarie per comprendere in cosa consistono polimorfismi ed eventi di

al-ternative splicing e da dove nasca l’esigenza che essi siano identificati. Tali

conoscenze sono fondamentali per poter apprezzare l’utilità e l’importanza del lavoro pratico svolto.

Verrà inoltre fatta una panoramica storica sulle tecnologie di sequenziamento, descritte alcune sue applicazioni e spiegato cosa si intende per RNA-seq. La finalità di questa breve trattazione è quella di dare un’idea degli strumenti, che stanno alla base del nostro studio, dai quali vengono estratti i dati da manipolare e dare inoltre percezione concreta dell’importante passo in avanti che si è fatto con l’avvento delle tecnologie NGS.

Capitolo 3

Nel Capitolo 3 viene introdotto approfonditamente il grafo di de Bruijn in alcune sue varianti, con l’obiettivo principale di illustrare l’approccio che verrà usato per il rilevamento di polimorfismi ed eventi di alternative splicing nei dati RNA-seq. Tale approccio è essenzialmente descritto nel modello di analisi proposto in KisSplice, il quale è basato interamente sulla ricerca di alcune strutture che assumono i grafi di de Bruijn in loro prossimità chiamate bubble. Verranno anche aggiunte alcune considerazioni riguardo i limiti di tale modello. In seguito viene data una descrizione sia del metodo impiegato da KisSplice per la soluzione del problema, sia della tecnica impiegata da MouthCycle per

1.2 Schema della tesi 9

il rilevamento di bubble in modo da fare chiarezza sulle linee teoriche che guideranno la parte applicativa del lavoro esposta nel capitolo successivo.

Capitolo 4

Il Capitolo 4 presenta la parte applicativa del lavoro, fornendo prima una dettagliata descrizione delle scelte implementative e progettuali legate a Mou-thCycle, ed enunciando in seguito le variazioni e gli adattamenti apportati a MouthCycle e KisSplice per perfezionare l’interfacciamento. Al termine del ca-pitolo verranno mostrati i tempi di esecuzione dei due moduli di ricerca bubble a confronto.

Nozioni preliminari

2.1

Richiami di Biologia

In questo capitolo si farà un breve richiamo ad alcuni argomenti della biologia molecolare con lo scopo di guidare il lettore nella comprensione, in particolare, di due importanti concetti che rivestono un ruolo importante nel lavoro svolto: il concetto di polimorfismo ed il concetto di alternative splicing. Vedremo che mentre il polimorfismo è presente in particolari zone del DNA, l’alternative

splicing corrisponde invece ad un meccanismo biologico che si manifesta

du-rante il processo di sintesi proteica e tramite il quale più proteine possono essere sintetizzate da uno stesso gene. A tale scopo si tenga presente che gli argomenti non verranno trattati in modo esaustivo e talvolta verranno voluta-mente omessi dettagli non ritenuti essenziali e che esulerebbero dall’argomento della tesi.

2.1.1

DNA

Il DNA, acido deossiribonucleico, è la molecola responsabile della trasmissione dei caratteri ereditari tra organismi viventi. La sua struttura è stata scoperta e dettagliatamente analizzata da Watson e Crick nel 1953 [1]. Il loro lavoro ebbe una tale rilevanza che li portò al premio Nobel nel 1962. Nello specifico, una molecola di DNA è costituita da un doppio filamento orientato a forma di spirale, in cui gli elementi di ciascuna catena sono uno fra i 4 acidi nuclei-ci: l’adenina (A), la guanina (G), la citosina (C) e la timina (T), chiamati nucleotidi o basi. I due filamenti sono tra di essi collegati mediante le basi, in particolare tra di esse vale la legge di complementarietà di Watson-Crick:

2.1 Richiami di Biologia 11

Figura 2.1: Struttura a doppia elica del DNA

l’adenina si lega solo con la timina (A-T) e la guanina si lega solo con la citosi-na (G-C); ciascucitosi-na di queste coppie è conosciuta in letteratura come base-pair (bp) ed è l’unità di misura di riferimento del DNA per valutare la lunghezza del filamento (100.000.000bp = 100.000kbp = 100Mbp = 0.1Gbp). Per ragioni da ricercare nella struttura chimica del DNA le estremità di un filamento vengono chiamate 5’ (five prime) e 3’ (three prime) e per convenzione l’orientamento cui ci si riferisce, quello impiegato nelle grandi banche dati di DNA, è 5’ verso 3’. Grazie alla legge di complementarietà, data la sequenza di un filamento pos-siamo dedurre univocamente la sequenza di quello complementare attraverso un’operazione chiamata reverse complementation. Ad esempio: data la sequen-za s = AGACGT prima invertiamo s ottenendo s0 _{= T GCAGA e in seguito}

rimpiazziamo ogni base con la sua complementare ottenendo ¯s = ACGT CT . Il motivo dell’inversione è proprio quello di rispettare la convenzione 5’, 3’ in quanto come si vede anche in figura 2.1 le estremità dei due filamenti sono invertite.

Nell’intera sequenza di DNA, detta genoma, sono contenute tutte le in-formazioni genetiche necessarie per la generazione delle proteine, composti organici molto complessi che regolano lo sviluppo ed il corretto funzionamen-to degli organismi viventi. Il processo che porta dal genoma alla proteina è conosciuto come processo di sintesi proteica.

Facendo una notevole approssimazione, possiamo vedere il genoma come illustrato in figura 2.2: un insieme di cromosomi separati fra loro da sequenze ripetute di nucleotidi, i telomeri. Ogni cromosoma è a sua volta costituito da regioni codificanti, i geni, e da regioni non codificanti, dette anche junk DNA, che tipicamente contengono alcune istruzioni di controllo per la creazione delle

Figura 2.2: Una rappresentazione schematica della struttura del genoma. proteine anche se in molti casi le funzioni svolte sono ancora sconosciute. I geni sono l’unità ereditaria fondamentale degli organismi viventi ed anch’essi al loro interno sono costituiti da parti codificanti, gli esoni, e parti non codificanti, gli introni. Per fare un esempio, si pensi che il genoma umano ha una dimensione approssimativa di 3.2 Gbp ed è composto da 23 coppie di cromosomi in cui si ipotizza siano contenuti tra i 20.000 ed i 25.000 geni.

2.1.2

La sintesi proteica

Nel DNA sono presenti tutte le informazioni necessarie per la produzione delle proteine, costituenti fondamentali di tutte le cellule animali e vegetali. Esse sono composte da una catena di amminoacidi, molecole più semplici che inter-vengono nella maggior parte dei processi biologici. Gli amminoacidi svolgono funzioni di trasporto come ad esempio l’emoglobina, che veicola l’ossigeno nel sangue, funzioni immunitarie come la cheratina, che protegge la pelle, o la glicoproteina, che è incaricata di produrre immunoglobina per la difesa dell’or-ganismo, oltre alle numerose funzioni strutturali, recettive e regolatorie. Nel processo di sintesi proteica un ruolo estremamente importante è quello che riveste l’RNA, acido ribonucleico, una molecola molto simile al DNA con la differenza che è costituito da un’unica catena di nucleotidi e, inoltre, il com-plementare dell’adenina (A) è l’uracile (U), e non la timina. Attraverso il processo di sintesi proteica le informazioni genetiche vengono trasformate in proteine. Tale processo, negli eucarioti, richiede due passaggi: la trascrizione

2.1 Richiami di Biologia 13

del DNA in mRNA (RNA messaggero), ovvero il trascrittoma, e la traduzione dell’mRNA in una catena di amminoacidi. L’mRNA è un particolare tipo di RNA che ha il compito di trasportare l’informazione genetica al di fuori del nucleo. Andiamo di seguito ad analizzare le due fasi della sintesi proteica.

La trascrizione

La trascrizione è un processo biochimico che avviene all’interno del nucleo della cellula e grazie al quale una molecola di mRNA viene generata impiegando un unico filamento del DNA di un gene. Possiamo riassumere questo processo in questo modo: il tratto di DNA che compone il gene da trascrivere viene aperto in un punto ben preciso, caratterizzato da una specifica tripletta nucleotidica chiamata codone di start. Un enzima, l’RNA polimerasi, si occupa della lettura delle informazioni legandosi chimicamente a uno dei due filamenti di DNA e, seguendo il suo orientamento, genera i nucleotidi di RNA (ribonucleotidi) complementari. Un’altra specifica tripletta chiamata codone di stop, determina l’interruzione della generazione di quello che prende il nome di pre-mRNA, un RNA temporaneo in cui sono presenti sia introni che esoni. Questa catena di ribonucleotidi si separa dal DNA e subisce il processo biochimico di splicing, attraverso il quale gli introni vengono rimossi. Si forma così l’mRNA che passando fra i pori della membrana nucleare entra nel citoplasma, sostanza presente fra nucleo e membrana cellulare. Intanto, terminata la lettura, il DNA si riavvolge a formare la doppia elica, oppure si lega a una nuova molecola di RNA-polimerasi per sintetizzare un nuovo filamento di mRNA.

La traduzione

La traduzione è la fase della sintesi proteica in cui le istruzioni trasportate dal-l’mRNA vengono tradotte nella sequenza corretta di amminoacidi per formare una proteina. In particolare la traduzione ha luogo nel citoplasma per opera di una complessa molecola detta ribosoma. Il ribosoma attua una conversione fra ogni tripletta di nucleotidi, codone, ed il corrispondente amminoacido per la sintesi della proteina o per la fine della sintesi della stessa. Tale corrispondenza dopo una lunga serie di esperimenti, è stato scoperto essere deterministica e dettata dalle regole del codice genetico [2], un insieme di regole che ha validità per qualsiasi organismo vivente. Esistono 20 diversi amminoacidi, ed il motivo per cui sono codificati da triplette di nucleotidi si dimostra matematicamente: solamente 4 nucleotidi non sono sufficienti per codificare i 20 diversi

ammi-Figura 2.3: Il processo di sintesi proteica schematizzato. Esoni ed introni del gene sono rappresentati rispettivamente in rosso ed in grigio. Le sequenza di aminoacidi di cui la proteina è costituita si riavvolge assumendo una forma simile a quella raffigurata.

noacidi, con una sequenza di 2 nucleotidi si riuscirebbero a codificare 42 = 16

amminoacidi mentre con una tripletta è possibile avere 43 = 64 combinazioni,

che sono più che sufficienti. Con 64 combinazioni possibili accade che più di una codifichi lo stesso amminoacido e inoltre vi sono alcuni codoni ai quali non ne corrisponde alcuna, tra i quali vi sono i codoni di start/stop a cui si è accennato nel paragrafo sulla trascrizione. Questo sovrannumero di combina-zioni è detto degenerazione del codice genetico. Al termine della conversione, il filamento di amminoacidi risultante si arrotola formando infine la proteina.

2.1.3

Dogma centrale ed eccezioni

Il processo di sintesi proteica, riassunto in precedenza, è comunemente cono-sciuto come il Dogma Centrale della Biologia Molecolare. Fu articolato per la prima volta da Francis Crick nel 1958 [3] ed in seguito ripubblicato sulla rivista scientifica Nature nel 1970 [4]. In questo lavoro si afferma che esiste unidirezio-nalità nell’espressione dell’informazione contenuta nei geni di una cellula, ossia

2.1 Richiami di Biologia 15

l’informazione transita sequenzialmente da DNA verso mRNA e in seguito ver-so le proteine ma non viceversa. Si ipotizza inoltre che a ogni gene corrisponda un’unica proteina e che solo il DNA possa duplicarsi, riprodursi, e trasmettere l’informazione genetica alla discendenza. Nella realtà si è dimostrato che le cose sono ben più complesse e meno dogmatiche. Esistono, infatti, dei casi in cui l’unidirezionalità non viene rispettata: è il caso, ad esempio, di alcuni virus della famiglia dei retrovirus che, attraverso un processo chiamato, non a ca-so, reverse transcription, riescono a trasferire informazioni dall’RNA al DNA, procedimento appunto inverso a quello di trascrizione. Per fare un esempio pratico, il virus dell’HIV fa parte di questa famiglia. Esistono anche casi in cui si ha traduzione diretta da DNA a proteine senza passare per l’mRNA [5]. Inoltre ad oggi, si è certi che da uno stesso gene possono essere sintetizzate tante proteine diverse tramite il processo di alternative splicing che approfon-diremo in seguito e che riveste il ruolo principale nel lavoro svolto. Quello che faremo nella parte applicativa di questa tesi sarà infatti andare alla ricerca in particolare di questi fenomeni.

2.1.4

Mutazioni genetiche e polimorfismi

Per evoluzione biologica si intende l’insieme di modifiche che si manifestano negli organismi e che, con il passare del tempo, ha originato la diversità tra le forme viventi. Questo processo si basa sulla trasmissione del patrimonio geni-co di un individuo alla sua progenie e sull’interferenza in essa frapposta dalle mutazioni casuali. Le mutazioni genetiche corrispondono a un’alterazione del-l’informazione genetica di un essere vivente, possono essere ereditate e possono inoltre avere effetti favorevoli o dannosi per l’organismo. Su questa variabilità opera la selezione naturale, la quale promuove le mutazioni favorevoli a scapito di quelle sfavorevoli o addirittura dannose. Essendo una parte delle mutazioni non favorevoli, gli organismi hanno sviluppato diversi meccanismi per la ripa-razione del DNA dai vari danni che può subire, riducendo in questo modo il tasso di mutazione.

Per polimorfismo si intende una mutazione genetica che interessa più dell’1% della popolazione di un determinato organismo in un dato ambiente. Lo studio di questi fenomeni è uno dei temi verso cui la scienza, partendo dalla biologia e passando per le scienze a suo supporto tra cui la bioinformatica e la biolo-gia computazionale, sta dedicando maggiore attenzione. La sua importanza deriva dal fatto che è noto da tempo il loro collegamento con molte malattie

genetiche, tra cui anche il cancro, come testimoniano i lavori [7] [8] [9]. Tra i vari tipi di mutazioni genetiche pongo l’accento su due in particolare:

• Single nucleotide polymorphism. • Copy Number Variation.

che verranno menzionate in seguito nel lavoro dato che assumeranno par-ticolari strutture nel modello di analisi impiegato. Avendo bene in mente il meccanismo della sintesi proteica è ora immediato comprendere come il poli-morfismo a livello genetico, nel momento in cui è presente in regioni codificanti, transita inevitabilmente a livello di trascrittoma (RNA).

Single nucleotide polymorphisms (SNPs)

Uno SNP (pronunciato snip), detto anche SNV (Single Nucleotide Variation), è una variazione che interessa un’unica base di una sequenza di DNA. Gli SNP si possono osservare dal confronto tra genomi di diversi organismi ma esiste anche la possibilità che nello stesso genoma si presentino porzioni di sequenze particolarmente simili con solo alcune variazioni di questo tipo. In particolare uno SNP può essere causato da:

• Sostituzione di un nucleotide per un altro • Indel inserimento o cancellazione di una base.

Negli esempi riportati in seguito si mostrano i due possibili tipi di SNP:

Sostituzione= A A C T A A | | × | | | A A T T A A Indel = A A C T A A A A T A A

Gli SNPs possono presentarsi all’interno di una regione esonica, in una re-gione intronica o in una rere-gione intergenica. Anche all’interno di una rere-gione codificante, in ogni caso, non modificano necessariamente la sequenza ammi-noacidica che verrà trascritta dal momento che il codice genetico è degenerato, come spiegato in 2.1.2.

2.1 Richiami di Biologia 17

trovate corrispondenze con alcune patologie; inoltre, la loro presenza causa diverse reazioni dell’organismo a patogeni, ad agenti chimici e a farmaci. Si pensa perciò che una loro analisi dettagliata sia una delle chiavi per lo sviluppo della medicina personalizzata.

Copy Number Variation (CNV)

Similmente agli SNPs anche le CNV sono polimorfismi del DNA, in cui però la sostituzione e l’indel interessano non più singoli nucleotidi ma intere regioni di più grandi dimensioni. Possiamo considerare un caso particolare dei CNV i cosiddetti Approximate Tandem Repeat in cui viene replicata una regione simile, e non perfettamente identica, a quella di partenza.

2.1.5

Alternative Splicing

Come già accennato, un’eccezione al dogma centrale consiste nel fatto che da uno stesso gene possono essere sintetizzate diverse proteine. Durante la fase di trascrizione, il pre-mRNA subisce il processo di splicing attraverso il quale gli introni vengono rimossi. In seguito gli esoni vengono riconnessi preservando l’ordine. Il meccanismo di alternative splicing consente la completa o parziale omissione di alcuni di questi esoni, così, da una stessa sequenza genetica si for-mano diversi mRNA o, più tecnicamente, diverse isoforme proteiche (splicing

isoforms) (fig. 2.4).

Eventi di Alternative splicing

Analizzando dettagliatamente le varie isoforme proteiche ottenute a partire da un medesimo gene, si sono osservati dei modelli ricorrenti conosciuti come eventi di Alternative Splicing (fig. 2.5). Tra questi troviamo:

1. Exon skipping: in questo caso un esone viene completamente omesso dal trascrittoma finale. Dato il pre-mRNA costituito dalla sequenza di esoni BCD, dallo splicing si può ottenere sia la sequenza BD che la sequenza BCD.

2. Mutually exclusive exon: solo uno di due esoni viene mantenuto nell’mR-NA maturo, non entrambi. Dato il pre-mRnell’mR-NA costituito dalla sequenza di esoni BCDE si possono ottenere 2 trascrittomi BCE, BDE.

Figura 2.4: Alternative splicing. Da uno stesso gene a causa di differenti eventi di splicing, possono essere espresse più proteine [10].

3. Alternative 5’ splice site: il punto in cui l’esone viene tagliato nell’e-stremità 5’ può essere posticipato, in questo modo solo una porzione dell’esone iniziale sarà presente nel trascrittoma generato.

4. Alternative 3’ splice site: il punto in cui l’esone viene tagliato nell’estre-mità 3’ può essere anticipato, in questo modo solo una porzione dell’esone finale sarà presente nel trascrittoma generato.

5. Intron retention: i siti di taglio di un introne possono non essere rico-nosciuti. In questo caso l‘introne non viene eliminato dal trascritto di mRNA.

2.2 Il sequenziamento 19

Figura 2.5: Alternative splicing events. Recenti studi sul DNA umano hanno evidenziato una corrispondenza tra frequenze anomale di splicing e distur-bi genetici [11], corrispondenze talvolta correlate con lo sviluppo di malattie tumorali [12] [13].

2.2

Il sequenziamento

Il sequenziamento è il ponte di congiunzione tra la biologia e l’informatica, il processo che permette di determinare l’ordine dei nucleotidi nel DNA o nel-l’RNA d’interesse, con lo scopo di eseguire, in seguito, una dettagliata analisi tramite l’aiuto delle più moderne tecnologie hardware e software. Questo pro-cedimento ha significativamente accelerato la ricerca biologica e l’avvento di nuove scoperte, assumendo inoltre un importante ruolo in discipline come la diagnostica, la biotecnologia, la biologia forense e la sistematica [16].

La nascita delle tecnologie per il sequenziamento di prima generazione si può datare intorno al 1977 con l’ideazione del metodo Sanger [14], anche se metodi molto laboriosi venivano già impiegati in precedenza. Il loro sviluppo ha dato il via a numerosi progetti tra cui lo Human Genome Project che, iniziato nel-l’ottobre del 1990, ha impiegato più di 10 anni per dare alla luce il contenuto del genoma umano, per un costo totale stimato intorno ai 3 miliardi di dolla-ri1_{. Nel 2005 nascono le tecnologie di seconda generazione, più comunemente}

chiamate tecnologie Next Generation Sequencing (NGS) o High-Throughtput

Sequencing (HTS), le quali hanno contribuito ad abbassare enormemente i

sti ed i tempi dell’operazione. Ciò è stato possibile grazie all’elevata velocità di sequenziamento offerta, affiancata da potenti strumenti informatici in grado di elaborare e gestire efficacemente la grande mole di informazioni prodotta. Per avere un’idea, per quanto riguarda il sequenziamento del genoma umano l’unità di misura per il tempo è diventata l’ora mentre i costi sono nell’ordine delle migliaia di euro, che comunque in un’ottica dello sviluppo di una medi-cina personalizzata, possiamo considerare un costo ancora troppo elevato (fig. 2.6).

Dopo questa breve introduzione, nella sezione successiva entrerò nel dettaglio della tecnologia NGS, il cui sviluppo ha dato nuova linfa ad alcuni settori del-l’informatica, in particolar modo al settore algoritmico, fino a contribuire al rapido sviluppo di nuove discipline specifiche. Tra di esse si evidenziano la bio-informatica e la biologia computazionale che hanno lo scopo di studiare nuovi algoritmi efficienti e fornire moderni strumenti per il trattamento e l’analisi dei dati nella fase di post-sequencing, tenendo conto dei limiti fondamentali di calcolo e di memoria delle moderne macchine a disposizione.

2.2 Il sequenziamento 21

2.2.1

Confronto Tecnologie Sanger e NGS

Una serie di nuove tecnologie per il sequenziamento sono emerse negli ultimi anni, partendo dal 2005 con il 454 Life Science della Roche, seguito da So-lexa/Illumina nel 2006, dalla tecnologia SOLiD della Applied Biosystems nel 2007 e, nel 2008, dall’Helicos (fig. 2.7) [18] [15]. La caratteristica comune di queste tecnologie è l’alto grado di parallelismo con cui svolgono il sequenzia-mento; per questo motivo talvolta ci si riferisce a questa nuova generazione di sequenziatori anche con il termine massively parallel technologies. È importan-te dire che tutimportan-te le importan-tecnologie di prima e seconda generazione sono in grado di sequenziare anche soltanto porzioni del DNA, possibilità che da sola, garantisce un gran numero di diverse utilizzazioni di un sequenziatore. Così come avviene per le tecnologie ‘figlie’ del metodo Sanger, il DNA viene suddiviso in milioni di frammenti ma, a differenza di queste ultime, i frammenti vengono sequenziati simultaneamente, garantendo così una produttività di gran lunga superiore. In entrambe le tecnologie ciascun frammento prima di essere sequenziato su-bisce un ulteriore taglio, in maniera non deterministica, in sottosequenze più piccole chiamate reads. Uno dei più grossi limiti delle NGS sta nel fatto che la lunghezza dei reads è tra i 35-250 bp a seconda del macchinario, mentre con la prima generazione si hanno sottosequenze lunghe tra i 650-800 bp che, con l’intento di riassemblare l’intero filamento, possono essere considerati parame-tri migliori. Siamo infatti portati a pensare che più lunghi sono i reads, minore è la quantità di dati generata e minore è anche lo sforzo computazionale in fase di riassemblaggio. Questo ragionamento è valido, ma resta il fatto che il collo di bottiglia della prima generazione di sequenziatori è proprio la fase di sequenziamento in sé e non il riassemblaggio. A complicare le cose, per entrambe le tecnologie, si aggiunge il fatto che al sequenziamento corrisponde l’arrivo disordinato dei reads ma, ad ogni modo, entrambi i limiti sono stati abilmente aggirati con l’utilizzo di potenti algoritmi appositamente studiati. Fra di essi, per quanto riguarda il difficile lavoro di ricostruzione (assembly), si distingue l’approccio basato sulla ricerca di cicli euleriani in una particolare struttura dati, detta grafo di De Bruijn che verrà presentata nel capitolo 3.1. Infine va aggiunto che, nel medesimo esperimento, la stessa sequenza nucleoti-dica viene più volte sequenziata in modo da garantire una maggior copertura (coverage) per ciascun nucleotide e permettere di individuare facilmente even-tuali errori di lettura. Viene così aumentata la qualità dei risultati a discapito di un maggior costo in termini di tempo e danaro, come si può vedere nella

Figura 2.7: Paragone metriche e performance fra alcuni NGS sequencer [18]

figura 2.7 ed in particolare alla riga della tabella cost per run.

2.2.2

Applicazioni NGS

Sono due i principali processi che possono subire i dati derivanti da un espe-rimento di sequencing. Entrambi hanno lo scopo di ricostruire la sequenza ma lo raggiungono usando un diverso approccio alla risoluzione del problema: il primo consiste nell’allineamento dei reads su una sequenza di riferimento [20], il secondo, chiamato de novo assembly, consiste nell’assemblaggio di una porzione di DNA partendo dai frammenti e senza nessuna informazione pre-liminare [21]. La decisione su quale strada prendere dipende ovviamente dal fatto che si conosca o meno la sequenza di riferimento, ma anche in base al tipo di analisi che deve essere fatta sui dati raccolti dettata a sua volta spesso dai limiti legati al costo ed ai tempi. Per fare un esempio: per identificare e catalogare variazioni genetiche fra batteri i cui genomi sono particolarmente si-mili, un metodo rapido e a basso costo consiste nell’allineare NGS reads al loro genoma di riferimento, senza alcuna necessità di riassemblaggio [15]. Esem-pi di altre applicazioni sono: identificazione di variazioni genetiche, de novo

assembly di batteri, catalogazione di geni e trascrittomi di cellule, tessuti e

organismi (RNA-seq), classificazione di specie [15]. Una disciplina emergente, che ha trovato sbocco dall’applicazione di NGS, è la Personal Genomics, un campo della genomica che tratta il sequenziamento e l’analisi del genoma degli individui, in modo da trovare correlazioni tra le caratteristiche di un indivi-duo e porzioni di genoma, o anche la sua propensione a determinate malattie. Gli strumenti software odierni, grazie all’impiego di tecniche di SNP detection, permettono di paragonare due sequenze genomiche e quantificare le differenze fra di esse. L’obiettivo è quello di raggiungere una conoscenza tale da permet-tere una genomica personalizzata per fini medici. L’idea di fondo della ricerca, su questo nuovo fronte della biologia molecolare, è che la diversità tra

indivi-2.2 Il sequenziamento 23

dui debba in qualche modo rispecchiarsi nella diversità a livello genetico, con questa premessa nasce anche l’applicazione delle NGS per il sequenziamento di RNA.

2.2.3

RNA-seq

Il sequenziamento dell’RNA è un processo che veniva anch’esso già realizza-to adottando sequenziarealizza-tori di prima generazione. Grazie a questi strumenti, gli studi sul trascrittoma hanno fatto maggiore chiarezza sulla complessità dell’argomento. Una migliore comprensione dell’RNA è infatti essenziale per interpretare quelli che sono gli elementi funzionali del genoma e rilevare le mo-lecole che costituiscono le cellule e i tessuti. Gli scopi principali sono quelli di catalogare i trascrittomi e determinare/quantificare i diversi modi in cui un gene può essere espresso (le diverse splicing isoforms). Anche sotto questo am-bito applicativo, lo sviluppo delle tecnologie NGS ha favorito la nascita di un nuovo metodo per il sequenziamento dell’RNA che prende il nome di RNA-seq [22]. In questa breve parentesi, voglio cercare di fare chiarezza su una sottile differenza tra sequenziamento di DNA e RNA-seq che talvolta può causare confusione. Questa differenza è puramente a livello biologico e, in particola-re, sta nella fase di preparazione della sequenza nucleotidica da sequenziare. Se per sequenziare il DNA, attraverso processi biochimici, è possibile isolare una sola molecola, o porzioni della stessa, in modo che venga data in input al sequenziatore, per l’RNA non avviene lo stesso. Per motivazioni sulle qua-li non entriamo nel dettagqua-lio, l’RNA subisce prima una riconversione in un DNA chiamato DNA complementare (in sigla cDNA) attraverso un processo di reverse transcriptase, in seguito è il cDNA ad essere sequenziato. Va notato come il cDNA, essendo stato ottenuto a partire da una molecola di RNA, è costituito da soli esoni. Quanto descritto è riassunto in figura 2.8. È molto recente invece la nascita di nuove tecnologie di Direct RNA-seq che permetto-no il sequenziamento di RNA direttamente senza passare per il cDNA, come testimonia [24]; per gli sviluppi futuri si consulti [23].

Figura 2.8: Un gene subisce il processo di alternative splicing, in entrambi i casi, a sinistra ed a destra, avviene un evento di exon skipping. L’mRNA attraverso il processo di reverse transcriptase viene convertito in cDNA ed in seguito ricevuto in ingresso dal sequenziatore NGS

Capitolo 3

Polimorfismi ed ASE nei dati

RNA-seq

Nel capitolo introduttivo abbiamo visto brevemente in cosa consistono gli

even-ti di Alternaeven-tive Splicing, cui acronimo è ASE (cap. 2.5), cosa si intende per Single Nucleotide Polimorphism, SNP (cap. 2.1.4) e Copy Number Variation

CNV. In particolare riaccenno brevemente al fatto che i primi avvengono di-rettamente nell’RNA, causati appunto del meccanismo biologico di alternative

splicing, mentre per quanto riguarda gli SNP e CNV sono inizialmente

pre-senti nel DNA e, nel caso interessino regioni codificanti (gli esoni), tramite il processo di sintesi proteica (cap. 2.1.2) propagano le variazioni nell’RNA. Se a queste conoscenze affianchiamo uno strumento in grado di sequenziare il trascrittoma (RNA), strumento per giunta già esistente che prende il nome di RNA-seq (cap. 2.2.3), per poter rilevare SNP ed ASE abbiamo bisogno solo di un qualche strumento di analisi.

In questo capitolo verrà presentato appunto uno strumento, chiamato

KisSpli-ce, nato per rilevare polimorfismi ed ASE passando attraverso lo studio dei

dati che giungono da un esperimento di RNA-seq. Verranno descritti alcuni suoi limiti e di seguito presentato un algoritmo chiamato MouthCycle che ha le potenzialità di superarli. Ma prima ancora introduciamo una struttura dati che sta alla base di tutto il discorso, il grafo di de Bruijn.

3.1

Il grafo di de Bruijn

Il grafo di de Bruijn (DBG) è una struttura dati usata oggi in particolare per il processo di de novo assembly di una sequenza nucleotidica, una volta

ricevuti in ingresso i reads di un esperimento NGS. Il DBG usato oggi è un adattamento al contesto biologico, di una struttura dati pensata nel 1946 per risolvere il problema della superstringa che nella sua formulazione richiede di trovare la stringa più corta che contenga tutte le possibili sottostringhe di un dato alfabeto [25]. Oggi di questa struttura resta l’idea principale ed il nome dell’ideatore, il matematico olandese Nicolaas de Bruijn.

Furono gli studiosi Idury e Waterman [26] ed in seguito Pevzner, Tang e Water-man [19] che pensarono di riadattare la sua struttura al campo dei sequenziato-ri. Essi proposero la creazione del grafo a partire dai reads per la ricostruzione della sequenza nucleotidica, attraverso la ricerca di particolari path al suo in-terno. In questo contesto comunque non entro nel merito degli algoritmi per la ricostruzione, in quanto non è nello scopo della tesi proposta, per un ap-profondimento propongo la lettura di [27]. Scopo di questa premessa è invece comprendere il modello del grafo di de Bruijn, perchè quello che faremo in seguito sarà andare alla ricerca di particolari strutture presenti al suo interno, chiamate bubble. In questa sezione proveremo a fare un pò di chiarezza sulle varie versioni esistenti del DBG, presentando per prima la versione risultato del lavoro di Pevzner del 2001 [19], seguita dalla modifica realizzata nel 2007 da Medvedev et al. [28]. Il motivo di questa ampia descrizione dipende dal fatto che nella pratica andremo a trattare entrambi i modelli. Vediamo innan-zitutto alcune definizioni utili:

Siano v e w due stringhe sull’alfabeto Σ, definiamo la lunghezza di v con |v| la loro concatenazione con vw. Il carattere ith _{di v con v[i]. Se 1 ≤ i ≤ j ≤ |v|,}

allora v[i, j] è la sottostringa che inizia dalla posizione ith _{e termina nella j}th

estremi inclusi. Se esistono i, j tali che v = w[i, j], allora si dice che v è una sottostringa di w.

Definizione 1 (k-mer) chiamiamo k-mer una string v t.c |v|= k

Definizione 2 (k-spectrum) Il k-spectrum di v, K(v), è l’insieme di tutte

le k-mer che sono sottostringhe di v, con k ≤ |v|

Definizione 3 (k-molecule) Una k-molecule è una coppia di k-mer che sono

tra di esse reverse complement (cap. 2.1).

Definizione 4 (k-molecule-spectrum) Il k-molecule-spectrum di una

mo-lecola di DNA è l’insieme delle k-molecule che corrispondono alle k-mers del k-spectrum di ciascun filamento del DNA.

3.1 Il grafo di de Bruijn 27

Definizione 5 Una stringa w si sovrappone (overlap) a v se esiste una

strin-ga z non vuota di lunghezza massima che è un prefisso di w ed un suffisso di v. La lunghezza della sovrapposizione è ov(v, w) = |z|. Se w non si sovrappone a v allora ov(v, w) = 0.

3.1.1

Modello Pevzner

Entriamo ora nel dettaglio del modello di de Bruijn graph studiato da

Pevz-ner [19], presentandolo con una semplice definizione generale:

Definizione 6 (de Bruijn graph) Sia S = {s1, ..., sn} un insieme non

vuo-to di stringhe in Σ, definiamo il DBG come un grafo orientato Bk(S) = (V, E), con k > 0, dove:

V = {v ∈ Σk|∃i 1 ≤ i ≤ n tale che v è una k-mer sottostringa di si}

E = {(u, v)|u, v ∈ V ∧ ov(u, v) == k − 1}

Nel nostro contesto l’insieme S è composto da tutti i reads che giungono dal processo di sequencing. L’insieme dei vertici V è l’unione dei k-spectrum di ciascun read, esiste perciò un nodo per ogni k-mer (si noti che essendo l’u-nione, non possono comparire due nodi che rappresentano la stessa k-mer). L’insieme E degli archi è costituito dalle coppie (u, v) tali che ov(u, v) = k − 1 con u, v ∈ V ; esiste perciò un arco da u a v se il suffisso lungo k − 1 di u è uguale al prefisso lungo k − 1 di v.

Già tempo prima Pevzner [29] aveva studiato una soluzione simile, rappresen-tata dalla costruzione del DBG Bk−1 _{in cui gli archi (u, v) sono etichettati con}

le k-mer, mentre u e v sono rispettivamente il prefisso ed il suffisso di lunghezza

k −1 (fig.3.2).

Solo per dare l’intuizione, si noti che percorrere un path in una struttura di questo tipo equivale a ricostruire una sequenza nucleotidica costituita dalle informazioni tratte dalle sovrapposizioni tra le k-mer e rappresentate dai nodi. Un’altra cosa, ben più complicata, è stabilire che tale sequenza sia consisten-te, ossia rappresenti realmente la molecola di DNA originale o anche solo una sua parte, di questo si occupano i metodi di assembly. Ad ogni modo, senza voler entrare nel dettaglio, questa intuizione è sufficiente per comprendere un limite intrinseco di questo modello proposto da Pevzner nel caso vengano se-quenziati entrambi i filamenti della molecola: nessuna distinzione viene fatta tra k-mer complementari. Questo comporta che per ogni path associato ad un

filamento della molecola esisterà nel grafo anche il path relativo alla sequen-za nucleotidica complementare. A seconda del obiettivo per cui si costruisce il grafo quest’informazione può risultare ridondante. Vedremo che il modello successivo cercherà di porvi rimedio.

3.1.2

Modello Medvedev

Nel 2007 Medvedev studiò una nuova struttura che più si presta a modella-re il DNA come molecola a doppio filamento [28]. Lavorando con entrambi i filamenti di una molecola di DNA, risulta necessario trattare con k-molecule invece che con le k-mers del DBG. L’idea di Medvedev è quella appunto di creare un nodo per ogni k-molecule. Il DBG in questo contesto è un bidirected

graph dove le coppie di k-mer che costituiscono ogni k-molecule N vengono

etichettate una positive (+) (o forward F (N)) e l’altra negative (-) (o

rever-se R(N)) a marcare il fatto che appartengano ad uno o a l’altro filamento.

Va notato che questo processo è puramente arbitrario, infatti non è possibile stabilire con certezza da quale dei due filamenti proviene un read. L’insieme V è costituito quindi da tutte le possibili k-molecules. Poniamo un arco da

N1 ad N2 se il suffisso di lunghezza k − 1 di F (N1) o R(N1) si sovrappone

perfettamente con il prefisso di F (N2) o R(N2). Etichettiamo ogni arco con

una stringa l ∈ {F F, RR, F R, RF }. La prima lettera, leggendo nella direzione dell’arco, indica quale fra F (N1) ed R(N1) si sovrappone a F (N2) o R(N2),

con quest’ultima informazione indicata dalla seconda lettera. Si noti che, se esiste un arco da N1 ad N2 etichettato ad esempio F F , necessariamente esiste

anche un arco da N2 ad N1 etichettato RR (lo stesso discorso vale ovviamente

anche per le altre etichette).

Nella pagina successiva in figura 3.1 mostro un semplicissimo esempio del mo-dello descritto, mentre in figura 3.2 vengono paragonati i 2 approcci modellistici Pevzner e Medvedev. Faccio presente che nell’articolo di Medvedev viene usa-ta una sinusa-tassi più concisa al posto delle etichette ed inoltre si fa riferimento alla costruzione del DBG Bk−1, il risultato finale comunque è semanticamente

equivalente a quello descritto in questo testo, che è stato tratto da [30]. Data la complessità della struttura dati, a differenza di quanto avviene con il modello Pevzner risulta non immediato stabilire quale sia un path valido, daremo allora una sua definizione:

3.1 Il grafo di de Bruijn 29

Definizione 7 (valid path) Il passaggio attraverso un nodo N è detto valido

se la seconda lettera (F o R) dell’etichetta di un arco entrante nel nodo è uguale alla prima lettera dell’etichetta dell’arco uscente dal nodo. Un path nel grafo è valido se l’attraversamento di ogni nodo in esso contenuto è valido. Quindi ogni coppia di nodi adiacenti nel path sono etichettati rispettivamente, XY e YZ con X, Y, Z ∈ {R, F }

Figura 3.1: In figura un esempio del modello Medvedev di un DBG Bk

costi-tuito dai soli nodi (k-molecule) N1 , N2. L’arco con etichetta RF ci indica che

la k-mer capovolta di N1 è prefisso della k-mer di N2. Viceversa vale per il

secondo arco.

Figura 3.2: In figura un paragone fra il modello Pavzner a sini-stra e il modello Medvedev a desini-stra. Entrambi rappresentano un DBG Bk−1 _{con k = 3 costruito a partire dal k-molecule-spectrum}

ATT/AAT,TTG/CAA,TGC/GCA,GCC/GGC,CCA/TGG,CAA/TTG, AAC/GTT. Con la sintassi usata da Medvedev un arco con estremità entrambe a sx (N1 < − < N2) corrisponde a 2 archi: (N1, N2) con etichetta

RR ed (N2, N1) con etichetta FF. Gli altri archi vanno letti con la stessa

logica. Immagine tratta da [28].

3.1.3

Da Medvedev a Pevzner

Come abbiamo visto, i due modelli Medvedev (MV) e Pavzner (PV), nascono entrambi per rappresentare il medesimo problema, ma MV riesce a farlo in una maniera più compatta. Un grafo di Pevzner può avere fino al doppio dei nodi di MV. Ciò nonostante è sempre possibile riportare un grafo di Medve-dev in Pevzner e viceversa in modo abbastanza immediato. In questa sezione

presenteremo una semplice maniera in cui è possibile convertire MV in PV, un’operazione che si rivelerà utile nel lavoro pratico realizzato.

Il miglioramento apportato da MV consiste brevemente nel riuscire a compat-tare le informazioni provenienti da entrambi i filamenti del DNA in nodi unici. Per risolvere questa bivalenza vengono etichettati gli archi in modo che possa essere definito quale sia il valid path da un nodo ad un altro. In questo modo, tramite l’etichetta dell’arco attraversato, possiamo sapere quale delle due se-quenze nucleotidiche contenute nel nodo va associata al path percorso.

Per realizzare la conversione si può agire in questo modo: dato GM(VM, EM)

grafo di Medvedev definiamo la funzione di conversione C :: GM −→ GP in cui

GP = (VP, EP) è il grafo di Pevzner. Ogni nodo v ∈ VM possiamo considerarlo

come una coppia di singoli nodi in VP e quindi:

VP = {+v, −v|v ∈ VM}

dove +v manterrà la sequenza F (v) mentre −v quella di R(v). L’insieme degli archi sarà invece:

EP = {(−v, −w) | (v, w) ∈ EM ∧(v, w).label = RR}

∪{(−v, +w) | (v, w) ∈ EM ∧(v, w).label = RF }

∪{(+v, −w) | (v, w) ∈ EM ∧(v, w).label = F R}

∪{(+v, +w) | (v, w) ∈ EM ∧(v, w).label = F F }

3.1.4

DBG compresso

Capiterà più avanti di far riferimento al compressed De Bruijn graph, in sigla cDBG. Tale struttura presenta un ulteriore variazione: ogni path lineare viene compresso in un unico nodo che conserva le informazioni dei nodi da esso inglo-bati. In pratica un DBG può essere compresso senza perdita di informazioni attraverso la fusione di nodi semplici. Con nodi semplici si intendono quei nodi collegati al massimo ad altri due nodi. Due nodi adiacenti possono essere fusi in un unico nodo rimuovendo l’informazione ridondante che essi contengono, dovuta alla sovrapposizione fra k-mer. Un valid path (cap. 3.1.2) composto da i > 1 nodi semplici verrà compresso in un unico nodo che terrà traccia della sequenza di lunghezza k + (i − 1). Ogni nodo v ∈ V rappresenta una sequenza lunga |v| ≥ k mentre, per gli archi la logica resta invariata. Lo stesso discorso è riportabile al modello di Pevzner, con le necessarie modifiche legate alla maggiore semplicità.

3.1 Il grafo di de Bruijn 31

Figura 3.3: Un esempio di compressione di un path lineare (in alto) in un DBG con k = 3. Il nodo risultante rappresenta la sequenza nucleotidica lunga

k+ (i − 1) = 6 con i numero di nodi del path.

3.1.5

Potenziali problemi

Un generico DBG, indipendentemente dal modello preso come riferimento, presenta alcuni potenziali problemi fra i quali pongo l’accento su due in parti-colare:

1. gli errori di sequenziamento si traducono in k-mer che potrebbero non far parte dell’insieme generato dai reads. Ciò si tradurrebbe certamente in nodi inconsistenti nel DBG che potrebbero portare ad archi e cammini inconsistenti.

2. per la logica con cui vengono posti gli edge, è possibile che esista un arco fra due nodi nonostante quel particolare path non sia previsto nei dati provenienti dai reads dell’esperimento.

Questi due problemi, a seconda dello scopo per cui viene costruito il DBG, possono portare a dei risultati sbagliati. Per far fronte a questi inconvenienti vengono applicate delle tecniche euristiche di controllo dei dati. Per risolvere il primo problema una tecnica consiste nel mantenere per ogni nodo il numero di

coverage, ossia quante volte la rispettiva k-mer è stata individuata fra i reads. I

nodi che presentano tale valore sotto una certa soglia stabilita, vengono rimossi in quanto classificati come errori di sequenziamento. Nel secondo caso possono, come controllo, essere applicate tecniche dette di read coherence come quella adottata in [30]: una volta individuato un path che ricostruisce una sequenza, questo viene allineato con i reads dell’esperimento e se almeno un nucleotide della sequenza non è “coperto” da nessun read, allora significa che il path non è read coherent.

3.2

Modello di analisi dei dati RNA-seq

L’approccio all’analisi dei dati che descriverò è interamente tratto da [30]. Gli ideatori sostengono che non è necessario portare a termine il difficile compito di riassemblare l’intera molecola, ponendo l’accento sul fatto che identificare SNP ed ASE è già fattibile solo per mezzo di una attenta analisi dei dati ed in particolare osservando e distinguendo alcune determinate strutture che assume il DBG proprio in tali regioni. Il modello di analisi mira quindi ad identificare e quantificare queste particolari strutture a partire dai dati RNA-seq, senza la necessità di nessun genoma di riferimento e senza dover riassemblare l’intero trascrittoma. Si tratta quindi di un processo differente, rispetto a quelli che tipicamente subiscono i dati provenienti da un NGS (descritti nel cap.2.2.2). Per facilitare la trattazione, le considerazioni sul modello di analisi verranno fatte su un cDBG associato al modello Pevzner, e cioè su un grafo direzionato

G = (V, E) con le caratteristiche ampiamente descritte nel capitolo 3.1.1 ed

i path lineari compressi come descritto nel capitolo 3.1.4. Rimarco però il fatto che le stesse considerazioni sono riportabili, con i dovuti adattamenti, a qualsiasi modello di DBG si decida di trattare, sia esso compresso o meno. Al termine del capitolo vedremo di analizzare anche quelli che sono i limiti derivanti dal modello descritto.

3.2.1

Caratterizzazione polimorfismi ed ASE nel DBG

1. Single Nucleotide Polimorphysm SNP (cap. 2.1.4) 2. Approximate Tandem Repeat ATR (cap. 2.1.4) 3. Alternative Splicing Events ASE (cap. 2.1.5)

Di seguito la prima importante osservazione che ci permette di separare polimorfismi ed ASE dal resto dei dati, preceduta da alcune definizioni:

Definizione 8 ((s,t)-path) Dati due vertici sv, tv ∈ V un (sv, tv)-path è un

path da sv(source) a tv(target).

Definizione 9 (bubble) Una (sv, tv)-bubble sono due vertex-disjoint (sv, tv

3.2 Modello di analisi dei dati RNA-seq 33

Definizione 10 (switching node) Chiamiamo i nodi sv, tv di una bubble

rispettivamente switching node sinistro e destro di una (sv, tv)-bubble.

Per vertex-disjoint path intendiamo due cammini che non hanno in comune nessun nodo eccetto i due switching sinistro e destro.

Osservazione: Polimorfismi ed ASE nel trascrittoma, così come nel

geno-ma, corrispondono a dei pattern particolari in un DBG/cDBG chiamati bubble.

Figura 3.4: In figura, l’esempio della particolare struttura, detta bubble, che assume un DBG nei pressi di polimorfismi o ASE.

Intuitivamente, le regioni polimorfiche e quelle di splicing corrisponderanno a path alternativi nel grafo mentre le parti comuni saranno l’inizio e la fine di entrambi. In generale, ogni processo che genera due path alternativi sxt e

syt nella sequenza, con s, t, x, y ∈ Σ∗ ed i corrispondenti nodi sv, tv, xv, yv ∈

V, crea delle bubble in un cDBG. Infatti, tutte le k-mer contenute in sv/tv

corrispondono all’inizio/fine comune del cammino e, dal momento che x 6= y, esiste almeno una coppia di k-mer, una in sx l’altra in sy, che condividono il prefisso k − 1 e differiscono dall’ultima lettera. In questo modo si crea una diramazione a partire dal nodo sv da cui nascono i due path alternativi. Lo

stesso discorso si può fare per xt, yt dove essi convergono.

Conosciamo ora una caratterizzazione che distingue le regioni polimorfi-che e quelle di splicing dalle restanti, ma come fare per distinguere fra i vari polimorfismi e gli ASE resta ancora da spiegare. Le prossime considerazioni chiariranno anche questo aspetto, ma anticipo che il principio di fondo sta nell’analizzare e confrontare le lunghezze fra i path delle varie bubble.

3.2.2

Eventi di Alternative Splicing

Un evento di splicing corrisponde a variazioni locali tra diversi trascrittomi, è caratterizzato da due parti (stringhe) comuni, s e t per usare la notazione precedente, e una parte variabile z.

Proposizione 1 Il path più corto di una bubble generata da un ASE del tipo

exon skipping ha lunghezza 2k − 2 ⇐⇒

(i) l’ultimo nucleotide della parte variabile z è diverso dall’ultimo nucleotide di sv ∧ (ii)il primo nucleotide della parte variabile z è diverso dal primo

nu-cleotide di tv.

Nel caso la (i)/(ii) non valgano i due path convergono/divergono prima ed il path più corto avrà lunghezza <2k − 2

Nel cDBG le parti comuni corrispondono ai nodi sv, tv. Dato che ci sono

k − 1 k-mer nella concatenazione st, fra i due path alternativi della bubble

senza contare s il path più corto sarà composto al massimo da k − 1 k-mers, che corrisponde ad una sequenza lunga 2k − 2. Come riportato in [30], a questa considerazione va aggiunto che nel genoma umano il 99% dei casi di ASE del tipo exon skipping conosciuti, generano bubble con cammino più corto mai inferiore a 2k − 8. In tale contesto abbiamo quindi anche la possibilità di imporre un limite inferiore per la lunghezza, nella fase di ricerca dei bubble.

Figura 3.5: Da un esperimento di RNA-seq vengono generate 2 stringhe s1 =

AAT GT T, s2 = AAT T CGCGT T . In s1 si ha un evento di exon skipping che

genera, in un cDBG con k = 3, due vertex disjoint path da s a t (path in alto e

pathin basso). Si noti che sono veri entrambi i predicati della Proposizione 1:(i)

( s[3]=T 6= z[4]=C) e (ii) (z[1]=T 6= t[1]=G); come conseguenza la sequenza più corta ha lunghezza esattamente 2k − 2 = 4.

3.2 Modello di analisi dei dati RNA-seq 35

Figura 3.6: Esempio di violazione del predicato (i) in Proposizione 1. La bubble risultante converge prima rispetto all’esempio 3.5, generando un path più corto di lunghezza minore a 2k − 2 (k = 3).

Figura 3.7: Esempio di violazione del predicato (ii) in Proposizione 1. La

bubble risultante diverge posticipatamente rispetto all’esempio 3.5, generando

un path più corto di lunghezza minorre a 2k − 2 (k = 3).

3.2.3

Single Nucleotide Polimorphism

Il polimorfismo a livello genomico, abbiamo detto (cap.2.1.4) e ripetuto nell’in-troduzione a questo capitolo, è presente anche a livello di trascrittoma quando interessa regioni codificanti (esoni). In particolare a livello genomico vediamo cosa accade per un evento SNP causato da sostituzione.

Proposizione 2 Una bubble generata da SNP di sostituzione presenta due

path alternativi di lunghezza identica pari a 2k-1.

La lunghezza del path più corto (uno dei due path essendo di pari lunghezza) di una bubble generata da SNP di sostituzione è 2k − 1, valore certamente maggiore rispetto alla lunghezza del massimo path corto generato da un ASE

Figura 3.8: Due stringhe s1 = AAT CT CG, s2 = AAT T T CG in cui si registra un evento di sostituzione: s1[3] 6= s2[3]. In un DBG (k = 3) generano una bubble con due path di lunghezza identica 2k − 1.

che abbiamo visto essere 2k − 2. Abbiamo quindi modo di differenziare questi particolari SNP dagli ASE.

Per quanto riguarda invece gli SNP causati da Indel la loro struttura è simile a quella degli ASE e le due bubble sono indistinguibili. Se però il modello di analisi lo applichiamo a dati provenienti dal genoma umano, la differenza di lunghezza tra i due path della stessa bubble ci può dare delle grandi indicazioni. Infatti alcuni studi [32] ci assicurano che nell’85% dei casi in cui tali eventi si manifestano, tale differenza è minore di 3 nucleotidi, mentre negli ASE nel 99% dei casi è maggiore di 3. Nel modello di analisi si può sfruttare questa sottile differenza, che inevitabilmente provocherà il rilevamento di una piccola percentuale di falsi positivi tra gli ASE/Indel classificati.

3.2.4

Approximate Tandem Repeat

Le bubble generate da ATR presentano una struttura simile a quelle generate da ASE nel DBG, ma la sequenza dei path consente di identificare facilmente la presenza di un pattern approssimato allineando il path più corto con la fine del path più lungo.

3.2.5

Limiti del modello

Il modello di analisi fin qui descritto presenta alcuni limiti. Innanzitutto, i vincoli sulla distinzione fra SNP Indel ed ASE di tipo exon skipping sono pensati per specializzare il modello all’analisi di dati provenienti dal genoma umano; perciò, se si volesse adottare lo stesso modello per effettuare analisi su

3.3 Metodo per rilevare polimorfismi ed ASE nel DBG: KisSplice37

altri tipi di dati, gli stessi vincoli non sarebbero validi. Un altro limite sta nella caratterizzazione che viene data alle bubble generate da eventi di Alternative

Splicing: questa non permette di identificare tutti gli ASE esistenti infatti ci

sono casi che vengono tagliati fuori. È il caso di ASE del tipo mutually exclusive

exon (2.1.5) attraverso i quali si possono presentare due o più cammini la

cui lunghezza sarà certamente maggiore di 2k − 1 mentre non esiste alcun limite superiore generico. Per individuare questi tipi di ASE sarebbe perciò necessario poter individuare tutte le bubble di un grafo. Nel capitolo 3.4.2 viene presentato un algoritmo che nasce proprio a tale scopo.

3.3

Metodo per rilevare polimorfismi ed ASE

nel DBG: KisSplice

KisSplice (KS) è uno strumento di analisi di dati RNA-seq presentato nell’A-prile del 2012 in RECOMB, una conferenza internazionale che si tiene annual-mente per la ricerca in materia di Computational Molecular Biology. In [30], viene spiegato il suo funzionamento che si basa sui principi definiti dal modello di analisi del precedente paragrafo (da cui è stato tratto). KS è composto da una pipeline sequenziale di sei passi:

1. Costruzione DBG.

dati i reads di un esperimento RNA-seq viene costruito un DBG modello Medvedev. Per ogni nodo sono mantenute le informazioni di coverage della k-mer corrispondente. Per minimizzare gli errori di sequenziamento i nodi con coverage 1 vengono rimossi (cap.3.1.5).

2. Scomposizione DBG in componenti biconnesse (BCC).

Un grafo non direzionato G(V, E) è biconnesso se resta connesso anche dopo la rimozione di un qualunque v ∈ V . Un BCCi di un grafo non

direzionato è un sottografo biconnesso massimale. È dimostrabile co-me ogni BCC in un grafo non direzionato forma una partizione di E che ha due importanti proprietà: ogni (s,t)-bubble si troverà esclusiva-mente in un BCC; ogni arco non contenuto in un (s,t)-bubble formerà un BCC composto da un unico nodo. La scomposizione in componen-ti biconnesse è realizzata nel DBG eseguendo una versione modificata dell’attraversamento depth-first [31].

Figura 3.9: Da un grafo vengono individuate 4 componenti biconnesse. Possono esistere nodi che fanno parte di più di una bcc.

3. Compressione di cammini.

In questo passo della pipeline avviene la compressione dei path lineari. A partire da ogni bcc verrà ottenuto il rispettivo cDBG (3.1.4). Inoltre un’altra importante considerazione viene fatta per agevolare la ricerca di ASE: gli SNP, che siano anche semplici errori di sequenziamento, ge-nerano un gran numero di bubble che possono a loro volta essere incluse in bubble più grandi. Questo step di KisSplice intercetta e comprime tutte le (s,t)-bubbles di soli 4 nodi: i due switching-node (cap.10) s e t (cap.3.2.1), e i due path separati composti da un unico nodo e contenenti una sequenza di uguale lunghezza (fig. 3.8). Per compressione in questo caso si intende che tutte le strutture di questo tipo vengono fuse in un unico path lineare formato da 3 nodi: s,x,t dove nella kmer del nodo x lo SNP viene sostituito con il carattere speciale N.

4. Identificazione di (s,t)-bubble.

Vengono cercati (s,t)-bubble nel cDBG usando il metodo Tiernan [33] unito a due criteri fondamentali: l’esplorazione di un ciclo viene fermata se il ciclo contiene più di due switching-nodes (oltre s e t) o se durante l’attraversamento del path da s a t si supera la dimensione 2k-2 (cap. 3.2.1).

5. Filtraggio e classificazione risultati.

I due path di ogni bubble vengono allineati. Se il path più corto si allinea con alta similarità al path più lungo, la bubble viene classificata come

3.4 Identificare bubbles in un grafo orientato: MouthCycle 39

approximate tandem repeat altrimenti viene classificata come ASE o Indel

a seconda che la differenza fra i due path sia ≥ 3 nucleotidi o meno. 6. Read Coherence e verifica coverage.

La read coherence verifica che i path ritrovati dal metodo rappresentino effettivamente una sequenza del trascrittoma analizzato. I reads vengo-no mappati in ognuvengo-no dei due path ritrovati, se almevengo-no un nucleotide non è “coperto” da nessun read il path viene scartato come non read

co-herent (cap. 3.1.5). Viene inoltre calcolata la copertura di ogni singolo

nucleotide come numero di read che si sovrappongono nella sua posizione. L’algoritmo di ricerca dei bubbles impiegato da KS nel punto 4, è rea-lizzato allo scopo di ricercare esclusivamente quei bubbles che rispondono ai vincoli decisi nel modello di analisi. Questi vincoli, abbiamo visto nel capito-lo precedente, come non riescano ad individuare tutti gli ASE. Nel prossimo capitolo presenterò un algoritmo in grado di individuare tutte le bubble in un grafo direzionato ed inoltre migliore in termini computazionali rispetto a quello impiegato in KisSplice.

3.4

Identificare bubbles in un grafo orientato:

MouthCycle

In questo paragrafo verrà presentato un algoritmo chiamato MouthCycle che nasce allo scopo di identificare tutte le bubble presenti in un grafo orientato, nel nostro contesto verrà applicato sul DBG con l’obiettivo di risolvere i limiti precedentemente esposti di KisSplice. MouthCycle prende il nome dal fatto che le bubble possono essere viste come delle bocche, in inglese mouth, viene descritto dettagliatamente in [33] ed ha una valenza teorica piuttosto elevata in quanto è il primo algoritmo attraverso il quale è possibile risolvere il problema dell’enumerazione di bubble in polynomial delay, ciò significa che il numero di attraversamenti massimo che intercorre tra l’output di due bubble consecutive è O(|V | + |E|). Un metodo simile è stato già impiegato in [30], che presenta un adattamento all’algoritmo di Tiernan del 1970 [34], il quale non ha però

polynomial delay. MouthCycle deriva dall’adattamento di un altro algoritmo,

quello di Johnoson del 1975 [36], il quale, come d’altronde anche Tiernan, risol-ve un problema apparentemente dirisol-verso: i due algoritmi nascono con l’intento di identificare i cosiddetti elementary circuits o cicli elementari in un grafo

direzionato. Questi cicli hanno la caratteristica che uno stesso nodo non può essere attraversato più di una volta. Vedremo che il nostro problema iniziale però può essere riadattato alla ricerca di particolari cicli elementari e di seguito spiegherò come questo sia possibile. Per semplicità di trattazione l’algoritmo farà riferimento al DBG modello Pevzner (cap. 3.1.1), ma bisogna sottolineare anche stavolta il fatto che il discorso può essere esteso anche agli altri modelli con i dovuti accorgimenti. Inoltre, rispetto a quella descritta in seguito, an-ticipiamo che esiste una versione con stessa complessità computazionale ma migliore efficienza in termini di spazio occupato.

3.4.1

Descrizione metodologia

Sia G = (V, E) un grafo orientato e siano s, t ∈ V , richiamiamo due definizioni già date nel (cap.3.2.1):

Definizione 11 ((s,t)-bubble) Con (s,t)-bubble intendiamo due vertex

di-sjoint (s,t)-path ovvero due (s,t)-path che non hanno alcun nodo in comune.

Definizione 12 ((s,t)-path) Un (s,t)-path è un cammino da un source-node

s ad un target-node t.

MouthCycle fondamentalmente si divide in due fasi distinte: 1. trasformazione di G in un grafo G0

s = (Vs0, Es0).

2. ricerca in G0

s di particolari cicli elementari.

Di seguito approfondiamo queste due distinte fasi dell’algoritmo ad iniziare dalla fase di trasformazione.

(FASE 1): Trasformazione G in G0_s

Il grafo direzionato G = (V, E) viene trasformato in un grafo G0

s = (V

0

s, E

0

s),

dove s è un parametro fondamentale nella costruzione e corrisponde ad un qualunque source-node s ∈ V :

V_s0 = {v, ¯v|v ∈ V }

3.4 Identificare bubbles in un grafo orientato: MouthCycle 41

Vediamo di descrivere a parole il formalismo: l’insieme dei nodi V0

s sarà

costituito da tutti i nodi v ∈ V e per ognuno di essi verrà aggiunto un nuovo nodo che denoteremo ¯v. In seguito con la notazione ¯V = V0

s/V ci riferiremo ai

soli nodi del tipo ¯x.

Definizione 13 (twin vertices) Due vertici x,¯x ∈ V_s0 sono detti twin verti-ces, nodi gemelli.

L’insieme degli edge E0

s sarà invece costituito da l’unione di questo elenco:

1. gli stessi archi di G meno tutti gli archi entranti in s.

2. per ogni arco (u, v) ∈ E aggiungeremo un arco nel senso opposto fra i rispettivi twin vertices (¯v, ¯u).

3. un arco (v, ¯v) che congiungerà ogni nodo v ∈ V al suo nodo twin corri-spondente fatta eccezione del source-node s.

4. un arco (¯s, s) che congiungerà ¯s ad s stesso.

Definizione 14 (twin arc) Definiamo twin arc ogni arco(¯v, ¯u) ∈ E_s0 fra twin nodes.

Figura 3.10: A sinistra un grafo G, a destra il rispettivo grafo G0

s ottenuto

applicandogli la procedura di trasformazione descritta. [33]

(FASE 2): Ricerca cicli elementari in G0_s

Definizione 15 (bipolar cycle) Un ciclo in G0_s è detto bipolare se contiene vertici sia in V che in ¯V

Definizione 16 (swap arc) Definiamo swap arc l’arco (t, ¯t) ∈ E_s0 che con-giunge il target-node t al suo nodo gemello ¯t per un qualche t ∈ V .