Considerazioni sulle prestazioni - Identificazione reference-free e assembly-free di polimorfis

6.4 Considerazioni sulle prestazioni

Come gi`a precedentemente sottolineato, il Prefix-Free Parsing risulta essere pi`u efficiente sia nella costruzione della BWT, quando confrontato con un algoritmo basato su SACA-K, che nel rispondere a query riguardo al SA, LCP ed LCE, quando confrontato con altre strutture dati basate sui suffix tree (maggiori dettagli in Sezione 5.4).

Le seguenti considerazioni fanno riferimento ad un’analisi computazionale data-driven, in quanto, le prestazioni del Prefix-Free Parsing si basano sul fatto che nella pratica, il dizionario 𝐷 e il parser 𝑃 sono significativamente più piccoli della stringa 𝑠 in input, potendo entrare in una memoria interna di dimensioni ragionevoli anche quando 𝑠 è molto grande. In particolare, attraverso gli esperimenti è stata testata la congettura che con una buona scelta della strategia di parsing (parametri 𝑝 e 𝑤) la lunghezza totale degli elementi in 𝐷 e il numero di frasi in 𝑃 occuperanno uno spazio inferiore rispetto alla dimensione della raccolta non compressa, e calcolare la BWT attraverso le informazioni contenute in 𝐷 e 𝑃 comporta a una riduzione complessiva nell’utilizzo della memoria.

Detto ciò è importante considerare le prestazioni del Prefix-Free Parsing per il nostro scopo, valu- tando quindi più attentamente i tempi e la memoria utilizzata dalla procedura per costruire la BWT e per garantire il supporto alle query.

La Tabella 6.1 riporta i risultati ottenuti dagli esperimenti svolti da Boucher et al. su una collezione di genomi di Salmonella. I dati trascritti provengono da due sperimentazioni distinte [46, 47] entrambe effettuate sullo stesso dataset e attraverso lo stesso server con Intel®_Xeon®_{CPU E5-2640}

v4 con 2.40 GHz e 756 GB di RAM. Il numero di genomi all’interno della collezione è stato fatto variare tra 50 e 5 000 e l’algoritmo del PFP implementato dagli autori è stato eseguito con i parametri 𝑤 = 10 e 𝑝 = 100. La somma dimensione del dizionario 𝐷 e del parser 𝑃 ottenuti è nettamente inferiore alla dimensione del file non compresso, occupando dal 59%, per il dataset con 50 genomi, e fino all’83%, per le collezioni con 1 000 e 5 000 genomi, di spazio in meno.

Le righe centrali della Tabella 6.1 riportano il tempo impiegato dal PFP (in secondi) sia per eseguire la fase di pre-processing dell’input che per l’elaborazione delle informazioni contenute in 𝐷 e in 𝑃 al fine di costruire la BWT, oltre al picco di memoria richiesto (in megabyte, MB). Le ultime tre righe, invece, riportano il tempo (in secondi) necessario per la fase di parsing e per la costruzione

Numero di genomi di Salmonella 50 100 500 1 000 5 000

Dimensione file non compresso [MB] 249 485 2 436 4 861 24 936

Dimensione di 𝐷 [MB] 91 122 377 643 3 196

Dimensione di 𝑃 [MB] 10 19 96 192 985

% occupata 41% 29% 19% 17% 17%

Tempo [secondi] 65 102 402 776 4 808

Costruzione

della BWT _{Picco di memoria [MB]} ₇₈₂ _{1 059} _{3 304} _{5 659} _{51 848}

Tempo [secondi] 95 140 500 1 000 7 500

Picco di memoria [MB] 3 3380 4 768 14 305 23 842 190 735 Supporto

query

Strutture ausiliari [MB] 1 907 2 384 8 583 14 305 143 051

Tabella 6.1: Dati recuperati dagli esperenti svolti da Boucher et al. per valutare le performance del Prefix-Free Parsing per costruire la BWT [46] e delle strutture dati ausiliari per supportare le query efficienti [47].

CAPITOLO 6. Variant calling con il Prefix-Free Parsing 6.4. Considerazioni sulle prestazioni delle cinque strutture dati ausiliarie che occorrono per garantire il supporto delle query efficienti, il picco di memoria (in MB) raggiunto durante l’esecuzione dell’algoritmo e, infine, la memoria (in MB) occupata per memorizzare le strutture dati ausiliari.

