Negli articoli precedenti ho avuto modo di parlare di alcune tecniche di sequenziamento e di come le reads ottenute da tale processo possono essere “pulite”, ma quale sarà il loro destino?

Le reads pulite e filtrate possono essere usate per la ricostruzione dell’intera sequenza del DNA o cDNA che abbiamo deciso di sequenziare mediante un processo che prende il nome di assemblaggio. Personalmente quando penso all’assemblaggio mi diverto a fare un paragone, forse un pò forzato ma devo dire che funziona. Immaginate che le lettere “F”, “W”, “L” e “O” siano delle reads (frammenti di una sequenza). Bene, assemblando le lettere tra loro si può ottenere una parola “WOLF”, che ha molto più senso delle singole lettere. Il lettore più attento avrà notato che con le lettere sopra citate può essere costruita anche la parola “FLOW”, e si starà chiedendo come faccio a sapere quale dei due “assemblaggi di lettere” è corretto. Queste problematiche si presentano anche per le reads e in tal caso ci viene in aiuto l’analisi della qualità dell’assemblaggio, ma tranquilli di questo ne parleremo meglio in un altro articolo. Ciò che vorrei farvi capire con questo esempio è che assemblare vuol dire disporre le reads ottenute dal sequenziamento al fine di ottenere l’intera sequenza di DNA o cDNA sequenziata.

In particolare l’assemblaggio delle reads è consentito da regioni di sovrapposizione che esistono tra queste. Il primo prodotto dell’assemblaggio sono i contigs i quali vengono collegati e orientati al fine di formate delle sequenze contigue chiamate scaffold. Queste sequenze però, sono dotati di “spazi vuoti” che verranno colmati usando delle reads ottenute in modo indipendente che vadano in qualche modo a sovrapporsi proprio presso questi spazi ciò consente di ottenere un’intera sequenza continua che nel suo insieme costituisce l’intera successione di basi azotate che compongono il DNA o cDNA sequenziato in origine e definita sequenza consenso. Nonostante ciò è possibile che alcuni spazi rimangano “scoperti” nel prodotto finale dell’assemblaggio. A volte gli scaffold possono essere uniti tra loro in base a informazioni genetiche definite da mappe pre-esistenti oppure in base ad informazioni di conformazione ottenuti mediante tecnica Hi-C. L’insieme di scaffold prende il nome di superscaffold.

Se vogliamo dunque essere schematici possiamo dire che, in ordine temporale, i prodotti dell’assemblaggio di una molecola di DNA o cDNA sono:

a) Contigs, insieme di reads sovrapposte in parte. Solitamente questi sono gli output usati da altri algoritmi che svolgono degli studi successivi agli assemblaggi.

b) Scaffold, insieme di contigs ordinati ed orientati in funzione di informazioni di posizione. Inoltre gli scaffold ottenuti presentano degli spazi vuoti che possono essere colmati attraverso il mappaggio nei punti “vuoti” di reads solitamente ottenute in modo indipendente. Il processo computazionale che porta all’ottenimento di scaffold privi o con pochi spazi vuoti prende il nome di scaffolding.

c) Superscaffold, insieme di scaffold uniti in base ad informazioni date da mappe o da tecnica Hi-C. Questi sono approssimabili a pseudo molecole quando sono sufficientemente lunghi da rappresentare un intero cromosoma.

Ma quali strumenti disponiamo per compiere un assemblaggio?

Esistono diversi tipi di algoritmi e relativi software disponibili (vedi immagine).

In ogni modo gli algoritmi più usati ed interessanti sono due:

  1. Overlap Layout Consensus (OLC) Algorithm
  2. De Brujin graph Algorithm

Gli algoritmi OLC sono stati soprattutto utilizzati per l’assemblaggio di reads lunghe e mentre gli algoritmi De Brujin graph sono più efficaci nell’assemblaggio di reads corte.

