file in formato fasta.
La funzione di validazione riceve in ingresso lo stack in modo da effetture la riduzione della corrispondenza tra bubble-cycle/(s,t)-bubble (cap. 3.4.3) così come avveniva nella versione di MouthCycle precedente. In più sfruttando l’accesso immediato alle proprietà di st_stringpath1, st_stringpath2, controlla che tutti i vincoli del modello di analisi di KisSplice siano rispettati. Oltre ai
bubble che non rispettano i vincoli di lunghezza delle ASE exon skipping, viene
anche effettuato, così come in KS, un controllo per invalidare gli Indel, quei
bubble in cui il path più corto ha edit distance minore di 3 rispetto al path più
lungo (cap. 3.2).
Con queste modifiche le funzionalità dei due algoritmi di ricerca bubbles sono perfettamente allineate.
4.3
Sperimentazione
Raggiunto il perfetto allineamento fra le due pipeline, tramite la sostituzio- ne del modulo della pipeline KS per la ricerca di bubble con MouthCycle ed attraverso alcuni altri accorgimenti spiegati dettagliatamente nel capitolo pre- cedente, siamo riusciti ad ottenere uno strumento di analisi dati RNA-seq che risolve lo stesso problema di KS e che abbiamo chiamato KisSplice con Mouth-
Cycle (KMC). È importante nuovamente sottolineare che, poichè MouthCycle
è in grado di individuare tutte le bubble in un grafo orientato, per allineare i risultati ottenuti dai due strumenti si è dovuto ridurre la quantità di dati prodotta in output da MouthCycle andando a validare esclusivamente quelli che rispondono ai vincoli stabiliti dal modello KS e scartando tutti gli altri. In questo modo si è intervenuto in un certo senso riducendo le potenzialità di KMC a livello di dati restituiti, che si presenta come strumento con caratte- ristiche superiori rispetto a KS. Infatti il modulo di ricerca bubble di KS è in grado di individuare esclusivamente quelle bubble che rispondono ai vincoli ed interrompe l’attraversamento del grafo non appena uno di essi viene violato. In questa sezione mostriamo i dati relativi ai tempi di esecuzione dei moduli di ricerca bubble di KS e KMC eseguiti entrambi in una macchina con proces- sore Intel Core 2 Duo 1.8 GHz e 2 Gb di RAM. Sono state effettuate le prove su due distinti file in input: liver.fasta, brain.fasta contenenti i reads di due esperimenti RNA-seq eseguiti sul DNA prelevato dal fegato e dal cervello di uno stesso individuo. La differenza di contenuto fra i due file dipende dal fatto
che gli stessi geni, presi da diversi tessuti esprimono diversi trascrittomi.
Figura 4.6: BCC ottenuti dal DBG relativo al file liver con K=25. Nelle ordinate si ha il numero di diverse BCC che contengono il numero di nodi in ascissa.
Figura 4.7: BCC ottenuti dal DBG relativo al file brain con K=25. Nelle ordinate si ha il numero di diverse BCC che contengono il numero di nodi in ascissa.
Caratteristiche input
La dimensione di entrambi i dati in input è di ∼56Mb. Attraverso il file
liver.fastail primo modulo della pipeline produce con k=25 un DBG di 2608558
nodi e 5177958 archi che viene suddiviso in 321 bcc. Attraverso brain.fasta viene generato un DBG di 1736613 nodi e 3597580 archi che viene suddiviso in 452 bcc. I grafici in figura 4.6 e 4.7 ci danno una idea riguardo le dimensioni dei BCC prodotti dai due diversi file in input.
4.3 Sperimentazione 61
Figura 4.8: Confronto tempi di esecuzione pipeline KisSplice(KS), KisSplice con MouthCycle (KMC).
Test
Nella pratica, KisSplice ha numerosi altri parametri rispetto a quelli descritti in [30] fra i quali: pone un limite, tramite timeout, al tempo di esecuzione dell’algoritmo di ricerca bubble che di default è impostato a 15 minuti; pone inoltre un limite al numero di bubble identificate di default impostato a 10000. Per allineare definitivamente la nostra pipeline viene impostato in KMC un timeout di uguale valore, in particolare, i tempi saranno presi con timeout di 5 e 15 minuti mentre il limite sul numero di bubble di KS viene rimosso. Un altro accorgimento preso in entrambe le pipeline consiste nell’evitare di analizzare i bcc che presentano una dimensione inferiore ai 4 nodi perchè certamente non conterranno alcuna bubble.
In figura 4.8 possiamo vedere una tabella riassuntiva contenente il confronto sui tempi di esecuzione delle due pipeline. Per entrambi i file in input, KMC termina in minor tempo rispetto a KS, in particolare si noti che per il file
brain il divario fra le due pipeline resta grosso modo inalterato al variare del
parametro di timeout. In questo caso infatti esiste una bcc per cui entrambi gli algoritmi di ricerca bubble terminano forzatamente per opera del timeout, ma dove KMC impiega una decina di secondi per analizzare le restanti bcc, KS impiega ∼ 4’20s. Andando invece ad analizzare i tempi relativi al file liver, non si osserva la stessa regolarità descritta in precedenza. In questo caso, infatti, mentre KS fa scattare 2 timeout in entrambi i casi di 5’ e 15’, KMC con il timeout impostato a 15’ riesce a terminare l’analisi di una bcc anzitempo richiedendo un solo timeout. A questo è dovuto il maggior divario tra i tempi
di esecuzione relativi al file liver: con timeout impostato a 5’ la differenza è ∼ 3’, mentre con timeout impostato a 15’ la differenza è ∼14’.
Capitolo 5
Conclusioni
In questo lavoro di tesi viene presentata la prima implementazione dell’al- goritmo MouthCycle per la ricerca di bubble in un grafo orientato. Al fine di esibire un risvolto pratico alla sua efficienza garantita finora solo dall’otti- malità a livello teorico, abbiamo individuato un’applicazione che richiedesse al suo interno una ricerca di bubble, con l’intento di verificare se l’algoritmo MouthCycle potesse migliorare le performance di tool esistenti, estendendone dunque anche l’applicabilità. L’applicazione individuata è KisSplice, un soft- ware di analisi per la ricerca di polimorfismi ed eventi di alternative splicing nei dati RNA-seq, presentato alla conferenza internazionale di bioinformatica RECOMB 2012. In KisSplice siamo intervenuti inserendo la nostra implemen- tazione di MouthCycle in modo da sostituire un modulo destinato al medesimo compito, ma che si presenta con alcuni importanti limiti: è in grado solamente di rilevare bubble che hanno determinate caratteristiche di lunghezza dei path. Proprio per questo motivo il nuovo strumento di analisi KMC, ottenuto dall’in- tegrazione in KisSplice di MouthCycle, si presenta con potenzialità superiori avendo MouthCycle la funzione di rilevare invece, tutte quante, le bubble in un grafo orientato. Questa funzionalità aggiunta consente di intercettare, come abbiamo mostrato a livello teorico, anche eventi di alternative splicing del tipo Mutually Exclusive Exon, che dal tool originale non venivano invece conside- rati proprio a causa dei vincoli imposti alle bubble in fase di ricerca. Con la consapevolezza quindi che il confronto dei tempi di esecuzione fra i due tool di analisi, per le differenze precedentemente evidenziate, è unfair in quanto KMC svolgendo un lavoro maggiore parte svantaggiato, nella fase di testing si è osservato che l’ottimalità di MouthCycle riesce comunque a sopperire a ta- le disallineamento, migliorando consistentemente i tempi d’attesa dei risultati
finali. Questo conferma dunque l’efficienza al lato pratico dell’algoritmo e ne estende la sua applicabilità, andando a rispondere concretamente agli obiettivi prefissati dal lavoro di tesi.
Sviluppi Futuri
Quello descritto in questa tesi rappresenta il nucleo di un lavoro che non può ritenersi concluso in quanto può essere esteso e certamente migliorato sotto diversi aspetti, offre inoltre lo spunto per altri studi rilevanti anche indipen- dentemente dal contesto trattato. Di seguito espongo alcune di queste idee, va ovviamente sottolineato la loro effettiva efficienza è tutta da dimostrare.
Poniamo innanzitutto l’accento su alcune modifiche che consentirebbero di perfezionare il tool di analisi dati RNA-seq:
• Al termine dei primi tre passi della pipeline KisSplice ci troviamo con un certo numero di biconnected component su disco. Su ognuno di essi viene eseguito MouthCycle e ciascuna esecuzione è indipendente dalle altre. Siamo di fronte ad un problema embarassingly parallel. Sfruttando il parallelismo, in linea teorica dovremmo essere in grado di ridurre il tempo di esecuzione complessivo del modulo di ricerca bubble.
• Sarebbe inoltre interessante valutare l’impatto di un’implementazione della pipeline in parallelo sui tempi di esecuzione.
• Infine i passi 2,3,4 della pipeline potrebbero essere compressi in un unico passo in cui dal DBG iniziale, per ogni biconnected component estrat- to, venga effettuata la compressione dei cammini e l’identificazione dei bubble con MouthCycle, evitando la scrittura su disco.
Uno dei quesiti, che questo lavoro lascia ad un passo dalla risposta, ri- guarda la verifica sperimentale che KMC riesca a trovare eventi di alternative splicing del tipo Mutually Exclusive Exon. Sebbene da un punto di vista teo- rico la risposta sia affermativa, la certezza si può avere solo con un riscontro pratico. Ad ogni modo, per estendere il tool di analisi dati RNA-seq alla ricer- ca di eventi Mutually Exclusive Exon, è necessario studiare un nuovo modello di analisi.
65
Da un punto di vista algoritmico sarebbe interessante studiare un ag- giornamento di MouthCycle per fare in modo che termini l’attraversamento del grafo non appena un vincolo sia violato. Si tratterebbe di gestire la ricerca di bubble vincolata on the fly; questa soluzione applicata al nostro contesto consentirebbe un notevole miglioramento delle prestazioni.
Infine un lavoro interessante dal punto di vista dell’ottimizzazione con- sisterebbe nello studiare come variano la precisione e l’accuratezza dello stru- mento, analizzando i risultati ottenuti in funzione della dimensione delle k-mer nel grafo di De Bruijn.
[1] Watson J.D., Crick F.H. Molecular structure of nucleic acids: a structure
for deoxyribose nucleic acid. Nature 171 (1953), 737-738.
[2] Nirenberg M., Leder P., Bernfield M. RNA codewords and protein syn-
thesis, VII. On the general nature of the RNA code. Proc Natl Acad Sci
U S A 5 (1965), 1161-1168.
[3] Crick F.H. On Protein Synthesis. Symp. Soc. Exp. Biol. XII (1958), 139–163.
[4] Crick F.H. Central Dogma of Molecular Biology. Nature 227 (1970), 561–563.
[5] McCarthy B.J., Holland J.J. Denatured DNA as a Direct Template for
in vitro Protein Synthesis. Biochemistry 54 (1965), 880-886.
[6] Black D. L. Mechanisms of alternative pre-messenger RNA splicing. Annual Reviews of Biochemistry 72 (2003), 291-336.
[7] Whibley C., Pharoah P.D., Hollstein M. p53 polymorphisms: cancer
implications. Nature Reviews Cancer 9 (2009), 95-107.
[8] Taze J., Bakkour N., Stamm S. Alternative splicing and disease. Biochimica et Biophysica Acta 1 (1972), 14-26.
[9] Garcia-Blanco M.A., Baraniak A.P., Lasda E.L. Alternative splicing in
disease and therapy. Nature Biotechnology 5 (2004), 535-546.
[10] Schulz M.H. Data Structures and Algotithms for Analysis of Alternative
Spliing with RNA-seq Data. PhD thesis, Free University of Berlin (2010).
[11] Matlin A.J., Clark F., Smith C.W. Understanding alternative splicing:
towards a cellular code. Nature Reviews 6 (2005), 386-398.
BIBLIOGRAFIA 67
[12] Skotheim R.I., Nees M. Alternative splicing in cancer: noise, functional,
or systematic. The international journal of biochemistry and cell biology
39 (2007), 1432-1449.
[13] Fackenthal J.D., Godley L.A. Aberrant RNA splicing and its functional
consequences in cancer cells. Disease models and mechanisms 1 (2008),
37–42.
[14] Sanger F., et al. DNA sequencing with chain-terminating inhibitors. Proc. Natl. Acad. Sci. U. S. A.74 (1977), 5463-5467.
[15] Metzker M.L. Sequencing technologies — the next generation. Nature Reviews Genetics 11 (2010), 31-46.
[16] Metzker M.L. Emerging technologies in DNA sequencing. Genome Research 15 (2005), 1767-1776.
[17] Sanger F., Nicklen S., Coulson A.R. DNA sequencing with chain-
terminating inhibitors. Proc. Natl. Acad. Sci. U.S.A. 12 (1977),
5463–5467.
[18] Mardis E.R. The impact of the next-generation sequencing technology on
genetics. Trends in Genetics 24 (2007), 133-141.
[19] Pevzner P.A., Tang H., Waterman M.S. An Eulerian path approach to
DNA fragment assembly. PNAS 17 (2001), 9748-9753.
[20] Trapnell C., Salzberg S.L. How to map billions of short reads onto
genomes. Nature Biotechnology 7 (2009), 455-457.
[21] Pop M., Salzberg S.L. Bioinformatics challenges of new sequencing
technology. Trends Genetics 3 (2008), 142-149.
[22] Wang Z., Gerstein M., Snyder M. RNA-seq: a revolutionary tool for
transcriptomics. Nature Reviews Genetics 1 (2009), 57-63.
[23] Fatih O., Platt A.R., Jones D.R et al. Direct RNA sequencing. Nature
461 (2009), 814-818.
[24] Fatih O., Milos P.M. RNA sequencing: advances, challenges and
[25] De Bruijn N.G. A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen 49 (1946), 758-764.
[26] Idury R.M., Waterman M.S. A new algorithm for DNA sequence
assembly. Journal of computational biology 2 (1995), 291-306.
[27] Compeau P.E.C., Pavzner P.A. How to apply de Bruijn graphs to genome
assembly. Nature Biotechnology 29 (2011), 987-991.
[28] Medvedev P., Georgiou K., Myers G., Brudno M. Computability of
Models for Sequence Assembly. Wabi 13 (2007), 289-301.
[29] Pevzner P.A. 1-Tuple DNA sequencing: computer analysis. Journal of Biomolecular Structure and Dynamics 7 (1989), 63-73.
[30] Sacomoto G. et al.: KisSplice: de-novo calling alternative splicing events
from rna-seq data. BMC Bioinformatics 13 (2012) (Suppl 6):S5.
[31] Tarjan R.E., Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing 2 (1972), 146-160.
[32] Sherry S.T., Ward M.H., Kholodov M., et al.: dbSNP: the NCBI database
of genetic variation. Nucleic Acids Research, 29 (2001), 308-311.
[33] Birmelè E., Crescenzi P., Ferreira R. et al.: Efficient bubble enumera-
tion in directed graphs. proceedings of String Processing and Information
Retrieval (SPIRE) 2012, Springer LNCS, 2012. In press.
[34] Tiernan J.C. An efficient search algorithm to find the elementary circuits
of a graph. Commun. ACM 3 (1970), 722-726.
[35] Johnson D.B. Finding all the elementary circuits of a direct graph. SIAM Journal on Computing 1 (1975), 77-84.
[36] Johnson D.B. Improvement of Short Read Genome Assembly with Graph