Analizzando il tempo e considerando che i valori riportati includono per entrambi i processi il tempo necessario al calcolo di 𝐷 e 𝑃 nella fase di parsing, si osserva comunque che il tempo richiesto dall’algoritmo di PFP che costruisce anche le strutture dati ausiliarie `e maggiore di quello necessario per il solo calcolo della BWT di un fattore che oscilla tra l’1, 2, se si osservano i risultati del dataset con 500 genomi, e l’1, 6, se invece si osservano i tempi impiegati per la collezione di dati per 5 000 genomi.

Contemporaneamente il picco di memoria `e aumentato di un fattore compreso tra 3, 7, in cui per il dataset con 5 000 genomi si passa da un picco di circa 51 GB a uno di circa 190 GB, e 4, 5 in cui per la collezione con 100 genomi si passa da un picco di oltre 1 GB a uno di oltre 4, 7 GB. Infine, lo spazio occupato dalle strutture dati che permettono il supporto delle query risulta essere oltre 3 volte e fino a 7, 7 volte maggiore della dimensione dei dataset non compressi; quindi la possibilit`a di effettuare query efficienti direttamente attraverso le informazioni contenute in 𝐷 e 𝑃 ha un costo di memoria non indifferente.

L’utilizzo del Prefix-Free Parsing alla base dell’algoritmo di variant calling attraverso il Metodo 1 non utilizza particolari risorse oltre a quelle gi`a elaborate per calcolare la BWT, tra cui il suffix array SAZdei suffissi degli elementi di 𝐷 e l’array LCP specifico lcp'Z, pertanto il tempo e il picco di me-

moria utilizzato per localizzare gli eBWT cluster ed estrarre i caratteri della eBWT dovrebbe essere simile a quello richiesto per calcolare la BWT. Il contesto destro di ciascun cluster `e velocemente ottenibile attraverso SAZ.

Per quanto riguarda invece l’applicazione del Metodo 2, `e necessario considerare che, dai risultati degli esperimenti sul tempo impiegato a rispondere a 1 000 query attraverso le specifiche strutture dati ausiliari costruite per la collezione di 5 000 genomi, in media, per rispondere ad una SA-query si impiegano circa 10 ns (nanosecondi), ad una LCP-query circa 5 ns e, infine, ad una LCE-query circa un nanosecondo. Considerato la collezione in esempio `e composta da circa 5 × 1010_{(𝑛) caratteri e}

che per utilizzare il Prefix-Free Parsing per localizzare gli eBWT cluster `e necessario eseguire 𝑛 SA- query e 𝑛 LCP-query, in questo caso sarebbero stati impiegati (10 + 5) ⋅ 5 × 1010_{= 75 × 10}10_{ns (circa}

13 minuti) per costruire l’array LCP lcpM2. Oltre alle LCP-query sono poi necessarie le BWT-query

per estrarre i caratteri dell’eBWT cluster e le SA-query per ottenere il contesto destro. Lo spazio necessario a memorizzare le strutture dati per le query sono comunque un aspetto fondamentale dell’implementazione del Metodo 2.

Infine, l’analisi effettuata sui cluster per identificare gli SNP, dopo aver ottenuto il contesto destro attraverso i due Metodi, richiede un’ulteriore scansione del file della collezione dei read in input per recuperare il contesto sinistro degli SNP.

Come suggerito dagli autori stessi del PFP esiste la possibilità di ridurre i tempi di esecuzione parallelizzando il lavoro con una tecnica multi-thread, specialmente per la fase in cui vengono cal- colati il dizionario 𝐷 e il parser 𝑃, suddividendo l’input in blocchi di stesse dimensioni e assegnando ciascun blocco ad un thread. L’aumento del numero di thread può comunque non garantire un mi- glioramento sostanziale a causa dell’aggiornamento costante del dizionario da parte di tutti i thread durante la fase di parsing. È inoltre possibile parallelizzare ulteriormente entrambi i metodi, una

CAPITOLO 6. Variant calling con il Prefix-Free Parsing 6.4. Considerazioni sulle prestazioni volta creati i bit-vector di supporto per localizzare gli eBWT cluster, utilizzando un thread principale che scansiona l’array LCP e ogni volta in cui individua un cluster assegna ad un altro thread il compito di eseguire i passi dell’algoritmo di variant calling recuperando il contesto, calcolando le stringhe consensus e producendo le informazioni che identificano uno SNP.

