Design and implementation of novel algorithms to integrate different DNA sequencing technologies for de novo genome assembly: Nannochloropsis as a test case

The advent of next generation sequencing technologies marked the beginning of a new era in the production of genomic data; nonetheless it also offered novel challenges to the bioinformatics community. While re-sequencing of genomes was made relatively easy and cheap, de novo assembly of eukaryotic genomes still presents significant hurdles. In this thesis we attempted the application of a mixed-techniques approach to the de novo sequencing of a small eukaryotic genome, that could allow us to takes advantage of both the relatively long reads obtainable using the Roche 454 and the incredibly high coverage of short reads allowed by SOLiD sequencer. The application of a hierarchical approach based on the production of reliable contigs using the 454 and the assembly of these contigs in scaffold using the SOLiD mate pairs, could represent a cost effective strategy to address this important issue. To realize this project a contig-centered data repository, called 4ngs, was produced that allowed the real time interrogation of partially assembled data as well as the evaluation of the assembly and the design of new experiments. Moreover I designed and implemented a scaffolding algorithm, ScaMP (Scaffolding with Mate Pairs), that uses the SOLiD mate-paired reads aligned to the reference contigs, to produce and store scaffolds in the 4ngs database. To further improve the assembly results, a gap closure pipeline was also developed that allows joining adjacent contigs using the SOLiD short sequences. I assessed the performance of both programs using as a test case the genome of a microalga, Nannochloropsis gaditana, which received pressing attention from the scientific community for its potential for biofuel production. The genome (that has an estimated size spanning between 30 and 40 Mbp) has been sequenced with a low-coverage 454 (that produced more than 12,000 contigs) and with SOLiD Mate Paired libraries. Scaffolding performed with my platform produced 95 scaffolds that include 26.8 Mbp of the genome and have an average size of 285,594 bp. The gap filling pipeline closed more than 3,000 gaps between adjacent contigs, and gave best results for scaffolded regions (the largest scaffold, composed by 140 contigs, had 106 gaps closed raising N50 of its contigs from 8.3 kbp to 77.4 kbp). My study fulfilled the expectation that for a small eukaryotic genome, de novo assembly starting from next generation data alone is feasible, cheap and efficient; that a mixture of SOLiD and 454 sequencing substantially improves the assembly; and that the quality of the resulting genome draft is enough to support further analysis of comparative genomics and to obtain a valuable framework to design the application of recombinant techniques. A good quality draft of N. gaditana genome was produced in this thesis, meeting the need of the scientific community for valuable tools able to boost the application of the new genomics resources to a vast plethora of biological problems and to serve new and interesting biotechnological applications.

L’avvento e la rapida evoluzione dei sequenziatori di nuova generazione (NGS) ha abbattuto il costo ed il tempo necessario alla produzione dei dati. La fase di assemblaggio di un genoma che porta ad ottenere la corretta sequenza genomica a partire dalle singole sequenze prodotte dai sequenziatori è sempre stato un processo complesso, e l’aumento della mole di dati prodotti non è corrisposto ad una nostra aumentata capacità di analisi degli stessi. In questa tesi si presenta un approccio misto di sequenziamento che combina i benefici di due sequenziatori di nuova generazione (il 454 di Roche che fornisce le sequenze più lunghe ed il SOLiD di Applied Biosystems che fornisce una massiva produzione di sequenze, ciascuna di lunghezza ridotta) al fine di ottenere le informazioni per il sequenziamento di un genoma. La strategia è stata testata sul genoma della microalga eucariote Nannochloropsis gaditana, un organismo che negli ultimi anni ha ricevuto notevole attenzione dalla comuntità scientifica per la sua capacità di immagazzinare energia luminosa sotto forma di acidi grassi (fino al 70% del suo peso). Questa caratteristica rende Nannochloropsis un valido candidato per le ricerche su fonti di energie alternative a quelle di origine fossile. La stima della dimensione del suo genoma varia tra i 30 ed i 40 milioni di paia di basi. Il rapido miglioramento delle tecnologie di sequenziamento non è corrisposto ad una altrattanto rapida evoluzione dei programmi di analisi dei dati, che spesso risultano indeguati a gestire la nuova mole di dati o a sfruttarne le potenzialità. Per questo ho deciso di progettare ed implementare una collezione di programmi per l’assemblaggio di genomi con dati misti (SOLiD e 454). Le sequenze ottenute da un sequenziamento di tipo shotgun con il 454 vengono assemblate per produrre un insieme di porzioni genomiche denominate contig. Per il genoma di Nannochloropsis ne sono stati prodotti 7 035 di dimensioni superiori alle 500 paia di basi. Sfruttando le informazioni delle librerie “mate-paired” del SOLiD, che prevedono il sequenziamento combinato di paia di sequenze ad una distanza nota nel genoma ho sviluppato un programma (ScaMP) che permette di produrre liste ordinate di contig (dette scaffold). Il programma ha prodotto 95 scaffold di dimensione media pari a 285 594 paia di basi, incorporandovici 26,8 milioni di nucleotide in totale. L’elevato numero di sequenze prodotte con il SOLiD permette anche, una volta ottenuti gli scaffold, di completare le sequenze mancanti fra un contig ed il successivo (dette gap). A tal fine ho sviluppato un ulteriore programma che estrae dall’insieme di sequenze SOLiD il sottoinsieme di quelle adiacenti ad un contig, ed effettua un assemblaggio locale che viene infine utilizzato per colmare gap. Su uno scaffold di 140 contig ha eliminato 106 regioni gap, portando il numero di contig a 36 ed aumentando la dimensione media da 8 300 a 77 400 paia di basi. I risultati ottenuti confermano che l’approccio combinato di SOLiD e 454 permette di ottenere un buon assemblaggio di un genoma eucariotico limitando al contempo i costi di sequenziamento. I risultati ottenuti sono stati validati tramite il sequenziamento di estremità di inserti BAC successivamente allineati contro il dataset di scaffold. I programmi sviluppati hanno dimostrato di essere un valido sistema di assemblaggio affidabile e di colmare una lacuna nel panorama dei programmi bioinformatici per il sequenziamento de novo con tecniche di nuova generazione.