Development and Application of New Strategies for Genome Scaffolding and Gene Predictio applied to NGS data

Next Generation Sequencing (NGS) technologies have a great impact both at economical and at research level, with the increasing of data production and the cost reduction and. This new kind of techniques allow the sequencing of thousands of genomes from humans to microbes and they open entirely new areas of biological inquiry, including the investigation of ancient genomes, of human disease, the characterization of ecological diversity, and the identification of unknown etiological agents. The application field could be divided into three main arguments: genomic tasks (genome assembly, SNPs and structural variations), transcriptome analysis (gene prediction and annotation, alternative splicing discovering) and epigenetic problems. The new technologies also offer challenges in experimental design, data management and analysis. In particular, it is desirable to have analysis keep pace with data production, and thus new bioinformatics tools are being developed. Three platforms for DNA sequencing read production are in reasonably widespread use: the Roche/454, the Illumina/Solexa Genome Analyzer and the Applied Biosystems SOLiDTM System. The Roche/454 is the first to achieve commercial introduction (in 2005) and it uses an innovative sequencing technology known as pyrosequencing. It produces sequences 300-400 bases, longer than Illumina/Solexa (about 70 bases) and SOLiD/Applied Biosystem (about 50 bases), but with a lower high throughput. During my Ph.D., the Next Generation Sequencing has become a wide spread practice and the aim of my research is the development of new proper tools. I hoped to create useful programs, that would be able to transform the large amount of produced raw data into useful information for biology tasks in few time. With my research and my algorithms, I collaborated to the development and solution of two of the most challenging and studied applications: genome assembly and gene prediction. De novo sequencing is the starting point of any possible genetic analysis with the creation of the original genomic sequence. This explain why de novo sequencing and genome assembly are very important and studied problems. With Next Generation Sequencing the task has began even more challenging: the reduced time and cost allows to sequence even long organisms. When I started my Ph.D., there were only few programs that were able to perform de novo assembly, and among these the most used were Newbler, Velvet and Cabog. My aim was to improve the current state of the art, developing a new assembly tool that use the strengths and overcome the weaknesses of the cited programs. Moreover, the new program should be able to work with any kind of data (Next Generation Sequencing and other available evidences), and to produce a well-defined genome assembly. Many efficient assembler have been implemented yet, but quite all of them are able to produce only unconnected fragments (contigs) of the original genome. In many cases, they were not able to realize the final scaffolding: set of well ordered and oriented contigs. Only few of them performs this task, that is useful to move toward the finishing of the assembly. The idea is to work in this direction: the development of a platform that is able to correctly order and orient a set of contigs, connected among them through mate-pairs, into scaffolds. The tool would be able to control the “consistency” of the starting assembly and correct the error of the links, to produce a genome sequence and reduce the background noise. The best strategy is to create contigs using Roche/454 reads and Newbler assembler, and mate-pair reads with Illumina or SOLiD. Gene prediction is a well studied and known problem. Over the past, a lot of program have been developed (Jigsaw, GeneID, GeneSplicer, Genscan, Glimmer, SNAP, TigrScan, Twinscan,...), and the reached results allow to predict quite all genes with a high specificity and sensibility level. After an accurate analysis, I found that a common weak point of all the programs was the requirement of a starting training set, from which learning the rules of the organism gene structure, used for the future prediction. Unfortunately, very often this set is not available and it is necessary to create a new one, using information coming from similar organism or from other source of evidences (EST, proteins,... ) . My idea was to use Next Generation Sequencing data to create a starting set of proper genes, sequencing the transcriptome, aligning the produced reads on the genome sequence and discovering the exons and introns to reconstruct the gene structure.