Le considerazioni trattate teoricamente in questo studio potrebbero essere verificate attraverso l’implementazione dei due metodi presentati e una loro applicazione su collezioni di read provenienti da database genomici, ma ci`o esula dallo scopo di questa tesi.

CAPITOLO 6. Variant calling con il Prefix-Free Parsing 6.4. Considerazioni sulle prestazioni

CAPITOLO

7

Conclusioni

Sebbene lo studio del DNA sia iniziato nel lontano 1880 (Capitolo 1), molte delle sue proprietà sono state scoperte più recentemente grazie all’avvento della tecnologia di sequenziamento e lo sviluppo di nuove tecniche di analisi bioinformatiche. Il primo passo fondamentale sullo studio del DNA fu quello del sequenziamento (Sezione 1.2), una potente tecnica per analizzare il DNA e determinare la sequenza di basi da cui è costituito, inizialmente messa a punto intorno alla metà degli anni sessanta da Maxam e Gilbert e successivamente migliorata da Sanger. Il metodo Sanger è stato per anni il metodo principale di sequenziamento del DNA effettuato soprattutto manualmente, con una procedura particolarmente laboriosa e costosa. Le tecnologie di sequenziamento di ultima generazione, chiamate Next-Generation Sequencig (NGS, tra cui Illumina), sono nuove metodiche che, grazie alla tecnologia più recente, hanno reso questa procedura centinaia di volte più veloce e meno costosa del tradizionale metodo Sanger, sequenziando, nella maggior parte dei casi, milioni di frammenti di DNA simultaneamente.

Nel 1990, con lo scopo di sequenziare l’intero genoma umano, caratterizzato da 3, 2 miliardi di paia di basi, è nato lo Human Genome Project (Sezione 1.3) che nel 2003 ha dichiarato completa la sequenza del genoma umano. Ad oggi, grazie alle potenzialità delle NGS e a progetti come 1 000 Genomes Project, è possibile sequenziare e confrontare i genomi di diverse migliaia di individui di differenti popolazioni allo scopo di scoprire nel maggior dettaglio possibile le somiglianze e le differenze fra i membri della specie umana. È stato osservato che, se da un lato l’incremento dei genomi sequenziati ha portato ad un notevole aumento della conoscenza sulle proprietà DNA, dall’altro ha prodotto una crescita esponenziale dei dati di sequenziamento contenuti nei database genomici (Figura 1.4 a pagina 11).

Nonostante il DNA sia una molecola molto stabile, che si replica con sorprendente accuratezza, `e stato osservato che possono comunque verificarsi mutazioni nella sua struttura ed errori di repli- cazione (Capitolo 2). Numerosi studi di genetica attuali si concentrano difatti sull’analisi di come vengono ereditate le varianti prodotte per mutazione. In particolare i siti in cui si osservano diffe-

CAPITOLO 7. Conclusioni

renze in una singola base del genoma fra individui della stessa specie sono chiamati polimorfismi di singolo nucleotide (Single Nucletide Polimorphism - SNP, Sezione 2.1.2).

Sono state trattate differenti metodologie (Sezione 2.2) che permettono l’assemblaggio del genoma, attraverso l’approccio dei grafi di sovrapposizione e quello dei grafi di de Bruijn; e l’allineamento di sequenze su un genoma (precedentemente assemblato), tramite l’approccio basato su tabelle hash e quello basto sulla Burrows-Wheeler Transform (BWT). `E stato quindi descritto il processo di analisi, detto variant calling, che (solitamente) segue la fase di allineamento, e il cui scopo `e l’identificazione delle varianti associate a un individuo, o a una popolazione.

