Efficient long-read overlap detection and alignment for De Novo genome assembly

Outstanding advancements in methods for genetic data sequencing and analysis have placed genomics at the forefront of the biology revolution. De novo genome assembly is the process of reconstructing entire genomes from DNA fragments (reads), of which only a fraction contains relevant information for the reconstruction. The main step of de novo genome assembly consists in overlapping reads, a process which becomes more effective if long-read data is used as input. However, long DNA reads are very prone to error, making the detection of the regions of overlap more difficult because it becomes harder to distinguish between informative and non-informative data. Therefore, the common approach for overlap detection is to prioritize the exclusion of non-informative data at the expense of some informative data. Our approach, named Berkeley Long-Read to Long-Read Aligner and Overlapper (BELLA), reverses the problem: by first identifying the features of informative data, it enforces its retention and the exclusion of all other data (which is assumed to be non-informative). This new mathematical method is optimized by adopting, for the first time in this field, the computationally efficient sparse-matrix multiplication paradigm. Because it tries to retain as much informative data as possible, our model gives priority to the maximization of recall. BELLA achieved high values of recall, mainly 94.70% for C. elegans 40X, 94.38% for E. coli, and 98.62% for C. elegans 20X. Its recall was higher than existing methods (while maintaining a comparable runtime), with an average improvement of 1.61% over the second-best tool available. In conclusion, BELLA has proven to be the most efficient tool available to date to retain as much informative data as possible from long-read sequencing data for de novo genome assembly.

Ad oggi, la genomica é considerata la punta di diamante di diversi campi di studio, dalla medicina alla agricoltura, poiché permette di studiare e comprendere i meccanismi molecolari alla base di diversi processi. Per meglio poter studiare tali meccanismi è, tuttavia, necessario conoscere nel dettaglio la composizione e la struttura del genoma. Il metodo che permette il passaggio da un campione biologico alla sua sequenza di DNA è chiamato “sequenziamento”. Le tecnologie odierne non sono in grado di fornire l’intera sequenza di DNA: ciò che restituiscono sono un insieme di sotto-sequenze che devono essere assemblate tra loro per ottenere il DNA completo, in modo da renderne possibile uno studio maggiormente dettagliato. Il metodo di assemblaggio de novo ricostruisce per l’intero il genoma cercando regioni di sovrapposizione tra una frazione di sotto-sequenze che sono ritenute utili ai fini dell’assemblaggio. Grazie allo sviluppo di tecnologie di sequenziamento di terza generazione, siamo oggi in grado di generare dati a lunghezza significativamente maggiore rispetto alle tecnologie precedenti, aumentando l’efficacia dell’assemblaggio. Tuttavia, all’incremento di lunghezza fa seguito un aumento di errori, risultando in un aumento della difficoltà di identificare dati informativi. Le soluzioni proposte fino ad ora approcciano il problema dando priorità all’esclusione dei dati non-informativi, risultando in una possibile perdita di sotto-sequenza utile per l’assemblaggio. Il lavoro presentato in questa tesi, BELLA, consiste in un nuovo software che mira ad identificare le sovrapposizioni tra sotto-sequenze. In BELLA, l’approccio è diametricalmente opposto a quello fino ad ora applicato: il nuovo software massimizza il trattenimento di dati informativi, individuando le caratteristiche che li rendono tali, riuscendo comunque ad escludere quelli non informativi. La formulazione matematica è resa efficiente dall’adozione, per la prima volta in questo campo, del paradigma di calcolo che sfrutta la moltiplicazione tra matrici sparse. Questa implementazione permette a BELLA di ottenere alti valori di sensitività, migliori rispetto ai metodi esistenti e con una percentuale di miglioramento medio dell’1.61% sul secondo miglior algoritmo. I risultati provano che BELLA è al momento lo strumento più efficace per trattenere dati utili all’assemblaggio de novo.