La commercializzazione delle nuove tecnologie di sequenziamento (NGS, Next Generation Sequencing), ha avuto un grande impatto sia a livello economico sia biologico, grazie alla significativa riduzione dei tempri di produzione e dei costi, e all’aumento della quantità di dati ottenuti. Le nuove tecniche di sequenziamento hanno permesso di ricreare il genoma di migliaia di organismi, sia piccoli come i microbi, sia grandi come il genoma umano, aprendo nuove aree di ricerca. Ad esempio, ora è possibile studiare il DNA antico, fare ricerca su malattie genetiche, studiare caratteristiche e differenze evolutive tra organismi,... I nuovi metodi si possono applicare a tre campi principali: genomico (come l’assemblaggio dei genomi, la ricerca di SNPs e variazioni strutturali), trascrittomico (per eseguire la predizione genica, l’annotazione e lo studio di splicing alternativi) ed epigenetico. I sequenziatori di nuova generazione hanno apportato cambiamenti anche a livello bioinformatico. Infatti, con l’acquisizione di moli di dati sempre più grandi, si è reso necessario affrontare il problema della loro gestione dal punto di vista sia di tempo computazionale per analizzarli sia di memoria richiesta per immagazzinarli. Inoltre, si è resa necessaria l’implementazione di strumenti in grado di elaborare i dati grezzi ottenuti, per trasformali in utili informazioni da applicare nelle analisi biologiche. Attualmente le tre piattaforme di sequenziamento più utilizzate sono Roche/454 , Illumina/Solexa Genome Analyzer, e Applied Biosystems SOLiDTM. Il primo sequenziatore ad essere commercializzato nel 2005 fu il 454. Si basa su tecniche di sequenziamento innovative (pyrosequencing) ed è in grado di produrre sequenze lunghe 300-400 basi, con una buona qualità media. Tuttavia il 454 non raggiunge i livelli di produzione di altri sequenziatori, come SOLiD ed Illumina, che in poco tempo sono in grado di produrre milioni di sequenze, anche se di dimensioni minori (circa 50 e 70 basi rispettivamente per SOLiD e Illumina). L’idea del mio dottorato è di applicare le conoscenze matematiche ed informatiche allo studio di nuove tecniche per l’utilizzo dei dati di nuova generazione in problemi biologici. Lo scopo è di sviluppare dei programmi in grado di elaborare grandi quantità di dati in poco tempo. Con la mia ricerca ho collaborato all’implementazione di metodi per la risoluzione di problemi di assemblaggio e di predizione genica. Il sequenziamento de novo e successivamente l’assemblaggio sono un punto fondamentale per l’analisi del genoma di un organismo. Attualmente il problema dell’assemblaggio è un problema ancora aperto e ampiamente studiato: non esistono ancora programmi in grado di ricostruire un genoma completo partendo da reads prodotte con un sequenziamento di nuova generazione. Esistono software come Newbler, Velvet e Cabog che producono lunghi frammenti di sequenza (contigs), ma tra loro disgiunti e di cui non si conosce la corretta posizione occupata all’interno del genoma d’origine. Alla maggior parte dei programmi manca una fase di “scaffolding” e “finishing”, in cui tutti i frammenti prodotti con l’assemblaggio vengono ordinati e orientati, creando gli scaffolds. Il mio scopo era di realizzare un metodo di scaffolding, Consort, e di analisi per il miglioramento dell’assemblaggio ottenuto. Il programma richiede come dati di input un insieme di contigs prodotti assemblando le reads 454 con il Newbler, e un insieme di mate-pairs generati con il SOLiD. La predizione genica è stata la mia seconda area di ricerca. E’ un problema ben studiato e negli anni moltissimi programmi sono stati sviluppati per predire efficientemente i geni contenuti in un genoma. Tra questi i più utilizzati e conosciuti sono: Jigsaw, GeneID, GeneSplice, Genscan, Glimmer, SNAP, TigrScan, Twinscan. La maggior parte dei software richiede un insieme di dati di allenamento dal quale apprendere le caratteristiche per eseguire la successiva predizione, che molto spesso non sono disponibili. Pertanto, si devono creare a partire da genomi simili. Tuttavia, questa soluzione non è sempre applicabile, anche se molto spesso lavora bene e permette di ottenere buon risultati. Infatti, se l’organismo studiato è nuovo e non se ne conoscono altri di abbastanza vicini, si rischia di non avere i i dati richiesti. La mia ricerca in quest’area si applica allo sviluppo di un metodo di creazione di un insieme di dati di allenamento a partire da sequenze di trascriptoma dello stesso organismo. L’idea è di allineare le reads prodotte sul genoma e di estrarre tutte le regioni individuate, che sono potenziali geni. L’algoritmo implementato ha mostrato la possibilità di ricavare insieme di dati sicuri con questa tecnica. Tuttavia, il metodo è soggetto alla predizione di molti falsi positivi a causa dell’elevato rumore di fondo. Per evitare di creare un training set poco affidabile, è preferibile essere molto stringenti nei criteri di selezione dei geni.