L’allineamento dei read su un genoma di riferimento, oltre ad essere soggetta ad errori e perdite di dati, presenta delle limitazioni dovute principalmente alla difficoltà di mappare regioni altamente ripetitive, soprattutto se il genoma di riferimento è di bassa qualità oppure nel caso estremo in cui tale genoma non è neanche disponibile. Per tale ragione sta crescendo l’interesse verso metodi di variant calling che elaborano direttamente i dai grezzi, senza la necessità di un genoma di riferimen- to (reference-free) e senza effettuare l’operazione di assemblaggio delle sequenze (assembly-free). La maggior parte degli strumenti che condividono il concetto di operare direttamente sui dati grezzi utilizzano un grafo di de Bruijn dei 𝑘-meri dei read. L’inclusione di diverse caratteristiche biologi- che all’interno della struttura del grafo e l’analisi delle cosiddette “bolle” nel grafo stesso (Figura 2.6 a pagina 22), permettono di identificare varianti come SNP, INDEL oppure errori di sequenziamen- to. Di contro però, le rappresentazioni con i grafi di de Bruijn hanno lo svantaggio della decisione del parametro 𝑘, e, di conseguenza, la limitazione a considerare solo 𝑘-meri piuttosto che l’effet- tiva collezione dei read. Informazioni sulla copertura di ogni 𝑘-mero o sull’appartenenza di due 𝑘-meri allo stesso read (e quindi adiacenti nel genoma) vengono quindi perse. L’utilizzo invece di un metodo di indicizzazione basato sulla BWT per le collezioni di read ha il vantaggio di essere allo stesso tempo facilmente comprimibile ed evita la perdita di dati.

Dal momento in cui il genoma umano pu`o essere rappresentato come una stringa definita sul- l’alfabeto Σ = {A, C, G, T} e di lunghezza superiore a 3 × 109caratteri, sono state introdotte (nel Capitolo 3) le strutture dati utilizzate nei tool bioinformatici che rappresentano stringhe, come ad esempio i Suffix Tree, i Suffix Array e la Burrows-Wheeler Transform.

Nel 2018 è stato introdotto da Prezza et al. il positional clustering (Capitolo 4), un framework reference-free e assembly-free che crea un indice delle raccolte di read basato sulla extended Burrows- Wheeler Transform (eBWT). L’osservazione su cui si basa è che se tutti i simboli in un cluster associato ad uno specifico contesto sono uguali ad uno stesso simbolo, ogni occorrenza del contesto nella collezione dei read è preceduta da tale simbolo (Figura 4.1(a) a pagina 36). Nel caso in cui un cluster contiene invece almeno due simboli distinti e il contesto è abbastanza lungo, al- lora quei simboli possono riflettere una variante (ad esempio uno SNP) nella collezione di read (Figura 4.1(b) a pagina 36). Introducendo i loro studi, attraverso le proprietà della eBWT e caratte- rizzazioni statistiche, è stato mostrano che i simboli antecedenti ai suffissi dei read che iniziano con uno stesso contesto, risultano contigui in una sottostringa della eBWT, denominata eBWT cluster (Sezione 4.1.1); e che i cluster possono essere localizzati per mezzo dell’array LCP (Sezione 4.1.2). Essendo il positional clustering basato sulla eBWT, è stato approfondito lo studio sul Prefix-Free Parsing (PFP), uno strumento di pre-processing introdotto da Boucher et al., che si distingue per semplicità e flessibilità e garantisce un processo di calcolo della BWT con una quantità di risorse ri-

CAPITOLO 7. Conclusioni

dotte (Capitolo 5) rispetto al calcolo della BWT attraverso classici algoritmi. Sono state riportate sia le basi teoriche (Sezione 5.1) che il procedimento di implementazione (Sezione 5.2) del Prefix-Free Parsing. Il PFP, data una stringa 𝑠[1, 𝑛], produce un dizionario 𝐷 ed un parser 𝑃 di frase sovrappo- ste tali per cui BWT(𝑠) può essere calcolata da 𝐷 e 𝑃 utilizzando uno workspace proporzionale alla somma della lunghezza di 𝑃 e degli elementi di 𝐷, ed un tempo 𝑂(𝑛) quando possiamo lavorare nella memoria interna. Inoltre, è stata approfondita la possibilità di costruire strutture dati ausiliarie per permettere query efficienti sul PFP (Sezione 5.3).

Analizzando i promettenti esiti degli esperimenti svolti da Boucher et al. per valutare le performance del Prefix-Free Parsing sia per calcolare la BWT che per il supporto di query efficienti (Sezione 5.4), la domanda a cui questo studio ha voluto rispondere riguarda la possibilit`a di eseguire un processo di variant calling su una collezione di read attraverso le informazioni contenute all’interno del Prefix-Free Parsing (Capitolo 6).