Fig. 3 L’illustrazione della pipeline di assemblaggio de novo (Current challenges and solutions of de novo assembly, https://link.springer.com/article/10.1007/s40484-019-0166-9).

Gli assemblatori basati su OLC

Per spiegare al meglio come gli assemblatori basati sugli algoritmi OLC funzionano ho pensato di presentare nel dettaglio i passaggi chiave con cui assemblano le reads:

  • Per prima cosa l’algoritmo compara le sequenze a coppie tra di loro mediante algoritmi di allineamento di tipo Blast o basati sui K-mers condivisi, ed in base ad un valore di omologia si decide quali sequenze siano tra loro più simili. Inoltre le reads simili vengono raggruppate in un unico cluster.
  • Successivamente queste reads simili vengono allineate globalmente mediante algoritmo di allineamento dinamico globale. Nel momento in cui il punteggio di allineamento supera un certo valore soglia, si definisce significativa la sovrapposizione delle reads simili allineate. Si crea dunque una struttura sulla base della quale viene generato un contig.
  • I diversi contigs ottenuti verranno poi a loro volta allineati o meglio estesi sempre sulla base di punti di sovrapposizione come nel caso delle reads al fine di ottenere delle sequenze molto più grandi definiti scaffold.
  • Infine gli scaffold vengono affiancati ed orientati tra loro fino ad ottenere un’unica grande sequenza consenso che costituisce il DNA o cDNA sequenziato.

Gli asseblatori basati sugli algoritmi di De Brujin

Per assemblare le reads ottenute con tecniche NGS vengono usati soprattutto algoritmi di De Brujin che permettono la costruzione di grafi. Questi sono delle strutture costituite da nodi e archi.

Fig. 5 Struttura algoritmi De Brujin Graph

Cerchiamo di vedere nel dettaglio come lavora un algoritmo basato sui grafi di De Brujin al fine di assemblare delle reads:

  • Innanzitutto le reads da assemblare vengono suddivise in k-mers, ovvero delle sottosequenze di lunghezza nota (decisa dall’operatore).
  • In seguito i k-mers vengono ordinati, secondo un criterio lessicografico, in tabelle dette hash.
  • A questo punto si costruiscono dei grafi per ogni reads proprio a partire dai k-mers ottenuti da ciascuna di queste. Nei grafi costruiti ogni nodo è costituito da un k-mer e gli archi collegano due k-mers tra loro.
Tutorials
Fig. 7 K-mers and De Brujn graph structure
  • Costruiti i grafi per ogni reads ottenuta dal sequenziamento, questi vengono confrontati tra loro con lo scopo di estendere le singole reads ed ottenere delle sequenze più lunghe, i contigs, che sono più rappresentative di una porzione del DNA o cDNA sequenziato. In particolare quando due reads hanno uno stesso nodo e, quindi k-mer, si osserva proprio in quel punto un collasso dei due grafi. Il nodo collassato avrà di conseguenza una copertura maggiore e dunque quella porzione di DNA o cDNA è più rappresentata e realistica rispetto ad altri nodi con copertura inferiore.
  • Infine non resta che “risolvere” i grafi dei contigs formatisi dal collasso di nodi condivisi. Questa risoluzione consentirà di costruire l’intera sequenza consenso del DNA o cDNA sequenziato in origine senza o con poche interruzioni. La risoluzione dei grafi può avvenire attraverso due tipi approcci di risoluzione: l’approccio Hamiltoniano e l’approccio Euleriano ed in entrambi i casi i k-mers sono collegati ai loro vicini sovrapponendo il prefisso e suffisso di sequenza (vedi immagine qui sotto). Non credo di essere capace di spiegarvi come questi due approcci funzionino nel dettaglio poichè si entra in un campo molto più matematico che biologico pertanto mi limito a dirvi che se volete saperne di più potete leggere questa review. In ogni modo occorre considerare che gli assemblatori basati su Eulerian de Bruijn graph generalmente si comportano meglio nell’assemblaggio di un genoma di grandi dimensioni rispetto all’approccio del Hamiltonian de Bruijn graph in termini di risultati dell’assemblaggio.

Gli algoritmi basati sui grafi di De Brujin sono sicuramente molto efficaci ma durante la risoluzione dei grafi estesi al fine di ricavare l’esatta sequenza consenso del DNA o cDNA sequenziato si possono incontrare delle problematiche che portano ad errori non banali.

I principali problemi che si incontrano durante la risoluzione dei grafi estesi sono:

  1. Durante la risoluzione dei grafi si possono formare delle biforcazioni, dette tips, dove si trovano nodi con bassa copertura. Questo si verifica a causa del fatto che le reads possono accumulare degli errori di sequenza presso le estremità 3′. Per risolvere tali problemi si possono filtrare ed eliminare i nodi con copertura bassa (e quindi rari) mediante specifiche opzioni che vengono assegnate al comando che lancia l’algoritmo di assemblaggio.
  2. A volte si possono creare delle “bolle” durante la risoluzione dei grafi a causa della presenza di poliorfismi come SNPs o Indels. Per risolvere tale problematica si consiglia di usare tecniche di sequenziamento che generano reads più lunghe oppure usare delle librerie particolari come la mate pair library le quali danno delle informazioni posizionali relative alle reads.
  3. Inoltre si possono creare delle giunzioni tra nodi di grafi diversi dovute alla presenza di sequenze ripetute nel DNA o cDNA sequenziato. Queste regioni sono definite “collapsing” ed in base alla loro lunghezza si distinguono in “short collapsing” e “long collapsing”. Le prime vengono individuate e ovviate direttamente dall’algoritmo di assemblaggio raggruppando le reads alla fine dell’assemblaggio mentre le seconde vengono escluse grazie all’utilizzo di mate pair library nella fase di sequenziamento.

Ok, penso sia il caso di interrompere qui l’articolo. Devo essere onesto, ho faticato molto per scriverlo, un pò perchè ho dovuto ripassare degli argomenti e un pò perchè gli algoritmi in questione sono ostici da comprendere nel dettaglio. Spero comunque di esser riuscito a spiegarvi come si ottiene l’assemblaggio di una molecola di DNA o cDNA. Ovviamente quando dico “molecola” intendo una porzione di genoma o trascrittoma, un cromosoma o una intero genoma o trascrittoma.

In ogni modo non mi sembra corretto chiudere senza lasciarvi un tutorial pratico relativo a quanto scritto sopra. Infatti di seguito ne troverete uno dove assemblo delle reads mediante un software di allineamento chiamato Velvet che si basa proprio su di un algoritmo di allineamento di De Brujin graph.

Ciao e a presto.

Fonti: