thesis.tex

\documentclass[a4paper,12pt, oneside]{book}
%\documentclass[a4paper,12pt, oneside, draft]{book}
% \usepackage{fullpage}
\usepackage[italian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphics}
\usepackage{amsfonts}
\usepackage{listings}
\usepackage{amsmath}
\usepackage{amstext}
\usepackage{colortbl}
\usepackage{engrec}
\usepackage{appendix}
\usepackage{multicol}
\usepackage{rotating}
\usepackage{subcaption}
\usepackage{verbatim}
\usepackage{stackengine}
\usepackage[safe,extra]{tipa}
% \usepackage{showkeys}
\usepackage{multirow}
\usepackage{hyperref}
\usepackage{microtype}
% \usepackage{fontspec}
\usepackage{enumerate}
\usepackage{braket}
\usepackage{relsize}
\usepackage{marginnote}
\usepackage{pgfplots}
\usepackage{cancel}
\usepackage{polynom}
\usepackage{booktabs}
\usepackage{enumitem}
\usepackage{framed}
\usepackage{pdfpages}
\usepackage{pgfplots}
\usepackage[chapter]{algorithm}
%\usepackage[ruled,vlined,linesnumbered]{algorithm2e}
%\usepackage[ruled,vlined]{algorithm2e}
\makeatletter
\renewcommand{\ALG@name}{Algoritmo}
\renewcommand{\listalgorithmname}{Lista degli algoritmi}
\makeatother
%\usepackage[backend=biber, backref=true, sorting=none]{biblatex}
\usepackage{fvextra}
\usepackage{csquotes}
% \usepackage{natbib}
% \usepackage{algpseudocode}
\usepackage[cache=false]{minted}
\usepackage{mathtools}
\usepackage[noend]{algpseudocode}
\usepackage{svg}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{setspace}
\usepackage{geometry}
\usepackage{blindtext}
\usepackage{titleps}
% \makeatletter
% \long\def\@makecaption#1#2{%
%   \vskip\abovecaptionskip
%     \bfseries #1: #2\par
%   \vskip\belowcaptionskip}%
% \makeatother
% \lstset{ % General setup for the package
%     language=Perl,
%     basicstyle=\small\sffamily,
%     frame=lines,
%     tabsize=4,
%     columns=fixed,
%     showstringspaces=false,
%     showtabs=false,
%     keepspaces,
%     commentstyle=\color{red},
%     keywordstyle=\color{blue}
% }
\usepackage{tikz}\usetikzlibrary{er}\tikzset{multi  attribute /.style={attribute
    ,double  distance =1.5pt}}\tikzset{derived  attribute /.style={attribute
    ,dashed}}\tikzset{total /.style={double  distance =1.5pt}}\tikzset{every
  entity /.style={draw=orange , fill=orange!20}}\tikzset{every  attribute
  /.style={draw=MediumPurple1, fill=MediumPurple1!20}}\tikzset{every
  relationship /.style={draw=Chartreuse2,
    fill=Chartreuse2!20}}\newcommand{\key}[1]{\underline{#1}}
\usetikzlibrary{arrows.meta}
\usetikzlibrary{decorations.markings}
\usetikzlibrary{arrows,shapes,backgrounds,petri} 
\usetikzlibrary{automata,positioning}
\usetikzlibrary{matrix}

%\usepackage[textsize=scriptsize, textwidth = 25mm]{todonotes}
\usepackage[disable, textsize=scriptsize, textwidth = 25mm]{todonotes}
\newcommand{\dc}[1]{\todo[backgroundcolor=yellow]{\textbf{DC} #1}}
\newcommand{\gdv}[1]{\todo[backgroundcolor=blue]{\textbf{GDV} #1}}
\newcommand{\pb}[1]{\todo[backgroundcolor=red]{\textbf{PB} #1}}
\newcommand{\yp}[1]{\todo[backgroundcolor=green]{\textbf{YP} #1}}
\newcommand{\rr}[1]{\todo[backgroundcolor=pink]{\textbf{RR} #1}}

\def\SLP{\mbox{\rm {\sf SLP}}}
\def\rank{\mbox{\rm {\sf rank}}}
\def\lcs{\mbox{\rm {\sf lcs}}}
\def\lcp{\mbox{\rm {\sf lcp}}}
\def\lce{\mbox{\rm {\sf lce}}}
\def\LCE{\mbox{\rm {\sf LCE}}}
\def\ROT{\mbox{\rm {\sf ROT}}}
\def\select{\mbox{\rm {\sf select}}}
\def\col{\mbox{\rm {\sf col}}}
\def\NULL{\mbox{\rm {\sf null}}}
\def\len{\mbox{\rm {\sf len}}}
\def\pos{\mbox{\rm {\sf pos}}}
\def\row{\mbox{\rm {\sf row}}}
\def\LF{\mbox{\rm {\sf LF}}}
\def\FL{\mbox{\rm {\sf FL}}}
\def\W{\mbox{\rm {\sf w}}}
\def\A{\mbox{\rm {\sf A}}}
\def\A{\mbox{\rm {\sf A}}}
\def\SA{\mbox{\rm {\sf SA}}}
\def\LCP{\mbox{\rm {\sf LCP}}}
\def\ISA{\mbox{\rm {\sf ISA}}}
\def\PLCP{\mbox{\rm {\sf PLCP}}}
\def\RLCP{\mbox{\rm {\sf RLCP}}}
\def\RLBWT{\mbox{\rm {\sf RLBWT}}}
\def\MEM{\mbox{\rm {\sf MEM}}}
\def\KMEM{\mbox{\rm {\sf K-MEM}}}
\def\KSMEM{\mbox{\rm {\sf K-SMEM}}}
\def\MS{\mbox{\rm {\sf MS}}}
\def\LCP{\mbox{\rm {\sf LCP}}}
\def\NSV{\mbox{\rm {\sf NSV}}}
\def\PSV{\mbox{\rm {\sf PSV}}}
\def\RMQ{\mbox{\rm {\sf RMQ}}}
\def\BWT{\mbox{\rm {\sf BWT}}}
\def\BWM{\mbox{\rm {\sf BWM}}}
\def\ITR{\mbox{\rm {\sf index\_to\_run}}}
\def\GS{\mbox{\rm {\sf get\_symbol}}}
\def\PBWT{\mbox{\rm {\sf PBWT}}}
\def\MPBWT{\mbox{\rm {\sf mPBWT}}}
\def\MRLPBWT{\mbox{\rm {\sf mRLPBWT}}}
\def\DPBWT{\mbox{\rm {\sf dPBWT}}}
\def\RLPBWT{\mbox{\rm {\sf RLPBWT}}}
\def\SMEM{\mbox{\rm {\sf SMEM}}}
\def\M{\mbox{\rm {\sf M}}}
\def\C{\mbox{\rm {\sf C}}}
\def\Occ{\mbox{\rm {\sf Occ}}}
\def\L{\mbox{\rm {\sf L}}}
\def\F{\mbox{\rm {\sf F}}}
\def\DA{\mbox{\rm {\sf DA}}}
\def\DM{\mbox{\rm {\sf DM}}}
\def\PA{\mbox{\rm {\sf PA}}}
\def\LCE{\mbox{\rm {\sf LCE}}}
\def\UP{\mbox{\rm {\sf update}}}
\def\uvtrick{\mbox{\rm {\sf uvtrick}}}
\def\lceb{\mbox{\rm {\sf lce\_bounded}}}
\def\RM{\mbox{\rm {\sf reverse\_map}}}

\newcommand{\Oh}{\mathcal{O}}

% \renewcommand{\chaptermark}[1]{\markboth{#1}{}}
\usepackage{fancyhdr}
\pagestyle{fancy}

\fancyhead[LO,RE]{\slshape \leftmark}
% \fancyhead[CO,CE]{\slshape\rightmark}
\fancyhead[LE,RO]{\slshape\rightmark}
\fancyfoot[C]{\thepage}
% \fancyhf{}
% \fancyhead[LO,RE]{\slshape \leftmark}
% % \fancyhead[CO,CE]{\slshape\rightmark}
% \fancyhead[LE,RO]{\slshape\thepage}
% \renewcommand{\footrulewidth}{0pt}
% \fancyfoot[C]{\thepage}
% \title{Relazione}
% \fancypagestyle{plain}{% \fancyhf{} % clear all header and footer fields
% \fancyhead[RO,RE]{\thepage}%RO=right odd, RE=right even
% \renewcommand{\headrulewidth}{0pt}
% \renewcommand{\footrulewidth}{0.3pt}}

% \AtBeginDocument{%
%   \renewcommand{\thelisting}{\Alph{chapter}.\arabic{listing}}
%   % \renewcommand\thetable{\Alph{section}.\arabic{table}}
%   % \renewcommand\thefigure{\Alph{section}.\arabic{figure}}
% }
% %Automatically change the driver counter for reset:
% \makeatletter
% \g@addto@macro\appendix{%
%   \counterwithin*{listing}{section}%
% }
% \makeatother
% c C plus plus
\def\Cplusplus{C\raisebox{0.5ex}{\tiny\textbf{++}}}
\definecolor{nordred}{RGB}{191, 97, 106}
\definecolor{nordcyan}{RGB}{94,129,172}
\definecolor{nordgreen}{RGB}{135, 157, 116}
\definecolor{nordpurple}{RGB}{180,142,173}

\pgfplotsset{compat=1.13}
\setlist[itemize]{leftmargin=.5in}
\setlist[enumerate]{leftmargin=.5in}
\begin{document}

% \maketitle
\newgeometry{margin=1in} 
\begin{titlepage}
  

  \noindent
  \begin{minipage}[t]{0.19\textwidth}
    \vspace{-4mm}{\includegraphics[scale=1.15]{img/logo_unimib.pdf}}
  \end{minipage}
  \begin{minipage}[t]{0.81\textwidth}
    {
      \setstretch{1.42}
      {\textsc{Università degli Studi di Milano - Bicocca}} \\
      \textbf{Scuola di Scienze} \\
      \textbf{Dipartimento di Informatica, Sistemistica e Comunicazione} \\
      \textbf{Corso di Laurea Magistrale in Informatica} \\
      \par
    }
  \end{minipage}
  
  \vspace{40mm}
  
  \begin{center}
    {\LARGE{
        \setstretch{1.2}
        \textbf{Algoritmi per la trasformata di\vspace{1mm}}}}
    \vspace{1mm}
    {\LARGE{
        \setstretch{1.2}
        \textbf{Burrows--Wheeler posizionale con}}}
    \vspace{1mm}
    {\LARGE{
        \setstretch{1.2}
        \textbf{compressione run-length}}}
    
  \end{center}
  
  \vspace{43mm}

  \noindent
  {\large \textbf{Relatore:} \textit{Prof.ssa~Raffaella Rizzi}} \\

  \noindent
  {\large \textbf{Correlatore:} \textit{Dr.~Yuri Pirola}}
  
  \vspace{15mm}

  \begin{flushright}
    \textbf{\large Tesi di Laurea Magistrale di:} \\
    \large{\textit{Davide Cozzi}}\\
    \large{\textit{Matricola 829827}}
  \end{flushright}
  
  \vspace{25mm}
  \begin{center}
    {\large{\bf Anno Accademico 2021-2022}}
  \end{center}

  \restoregeometry
  
\end{titlepage}
\restoregeometry
\definecolor{shadecolor}{gray}{0.80}
\setlist{leftmargin = 2cm}
\newtheorem{teorema}{Teorema}
\newtheorem{definizione}{Definizione}
\newtheorem{esempio}{Esempio}
\newtheorem{corollario}{Corollario}
\newtheorem{lemma}{Lemma}
\newtheorem{osservazione}{Osservazione}
\newtheorem{nota}{Nota}
\newtheorem{esercizio}{Esercizio}

\algdef{SE}[DOWHILE]{Do}{doWhile}{\algorithmicdo}[1]{\algorithmicwhile\ #1}
\renewcommand{\bibname}{Bibliografia}
\renewcommand{\chaptermark}[1]{%
  \markboth{\chaptername
    \ \thechapter.\ #1}{}}
\renewcommand{\sectionmark}[1]{\markright{\thesection.\ #1}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}

\newcommand{\MYhref}[3][blue]{\href{#2}{\color{#1}{#3}}}%
\newcommand{\hiddenchapter}[1]{
  \stepcounter{chapter*}
  \chapter*{\arabic{chapter}\hspace{1em}{#1}}
}
\newcommand\xrowht[2][0]{\addstackgap[.5\dimexpr#2\relax]{\vphantom{#1}}}
% \pagenumbering{roman}
\begin{titlepage}
  \begin{flushright}
    \textit{E pensare che\\
      mi iscrissi a informatica\\
      per fare il sistemista!}
  \end{flushright}
\end{titlepage}
\newpage
\newpage
% \thispagestyle{plain}
% \begin{flushleft}
%   \huge{\textbf{Abstract}}
% \end{flushleft}
% \vspace{10mm}
% \input{include/abstract}
{
  \pagestyle{plain}
  \tableofcontents
  \cleardoublepage
}
\chapter{Introduzione}
Negli ultimi anni si è assistito a un cambio di paradigma nel campo della
bioinformatica, ovvero il passaggio dallo studio della sequenza lineare di un
singolo genoma a quello di un insieme di genomi, provenienti da un gran numero
di individui, al fine di poter considerare anche le varianti
geniche. Questo nuovo concetto è stato nominato per la prima volta, nel 2005,
da Tettelin \cite{tettelin} con il termine di \textbf{pangenoma}. Grazie ai
risultati ottenuti in pangenomica, ci sono stati miglioramenti sia nel 
campo della biologia che in quello della medicina personalizzata, grazie al
fatto che, con il pangenoma, si migliora la precisione della rappresentazione di
multipli genomi e delle loro differenze. \\
Il genoma umano di riferimento (GRCh38.p14) è composto da circa
3.1 miliardi di basi, con più di 88 milioni di
varianti tra i genomi sequenziati, secondo i risultati ottenuti nel 1000 Genome
Project (1KGP) \cite{tutorial} \cite{1kgp}. Considerando come la quantità dei
dati di sequenziamento sia destinata 
ad aumentare esponenzialmente nei prossimi anni, grazie al
miglioramento delle tecnologie di sequenziamento (Next Generation Sequencing e
Third-Generation Sequencing), risulta necessaria la costruzione di algoritmi e
strutture dati efficienti per gestire una tale informazione. 
In merito, uno degli approcci più usati per rappresentare il pangenoma è un
pannello di aplotipi \cite{pancon}, ovvero, computazionalmente, una matrice di
$M$ righe, corrispondenti agli individui, e $N$ colonne, corrispondenti ai siti
con le varianti. Si specifica che, con il termine
aplotipo, si intende l'insieme di alleli, ovvero di varianti, che, a meno di
mutazioni, un organismo eredita da ogni genitore.\\
In questo contesto trova spazio uno dei problemi fondamentali della
bioinformatica, ovvero quello del pattern matching. Inizialmente, tale concetto
era relativo allo studio di un piccolo pattern all'interno di un testo di
grandi dimensioni, ovvero il genoma di riferimento. Ora, con l'introduzione 
del pangenoma, tale problema si è adattato alle nuove strutture
dati.\\
Lo scopo di questa tesi è ottimizzare il problema del pattern 
matching, inteso come ricerca dei \textbf{set-maximal exact match}
  ($\SMEM$) tra un aplotipo 
esterno e un pannello di aplotipi, in una delle 
strutture dati più utilizzata: la \textbf{trasformata di Burrows--Wheeler
  Posizionale} ($\PBWT$) \cite{pbwt}. Il progetto di tesi ha quindi permesso lo
sviluppo di 
diverse strutture dati composte per la variante 
\textbf{run-length encoded} della \textbf{PBWT} ($\RLPBWT$),
efficienti dal punto di vista della memoria utilizzata.
Tale progetto è stato svolto in
collaborazione con due tra gli autori dei principali risultati ottenuti per la
\textbf{trasformata di Burrows--Wheeler run-length encoded} ($\RLBWT$)
\cite{rlbwt} 
\cite{gagie2020} \cite{moni} \cite{phoni}: il 
prof. Gagie (Dalhousie University) e la prof.ssa Boucher 
(University of Florida).\\
Parte delle strutture dati e degli algoritmi presentati in questa tesi sono
inseriti in un articolo, dal titolo \textit{Compressed data structures for
  population-scale positional Burrows--Wheeler transforms} \cite{rlpbwt}.
Al
momento della 
stesura di questa tesi, tale articolo è in fase di review per la rivista
\textit{Genome Research} (\textit{Cold Spring Harbor Laboratory Press}).
\subsection*{Struttura della tesi}
Nel Capitolo \ref{prechap}, si introdurranno i concetti di base, di ambito
computazionale e bioinformatico, necessari a
comprendere questa tesi. Nel Capitolo \ref{metchap}, verranno discussi i
contributi di questa tesi, descrivendo le soluzioni algoritmiche e le
metodologie utilizzate per raggiungere gli obiettivi prefissati. Nel dettaglio
verranno presentate varie strutture dati che saranno le componenti necessarie
alla produzione delle strutture dati composte per la $\RLPBWT$ e al calcolo
degli $\SMEM$. Nel Capitolo 
\ref{reschap}, si discuteranno i risultati ottenuti durante la
sperimentazione sui dati reali della \textit{phase 3} del \textbf{1000 Genome
  Project} \cite{1kgp}, progetto, iniziato nel 2008, che ha
visto lo sforzo 
della comunità scientifica internazionale per la catalogazione delle varianti
geniche umane. Infine, nel Capitolo \ref{conchap}, si trarranno le conclusioni 
di questo progetto di tesi, discutendone gli sviluppi futuri.
\chapter{Preliminari}
\label{prechap}
In questo capitolo verranno specificati tutti i concetti fondamentali, allo
stato dell'arte, atti a comprendere i metodi usati in questa tesi.
Si introdurranno i concetti di:
\begin{itemize}
  \item bitvector
  \item straight-line program e longest common extension query
  \item suffix array e longest common prefix
  \item trasformata di Burrows--Wheeler e la sua variante run-length encoded
  \item trasformata di Burrows--Wheeler posizionale
\end{itemize}
% L'unione di tutte queste strutture e di queste tecniche ha permesso la creazione
% della $\RLPBWT$.\\
\noindent
\textit{A livello di notazione, si specifica che, con
  $T[i,j]$ si intende la sottostringa del testo/sequenza/riga/colonna $T$,
  iniziante all'indice $i$ e terminante all'indice $j$ incluso. Qualora si
  avesse $j>i$ si identifica la sottostringa nulla $\varepsilon$.}

% sezione introduzione biologia
%\input{include/bio}

% sezione bitvector
\input{include/bitvector}

% sezione slp
\input{include/slp}

% sezione suffix array
\input{include/sa}

% sezione BWT
\input{include/bwt}

% sezione PBWT
\input{include/pbwt}


\chapter{Metodi}
\label{metchap}
In questo capitolo verranno illustrate le metodologie usate in questa tesi,
trattando tutte le soluzioni
che hanno portato alla costruzione di diverse varianti della $\RLPBWT$.\\
Verranno discussi gli usi delle singole componenti, le stime asintotiche sia in
tempo che in spazio, gli algoritmi di costruzione e di successivo calcolo degli
$\SMEM$ e i pro/contro delle varie strutture dati
ottenibili da tali componenti.

% sezione varianti RLPBWT
\input{include/var_rlpbwt}
\input{include/comp_map}
\input{include/comp_thr}
\input{include/comp_perm}
\input{include/comp_ra}
\input{include/comp_phi}
\input{include/match_lcp}
\input{include/match_ms}

% sezione RLPBWT naive
% \input{include/naive_rlpbwt}

% % sezione RLPBWT bitvectors
% \input{include/bv_rlpbwt}

% % sezione mapping RLPBWT
% %\input{include/map_rlpbwt}

% % sezione match massimali di RLPBWT naive/bitvectors
% \input{include/naive_bv_matches}

% % sezione RLPBWT ms
% \input{include/ms_rlpbwt}

% % sezione per struttura phi
% \input{include/phi}


\chapter{Risultati sperimentali}
\label{reschap}
Si riportano alcuni risultati sperimentali
relativi alle diverse implementazioni della $\RLPBWT$. Nel capitolo,
verranno discusse le modalità di sperimentazione e i
risultati ottenuti su alcuni pannelli della phase 3 del 1KGP \cite{1kgp},
progetto, nato nel 2008, che 
ha visto lo sforzo della comunità 
scientifica internazionale per la catalogazione delle varianti geniche
umane, tramite il sequenziamento di multipli individui. Il 1KGP risulta essere
uno dei più importanti progetti nell'ambito 
bioinformatico. \\  
Quindi, verranno confrontate le implementazioni degli algoritmi di calcolo degli
$\SMEM$ della $\PBWT$ di Durbin \cite{pbwt} e delle varianti per la
$\RLPBWT$.  
% sezione strumenti
\input{include/strumenti}
% sezione benchmark
%\input{include/bench}

% sezione complessità
%\input{include/compl}
\input{include/risultati}

\chapter{Conclusioni}
\label{conchap}
Fissato l'iniziale obiettivo di risolvere le problematiche relative alla
memoria richiesta dall'algoritmo 5 di Durbin, le implementazioni della
$\RLPBWT$ proposte in questa tesi, principalmente nelle strutture dati composte
segnalate nel 
Capitolo \ref{reschap}, hanno riportato risultati molto incoraggianti. Come
descritto nel medesimo capitolo, la quantità di memoria richiesta per il calcolo
degli $\SMEM$ risulta essere 
molto inferiore rispetto a quella richiesta dall'algoritmo
\texttt{matchIndexed}. D'altro canto, l'algoritmo \texttt{matchDynamic} di 
Durbin, per quanto non approfondito nell'articolo del 2014 \cite{pbwt}, risulta
essere ancor meno esoso di memoria, nonché incredibilmente più veloce dal punto
di vista dei tempi di calcolo, a eccezione del caso limite di avere un numero
esiguo di query. Lo svantaggio si ritrova anche nell'ordinamento dei risultati
e nella creazione di un'ulteriore $\PBWT$
che sembra implichino un non facile 
riadattamento dell'algoritmo alla risoluzione di altri task,
giudicando la letteratura degli ultimi anni, basata
principalmente sull'algoritmo 5.\\
Ipotizzando un possibile futuro in cui diventi comune
interrogare pannelli di aplotipi, con singole query da
un'interfaccia web o tramite API (alla stregua di quanto avviene
quotidianamente con BLAST), l'uso della $\RLPBWT$, in una delle sue
migliori varianti, avrebbe vantaggi in termini di tempo di calcolo
degli $\SMEM$, non solo
rispetto all'algoritmo 5 di Durbin, ma anche all'algoritmo
\texttt{matchDynamic}, 
alla luce dei risultati su singole query. Inoltre, quest'ultimo richiederebbe
ogni volta la ricostruzione della permutazione, a differenza delle
implementazioni della $\RLPBWT$ che potrebbero essere costruite e caricate in
memoria \textit{una tantum}.\\
Si possono rilevare alcune possibili migliorie in merito
alle varie implementazioni della $\RLPBWT$ presentate in questa tesi,
riferendosi essenzialmente alle soluzioni che prevedono il calcolo
dell'array delle matching statistics: 
\begin{itemize}
  \item si potrebbe pensare a un metodo per gestire in modo efficiente lo
  studio di più query contemporaneamente, migliorando i tempi di calcolo
  complessivi. Studiando contemporaneamente tutte le query si potrebbe, alla
  stregua di quanto visto con l'algoritmo \texttt{matchDynamic}, caricare in
  memoria solo la 
  colonna necessaria a un dato passo di computazione o comunque un sottoinsieme
  di colonne. In tal modo, si ridurrebbe l'uso massimo di memoria, qualora non
  fosse necessario caricare stabilmente la struttura per rispondere a diverse
  query 
  provenienti da varie fonti
  \item studiare eventuali ottimizzazioni per la componente \texttt{MAP-BV} al
  fine di comprendere se sia possibile tenere in
  memoria un solo bitvector $uv_k$, che funzioni in modo similare a quanto si ha
  con la componente \texttt{MAP-INT}
\end{itemize}
Inoltre, risulterebbe interessante, dal solo punto di vista teorico, una più
approfondita caratterizzazione delle complessità asintotiche, sia in spazio che
in tempo. Questa analisi, a causa degli algoritmi stessi e dell'uso di strutture
dati succinte, sarebbe sicuramente molto difficile, ma potrebbe portare a nuovi
spunti di riflessione per il campo dell'informatica teorica, oltre che della
bioinformatica.\\
Nonostante quanto detto, la qualità dei risultati è sufficiente
per stabilire che una variante run-length encoded della $\PBWT$,
come analizzato negli ultimi anni per la $\RLBWT$ con
MONI \cite{moni} e PHONI \cite{phoni}, è possibile e possa
permettere, nel prossimo futuro, la memorizzazione compatta delle informazioni
necessarie allo studio di grandi pannelli di aplotipi. In un futuro in cui le
tecnologie di sequencing produrranno sempre più dati, provenienti da sempre più
individui, avere a disposizione strutture dati efficienti in spazio permetterà
uno studio più approfondito dei dati stessi, in numerosi ambiti tra cui GWAS e
medicina personalizzata. 
% sezione sviluppi
\input{include/sviluppi}
%% BIBLIOGRAFIA
% \addcontentsline{toc}{chapter}{Bibliografia e sitografia}
% \printbibliography[title={Bibliografia e sitografia}]
% \addcontentsline{toc}{chapter}{Bibliografia}
\fancyhead[LO,RE]{\slshape \leftmark}
% \fancyhead[CO,CE]{\slshape\rightmark}
\fancyhead[LE,RO]{}
\addcontentsline{toc}{chapter}{Bibliografia}
\bibliographystyle{unsrt}
\bibliography{thesis}
%\dc{Sistemare tutte le citazione coi DOI}
%\appendix
% \chapter{Tabelle}
% \input{include/tabelle}
%\chapter{Algoritmi}
%\input{include/pseudo}
% \chapter{Esempi di File}
% \input{include/file}

% ringraziamenti
\input{include/ringraziamenti_final}
\end{document}

% LocalWords:  divergence prefix primis