Per dimostrare la possibilit`a di utilizzare le informazioni rappresentate con il dizionario 𝐷 e il parser 𝑃, prima per localizzare gli eBWT cluster (Sezione 6.2), e poi per stabilire la presenza di possibili SNP nell’insieme di read (Sezione 6.3), sono stati presentati due metodi (Figura 6.1 a pagina 61). In particolare, il primo metodo utilizza la base teorica del Prefix-Free Parsing elaborando i suffissi degli elementi dell’insieme 𝐷 con lo scopo di recuperare direttamente le informazioni dei minimi locali nell’array LCP per localizzare gli eBWT cluster, e poi i caratteri della (e)BWT ed il contesto del cluster per effettuare l’analisi. Mentre, il secondo metodo si basa sul Prefix-Free Parsing come struttura dati sulla quale effettuare BWT-, SA-, LCP- e LCE-query; localizzando gli eBWT cluster attraverso i minimi locali dell’array LCP costruito con LCP-query; e stabilendo successivamente, per ogni cluster, il contesto tramite delle LCE-query.

Una volta descritto nel dettaglio come localizzare gli eBWT cluster attraverso ognuno dei due metodi presentati, sottolineando anche le loro differenze, ed a seguito della trattazione dell’identificazione dei polimorfismi a singolo nucleotide con le informazioni elaborate, sono state fatte delle considerazioni sulle prestazioni (Sezione 6.4). Si è cos`ı dimostrato che è possibile eseguire un processo di variant calling, per individuare gli SNP, basato sulla teoria del positional clustering partendo dalle sole informazioni contenute nel dizionario 𝐷 e nel parser 𝑃 generati dal Prefix-Free Parsing. Una conseguenza è che può essere utilizzato uno workspace contenuto in quanto nella pratica il dizionario 𝐷 e il parser 𝑃 sono significativamente più piccoli della stringa 𝑠 in input, potendo rientrare in una memoria interna anche quando 𝑠 è molto grande.

