\documentclass[11pt]{article}
\usepackage[margin=1.2in,a4paper]{geometry} % try also "letterpaper" instead of "a4paper"
\usepackage{enumitem} % this package is used to generate the custom chapter prefix "[Chapter number].[Exercise Number]"
\usepackage{amssymb}
\usepackage{amsmath}

%%%%%%%%%% macros %%%%%%%%%%
  \newcommand{\Fig}[1]{Figure~{#1}}
  \newcommand{\Def}[1]{Definition~{#1}}  
  \newcommand{\Thm}[1]{Theorem~{#1}}
  \newcommand{\Lemma}[1]{Lemma~{#1}}  
  \newcommand{\Sec}[1]{Section~{#1}}   
  \newcommand{\Btw}[1]{Insight~{#1}}
  \newcommand{\Prob}[1]{Problem~{#1}}  
  \newcommand{\Exe}[1]{Exercise~{#1}}  
  \newcommand{\Algo}[1]{Algorithm~{#1}}
  \newcommand{\Prop}[1]{Property~({#1})}  
  \newcommand{\Cor}[1]{Corollary~{#1}}  
  \newcommand{\ltdots}{..}  
  \newcommand{\wt}{\::\:}
  \newcommand{\st}{\:|\:}  
  \newcommand{\Eq}[1]{Equation~({#1})} 
  \newcommand{\Chap}[1]{Chapter~{#1}}
  \newcommand{\Ex}[1]{Example~{#1}}   
  \renewcommand{\pageref}[1]{{#1}}
  \DeclareMathOperator*{\argmax}{argmax}  
  \newcommand{\SA}{\ensuremath{\mathsf{SA}}}  
  \newcommand{\LCP}{\ensuremath{\mathsf{LCP}}}  
  \newcommand{\ST}{\ensuremath{\mathsf{ST}}}  
  \newcommand{\REV}[1]{\ensuremath{\underline{#1}}}  
  \newcommand{\BWT}{\ensuremath{\mathsf{BWT}}}  
  \newcommand{\DBG}{\ensuremath{\mathsf{DBG}}} % De Bruijn graph  
  \newcommand{\INTERVALFUNCTION}{\ensuremath{\mathbb{I}}}  
  \newcommand{\KL}{\ensuremath{\mathsf{KL}}}
  \newcommand{\SUS}{\ensuremath{\mathsf{SUS}}} 
  \newcommand{\SLT}{\ensuremath{\mathsf{SLT}}}     
  
%%%%%%%%%% macros %%%%%%%%%%

\begin{document}

%%%%%%%%%% header %%%%%%%%%%
\noindent {\sf\LARGE GENOME-SCALE ALGORITHM DESIGN} \\
\noindent {\sf by Veli M{\" a}kinen, Djamal Belazzougui, Fabio Cunial and Alexandru I. Tomescu}\\
\noindent {\sf Cambridge University Press, 2nd edition, 2023}\\
\noindent {\sf www.genome-scale.info}\\
\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%%%%%%%%%% header %%%%%%%%%%

\section*{Exercises for Chapter 15. Pangenomics}

\begin{enumerate}[label=15.\arabic*]

\item\label{exe:recoloredDBG} Recall the colored de Bruijn graph from Section 15.1.1. If every one of the $d$ colors corresponds to a distinct short read rather than to a whole genome or haplotype, one might consider reducing $d$ by reusing the same color across different reads. Assume that every read corresponds to a path with no repeated vertices, and that colors must allow one to reconstruct all and only the original reads. Which pairs of reads must be assigned different colors?
\item\label{exe:guidedDBG} Consider the right-to-left de Bruijn graph traversal of Insight 15.1. Describe the details of how to implement it using the suffix tree of the set of walks $P$. Do you need the whole suffix tree? How would you implement a left-to-right traversal?
\item\label{exe:compactedDBG} \emph{Compacting} a de Bruijn graph means repeatedly merging into a single vertex every pair of adjacent vertices $(u,v)$ such that $v$ is the only right-neighbor of $u$, and $u$ is the only left-neighbor of $v$, until no such merge is possible. This notion is related to the \emph{unitigs} from Section~13.2, and it is especially useful for sets of genomes from the same species. We assume that the vertices of the non-compacted de Bruijn graph are strings of length $k$.
\begin{enumerate}
\item[(i)] Describe the compacted de Bruijn graph of the \emph{de Bruijn string} defined in Exercise~11.7, where the graph and the string have the same order $k$. 
\item[(ii)] Show how to build the compacted de Bruijn graph directly from the suffix tree of the input sequences in linear time.
\item[(iii)] Implement a compacted de Bruijn graph using the frequency-aware representation of the standard de Bruijn graph from Section~9.7.2. How would you enforce the additional constraint that every vertex of the compacted graph must occur in some input sequence?
\item[(iv)] Given a substring of length at least $k$ of a vertex of the compacted de Bruijn graph, describe how to find the vertex it belongs to using the previous representation.
\end{enumerate}
\item\label{exe:core-pangenome} Given a pangenome, it is natural to look for the common parts that are shared by many individuals (the \emph{core genome}), since they most likely code for essential traits. This has obvious applications in finding targets for vaccines or antibacterials. Assume that the pangenome is represented as a colored de Bruijn graph whose nodes correspond to $k$-mers. Let a \emph{core $k$-mer} be one with at least $c$ colors, and let a \emph{bridging $k$-mer} be any $k$-mer that lies on a walk of length at most $\ell$ between two core $k$-mers. Describe an algorithm that computes all core and bridging $k$-mers in linear time in the number of $k$-mers. What advantages and disadvantages does this definition of core have?
\item\label{exe:iterative-align} Given a reference sequence and a sequence-to-graph aligner, describe an algorithm that grows a pangenome graph by iteratively aligning assembled contigs or long reads to the current graph. Does the graph contain cycles? Does its structure depend on the order with which the sequences are added? How are inversions represented?
\item\label{exe:pangenomecoordinates}
Pangenome graphs are often required to support \emph{positional queries}: Given an integer $i$ and a haplotype $T$ from a large population, find the node of the graph that contains the $i$-th position of $T$. This is useful for changing the frame of reference, or for finding the variant closest to $i$ in $T$. Describe how to support positional queries, assuming that all the haplotypes are represented as sequences of node identifiers in the pangenome DAG, and that the concatenation of all such strings is stored in a BWT as described in Insight~15.4.
\item\label{exe:foundergraphindexing} Show how to use the data structures covered earlier in this book to support fast exact pattern matching on the indexable founder graphs studied in \Sec{15.1.2}.
\item\label{exe:foundergraphconstruction} Fill in the details on how to efficiently construct the indexable founder graphs of \Sec{15.1.2}.
\item\label{exe:rlz-pangenome} Given a large set of genomes $\mathcal{S}$ from the same species, assume that we select a small subset $\mathcal{T} \subset \mathcal{S}$ that captures most of the variation, and that we concatenate all the elements of $\mathcal{T}$ into a string $T$. Assume also that we are given the \emph{relative Lempel--Ziv factorization} of every element of $\mathcal{S} \setminus \mathcal{T}$ with respect to $T$ (see Insight~12.3). Describe a way to build a directed pangenome graph for $\mathcal{S}$ by scanning the factorization and $T$. Does the choice of the source of a factor affect the graph?
\item\label{exe:alibi1}
\index{subject}{van Emde Boas tree}
Consider the pangenome read alignment scheme described in \Sec{15.2.1}. Develop the
bookkeeping data structures to map alignment position from the patched sequence $B$ to the position in $T$.
\item\label{exe:alibi2}
Consider the pangenome read alignment scheme described in \Sec{15.2.1}. Show how the wavelet tree can be
used to retrieve secondary occurrences, each in $O(\log n)$ time.
\item\label{exe:alibi3}
Consider the pangenome read alignment scheme described in \Sec{15.2.1} and recall \Exe{3.6}. Show how to use van Emde Boas trees
 to retrieve secondary occurrences, each in $O(\log\log n)$ time.
\item\label{exe:access-r-index}
Show that $r$-index supports accessing $L[i]$ in $O(\log n)$ time using the data structures we constructed for $L'$, where $L'[1..r]$ is the run-length encoding of $L[1..n]$.
\item\label{exe:r-index-construction}
Show that the data structures of the $r$-index that support reporting locations can be constructed as fast and as space-efficiently as the structures that support backward search. \emph{Hint:} Mimic the algorithm that builds the samples for the regular succinct suffix array.  
\item\label{exe:bidirectional-r-index}
Show that the $r$-index can be made functionally equivalent to the bidirectional BWT index of Section~9.4. Namely, it suffices to show that operation $\mathtt{rangeCount}(L,sp,ep,0,c-1)$, which counts how many characters there are in $L[sp..ep]$ smaller than $c$, can be supported in $O(\log n)$ time using only $L'[1..r]$, where $L'$ is the run-length encoding of $L$. The structure to support the operation should be constructed in $O((\sigma+ r)\log n\log \sigma)$ time, and it should take $O((\sigma+r)\log n \log \sigma)$ bits of space.   
\item\label{exe:prefixpruningdagBWT}
Show how to compute values $\kappa(i)$ for prefix pruning for prefixes $P_{1\ltdots i}$ of the pattern $P$ in the case of the BWT index on a labeled DAG.
\item\label{exe:dagBWT_allpaths}
Give a pseudocode for listing all the subpaths matching a pattern using the BWT index of the labeled DAG.
Extend the algorithm given in \Sec{15.2.3} for listing the matching prefix of a path starting at vertex $v$ with smallest lexicographic order.
\item Show that \Prob{prob:heaviestrecombinationpath} can be reduced to the particular shortest-path problem on DAGs from \Exe{4.16}.
\item\label{exe:dagshortestdetour}
Under what assumptions does the shortest-detour algorithm of \Sec{6.1.2}, applied to aligning a haploid prediction to the labeled DAG of a diploid ground-truth, give $O(dn)$ running time,
where $d$ is the resulting edit distance and $n$ is the largest of DAG size and haploid length?
\item\label{exe:pangenomeBWT} A \emph{series-parallel graph} $G$ is either a single edge that connects a source node to a sink node, or it is the result of merging the sink of a series-parallel graph $G_1$ to the source of a series-parallel graph $G_2$ (\emph{series composition}), or of merging the source of $G_1$ to the source of $G_2$ and the sink of $G_1$ to the sink of $G_2$ (\emph{parallel composition}). A \emph{bubble} is the result of all parallel compositions that affect the same source and sink nodes. Assume that we are given a pangenome graph $G$ that is a series-parallel graph with arbitrary string labels on the nodes, and with a small number of bubbles. Describe a representation of $G$ as a string $T$, such that all the paths inside the same bubble correspond to a compact block in the BWT of $T$, and such that one can count the occurrences of a pattern in $G$ via a modified backward search in the BWT of $T$. How much space does your data structure take? \emph{Hint:} Apply ideas from the \emph{positional BWT} in Section~14.2.2. 

\end{enumerate}

\end{document}  