A methodology to enhance quality performance of third generation DNA sequences error correction

In the last few years, Third Generation Sequencing (TGS) technologies have allowed to drastically increase the length of the sequenced strand of DNA. By analyzing these data it is possible to determine the genetic variations existing in the DNA of an individual that can potentially cause the genesis of diseases. This is the basis of the personalized medicine. Unfortunately, TGS is also characterized by a higher error rate, compared to older sequencing techniques. As the errors in the strands could introduce inaccuracy in personalized drugs scientists started to develop several techniques to correct the sequenced strands, because the absence of the error correction would produce inaccuracy in personalized drugs. The issues associated with TGS sequence correction are various: the dependency on other sequencing techniques called Second Generation Sequences that increase the costs of the correction and the amount of time necessary to perform the tasks, typically caused by onerous alignments and the efficacy in producing consistently corrected sequences. Among various tools and software that implement this procedure, the fastest is MECAT. This tool first implements a restrictive candidate selection and then correct sequences basing on Myers diff algorithm, a heuristic alignment. Although MECAT is associated with high speed, its output dimension and quality is limited. The introduction of an optimal alignment algorithm in the tool, such as Needleman-Wunsch, could contribute to enhance the correction quality. We introduced the Seqan's version of Needleman-Wunsch in MECAT, after a reverse-engineering analysis of the tool's code. Needleman-Wunsch is an onerous time-consuming algorithm. Although the original candidate selection performed by MECAT helps to avoid aligning useless sequences (thus, saving time). We decided to solve the runtime problem using a Graphics Processing Unit (GPU) implementation of Hirschberg alignment, a Needleman-Wunsch variant. Thanks to our work the number and length of corrected sequences increased, translating in an improvement of various assembly metrics particularly for low coverage datasets. The integration of a GPU implementation didn't enhance the time-consuming profile of MECAT, but lay the foundations for an efficient time consuming and accurate non-hybrid error correction tool.

Negli ultimi anni le tecnologie di Sequenziamento di Terza Generazione (TGS) hanno permesso di aumentare drasticamente la lunghezza delle sequenze di DNA derivanti dalle operazioni di sequenziamento. Analizzando questi dati è possibile determinare variazione genetiche esistenti nel DNA di un individuo che possono potenzialmente causare l'insorgere di malattie, ereditate o acquisite. Questa è la base della medicina personalizzata. Sfortunatamente, TGS è anche caratterizzata da un alto numero di errori, se confrontata con altre tecniche di sequenziamento. Questo problema ha portato la comunità scientifica a sviluppare nuove tecniche di correzione delle sequenze digitalizzate, poiché la presenza di errori porterebbe inaccuratezza nel farmaco personalizzato. I problemi associati alla correzione di sequenze di terza generazione sono vari: la dipendenza da altre tecniche di sequenziamento che aumenta i costi di correzione, l'incredibile quantità di tempo necessaria per portare a termine questo processo, generalmente dovuta ad onerosi allineamenti e l'efficienza nella produzione di sequenze corrette consistenti. Tra i vari software presenti nello stato dell'arte, il più veloce è MECAT. MECAT inizialmente implementa una selezione restrittiva delle sequenze candidate, andando a filtrare sequenze potenzialmente compromesse che infine correggerà basandosi sull'allineamento euristico diff. Benché MECAT sia associato ad un alta velocità, il suo output è ridotto sia in termini di numero di sequenze, sia della lunghezza delle stesse. Questo può portare ad assemblaggi non accurati e future conseguenze connesse. Se da un lato l'introduzione dell'algoritmo di allineamento Needleman-Wunsch, capace di calcolare l'allineamento ottimale tra due sequenze, può aumentare la qualità di correzione, dall'altro lato aumenterebbe anche il tempo di correzione. L'introduzione dell'algoritmo di Needleman-Wunsch è stato possibile grazie a Seqan, una libreria C++ con scopi bioinformatici, solo dopo un attenta analisi di ingegneria inversa. Benché l'originale selezione dei candidati eseguita da MECAT evita allineamenti di sequenze superflue (salvando così del tempo nell'esecuzione generale), abbiamo deciso di risolvere il problema utilizzando un'implementazione GPU dell'allineamento di Hirschberg, una variante di Needleman-Wunsch. Grazie al nostro lavoro il numero e la lunghezza delle sequenze corrette è aumentato e ciò si è tradotto in un miglioramento di svariate metriche di assemblaggio, in modo particolare per datasets con bassa coverage. L'integrazione dell'implementazione GPU non ha portato miglioramenti per quanto riguarda il consumo di tempo di MECAT, ma getta le basi per la creazione di un software non ibrido di correzione degli errori, efficiente sia dal punto di vista della qualità che di tempo.