Si intende ricordare che le considerazioni trattate teoricamente in questo studio potrebbero essere verificate attraverso l’implementazione dei due metodi presentati e una loro applicazione su collezioni di read provenienti da database genomici, ma ci`o esula dallo scopo di questa tesi.

CAPITOLO 7. Conclusioni

Acronimi

1KGP 1 000 Genomes Project

bp base pair

BWT Burrows-Wheeler Transform CNV Copy Number Variation DDBJ DNA Database of Japan ddNTP didesossiribonucleosidi DNA DeoxyriboNucleic Acid dNTP desossiribonucleosidi

EBI European Bioinformatics Institute eBWT extended Burrows-Wheeler Transform eGSA enhanced Generalized Suffix Array EMBL European Molecular Biology Laboratory ENA European Nucleotide Archive

ENCODE Encyclopedia of DNA Elements GATK Genome Analysis Toolkit GSA Generalized Suffix Array GST Generalized Suffix Tree

HGP Human Genome Project

IHGSC International human genome sequencing consortium INSDC International Nucleotide Sequence Database Collaboration LCA Lowest Common Ancestor

LCE Longest Common Extension LCP Longest Common Prefix

NCBI National Center for Biotechnology Information NGS Next-Generation Sequencig

NIG National Institute of Genetics NIH National Institutes of Health

PCR Polymerase Chain Reaction PFGE Pulsed-Field Gel Electrophoresis RMQ Range-Minimum Query

RNA RiboNucleic Acid SA Suffix Array

SAM Sequence Alignment Map SMRT single-molecule real-time SNP Single Nucletide Polimorphism SNV Single Nucletide Variants SRA Sequence Read Archive ST Suffix Tree

VCF Variant Call Format

Bibliografia

[1] Gregor Mendel.≪Versuche ¨uber Plflanzen-Hybriden≫. In: Verhandlungen des naturforschen-

den Vereines in Br¨unn. A cura di Abhandlungen. 1aed. Vol. 4. 1865, pp. 1–47.

[2] James Dewey Watson e Francis Harry Compton Crick.≪Molecular Structure of Nucleic

Acids: A Structure for Deoxyribose Nucleic Acid≫. In: Nature 171.4356 (1953), pp. 737–738.

[3] Rosalind Elsie Franklin e Raymond Gosling.≪The structure of sodium thymonucleate fibres.

I. The influence of water content≫. In: Acta Crystallographica 6.8-9 (1953), pp. 673–677.

[4] Paolo Vezzoni. Genoma, DNA e geni. Humanitas. 2017.

[5] International Human Genome Sequencing Consortium.≪Finishing the euchromatic sequen-

ce of the human genome≫. In: Nature 431.7011 (2004), pp. 931–945.

[6] Ran Elkon e Reuven Agami.≪Characterization of noncoding regulatory DNA in the human

genome≫. In: Nature Biotechnology 35.8 (2017), pp. 732–746.

[7] Ian Dunham e Kundaje.≪An integrated encyclopedia of DNA elements in the human geno-

me≫. In: Nature 489.7414 (2012), pp. 57–74.

[8] Allan Maxam e Walter Gilbert.≪A new method for sequencing DNA.≫eng. In: Proc Natl Acad

Sci U S A 74.2 (1977), pp. 560–564.

[9] Frederick Sanger e Alan Coulson.≪A rapid method for determining sequences in DNA by

primed synthesis with DNA polymerase.≫eng. In: J Mol Biol 94.3 (1975), pp. 441–448.

[10] Illumina. An introduction to Next-Generation Sequencing Technology. 2017.

[11] Hengyun Lu, Francesca Giordano e Zemin Ning.≪Oxford Nanopore MinION Sequencing and

Genome Assembly.≫eng. In: Genomics Proteomics Bioinformatics 14.5 (2016), pp. 265–279.

[12] Sotaro Uemura, Colin Echeverr´ıa Aitken, Jonas Korlach, Benjamin Flusberg, Stephen Turner e Joseph Puglisi.≪Real-time tRNA transit on single translating ribosomes at codon resolu-

tion≫. In: Nature 464.7291 (2010), pp. 1012–1017.

[13] Anthony Rhoads e Kin Fai Au.≪PacBio Sequencing and Its Applications.≫ In: Genomics

[14] Jolinda Pollock, Laura Glendinning, Trong Wisedchanwet e Mick Watson.≪The Madness of

Microbiome: Attempting To Find Consensus “Best Practice” for 16S Microbiome Studies≫.

In: Applied and Environmental Microbiology 84.7 (2018). A cura di Shuang-Jiang Liu. [15] Robert Fleischmann, Mark Adams, Owen White, Rebecca Clayton, Ewen Kirkness, A R Ker-

lavage, Carol Bult, Jean-Francois Tomb, Brian Dougherty e Joseph Merrick.≪Whole-genome

random sequencing and assembly of Haemophilus influenzae Rd.≫eng. In: Science 269.5223

(1995), pp. 496–512.

[16] Eric Lander.≪Initial impact of the sequencing of the human genome≫. In: Nature 470.7333

(2011), pp. 187–197.

[17] The 1000 Genomes Project Consortium.≪A map of human genome variation from population-

scale sequencing≫. In: Nature 467.7319 (2010), pp. 1061–1073.

[18] The 1000 Genomes Project Consortium.≪An integrated map of genetic variation from 1,092

human genomes≫. In: Nature 491.7422 (2012), pp. 56–65.

[19] The 1000 Genomes Project Consortium.≪A global reference for human genetic variation≫.

In: Nature 526.7571 (2015), pp. 68–74.

[20] International HapMap Constortium.≪A second generation human haplotype map of over

3.1 million SNPs.≫eng. In: Nature 449.7164 (2007), pp. 851–861.

[21] Mathieu Emily, Thomas Mailund, Jotun Hein, Leif Schauser e Mikkel Heide Schierup.≪Using

biological networks to search for interacting loci in genome-wide association studies.≫eng.

In: Eur J Hum Genet 17.10 (2009), pp. 1231–1240.

[22] Sergey Koren, Gregory Harhay, Timothy Smith, James Bono, Dayna Harhay, Scott Mcvey, Diana Radune, Nicholas Bergman e Adam Phillippy. ≪Reducing assembly complexity of

microbial genomes with single-molecule sequencing≫. In: Genome Biology 14.9 (2013), R101.

[23] Heng Li, Jue Ruan e Richard Durbin.≪Mapping short DNA sequencing reads and calling

variants using mapping quality scores.≫In: Genome Res 18.11 (2008), pp. 1851–1858.

[24] Pierre Peterlongo, Nicolas Schnel, Nadia Pisanti, Marie-France Sagot e Vincent Lacroix.≪Iden-

tifying SNPs without a Reference Genome by Comparing Raw Reads≫. In: String Processing

Nel documento Identificazione reference-free e assembly-free di polimorfismi a singolo nucleotide con Prefix-Free Parsing (pagine 79-93)