\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{\ltdots}{..}  
  \newcommand{\wt}{\::\:}
  \newcommand{\Eq}[1]{Equation~({#1})} 
  \newcommand{\Chap}[1]{Chapter~{#1}}
  \newcommand{\Ex}[1]{Example~{#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}}}  
  
  %%%% custom interval notations %%%%
  \makeatletter
  \newcommand{\fullbullet}{\begin{picture}(-1,.5)(1,-.2)\circle*{2.1}\end{picture}}
  
  \newcommand\SP[1]{\vbox{\m@th\ialign{##\crcr
      \kern.1em\fullbullet\crcr\noalign{\kern-\p@\nointerlineskip}%
      $\hfil\displaystyle\overline{#1}\hfil$\crcr}}}

  \newcommand\EP[1]{\vbox{\m@th\ialign{##\crcr
	  \hfill\fullbullet\crcr\noalign{\kern-\p@\nointerlineskip}%
      $\hfil\displaystyle\overline{#1}\hfil$\crcr}}}
      
  \newcommand\INTERVAL[1]{\vbox{\m@th\ialign{##\crcr
	  \kern.1em\fullbullet\hfill\fullbullet\crcr\noalign{\kern-\p@\nointerlineskip}%
      $\hfil\displaystyle\overline{#1}\hfil$\crcr}}}
      
  \makeatother
  %%%% custom interval notations %%%%
  
%%%%%%%%%% 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, 2015}\\
\noindent {\sf www.genome-scale.info}\\
\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%%%%%%%%%% header %%%%%%%%%%

\section*{Exercises for Chapter 9. Burrows--Wheeler indexes}

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

\item Consider the original definition of the Burrows--Wheeler transform with the cyclic shifts, without a unique endmarker $\#$ added to the end of the string. Assume you have a fast algorithm to compute our default transform that assumes the endmarker is added.
Show that you can feed that algorithm an input such that you can extract the original cyclic shift transform efficiently from the output. 
 
\item \label{exe:buildingSuccinctSA} Describe an algorithm that builds the succinct suffix array of a string $T$ from the BWT index of $T$, within the bounds of \Thm{9.6}.

\item \label{exe:batched2} Consider the strategy for answering a set of $\mathtt{occ}$ locate queries in batch described in \Sec{9.2.4}. Suppose that, once all positions in $\SA_{T\#}$ have been marked, a bitvector $\mathtt{marked}[1 \ltdots n+1]$ is indexed to answer rank queries. Describe an alternative way to implement the batch extraction within the same asymptotic time bound as the one described in \Sec{9.2.4}, but \emph{without resorting to radix-sort}. Which strategy is more space-efficient? Which one is faster? The answer may vary depending on whether $\mathtt{occ}$ is small or large. 

\item \label{exe:removingSharps} Recall that at the very end of the construction algorithm described in \Sec{9.3} we need to convert the BWT of the padded string $X$ into the BWT of string $T\#$. Prove that $\BWT_X = T[n] \cdot \#^{k-1} \cdot W$ and $\BWT_{T\#} = T[n] \cdot W$, where $n=|T|$, $k=|X|-n$, and string $W$ is a permutation of $T[1 \ltdots n-1]$.

\item Assume that you have a machine with $P$ processors that share the same memory. Adapt \Algo{9.3} to make use of all $P$ processors, and estimate the resulting speedup with respect to \Algo{9.3}.

\item \label{exe:weinerLinksOfChildren} Recall that \Prop{1} is key for implementing \Algo{9.3} with just one BWT. Prove this property.

\item \label{exe:enumerateLeftExtended} In many applications, the operation $\mathtt{enumerateLeft}(i,j)$, where $[i \ltdots j]=\INTERVALFUNCTION(W,T)$, is immediately followed by operations $\mathtt{extendLeft}\left(c,\INTERVALFUNCTION(W,T),\INTERVALFUNCTION(\REV{W},\REV{T})\right)$ applied to every distinct character $c$ returned by $\mathtt{enumerateLeft}(i,j)$.
\begin{enumerate}
\item \begin{sloppypar}
Show how to use operation $\mathtt{rangeListExtended}(T,i,j,l,r)$ defined in \Exe{3.12} to efficiently support a new operation called $\mathtt{enumerateLeftExtended}(\INTERVALFUNCTION(W,T),\INTERVALFUNCTION(\REV{W},\REV{T}))$ that returns the distinct characters that appear in substring $\BWT_{T\#}[i \ltdots j]$, and for each such character $c$ returns the pair of intervals computed by $\mathtt{extendLeft}\left(c,\INTERVALFUNCTION(W,T),\INTERVALFUNCTION(\REV{W},\REV{T})\right)$. Implement also the symmetric operation $\mathtt{enumerateRightExtended}$.
\end{sloppypar}
\item \begin{sloppypar}
Reimplement \Algo{9.3} to use the operations $\mathtt{enumerateLeftExtended}$ and $\mathtt{enumerateRightExtended}$ instead of $\mathtt{enumerateLeft}$, $\mathtt{enumerateRight}$, $\mathtt{extendLeft}$, and $\mathtt{extendRight}$.
\end{sloppypar}
\end{enumerate}

\item \label{exe:propTreeBwt} Recall that \Prop{2} is key for navigating the Burrows--Wheeler index of a labeled tree top-down (\Sec{9.5.1}). Prove this property.

\item \label{prob:treeBWT_startingPositions} Consider the Burrows--Wheeler index of a tree $\mathcal{T}$ described in \Sec{9.5}. 
\begin{enumerate}
\item Given a character $c \in [1 \ltdots \sigma]$, let \SP{c} be the starting position of its interval $\INTERVAL{c}$ in $\BWT_\mathcal{T}$, and let $C'[1 \ltdots \sigma]$ be an array such that $C'[c]=\SP{c}$. Describe an $O(n)$-time algorithm to compute $C'$ from $C$ and $\mathtt{last}$.
\item Recall that $\mathbb{I}(v)=[\SP{v} \ltdots \EP{v}]$ is the interval in $\BWT_\mathcal{T}$ that contains all the children of node $v$, and that $\mathbb{I}'(v)$ is the position of the arc $(v,\mathtt{parent}(v))$ in $\BWT_\mathcal{T}$. Let $D[1 \ltdots n+m-1]$ be an array such that $D[i]=\SP{v}$ where $\mathbb{I}'(v)=i$, or $-1$ if $v$ is a leaf. Describe an $O(n+m)$-time algorithm to compute $D$ from $C'$, $\mathtt{last}$ and $\mathtt{labels}$. \emph{Hint.} Use the same high-level strategy as the one in Lemmas 8.7 and 9.9.
\item Give the pseudocode of an $O(n)$-time algorithm that reconstructs the original tree $\mathcal{T}$ from $\BWT_\mathcal{T}$ and $D$, in depth-first order.
\end{enumerate}

\item \label{prob:treeBWT_construction_doubling} In order to build the Burrows--Wheeler index of a tree $\mathcal{T}$ described in \Sec{9.5}, we can adapt the prefix-doubling approach used in \Lemma{8.8} for building suffix arrays. In particular, assume that we want to assign to every node $v$ the order $R(v)$ of its path to the root, among all such paths in $\mathcal{T}$. We define the $i$th \emph{contraction} of tree $\mathcal{T}$ as the graph $\widetilde{T}^i=(V,E^i)$ such that $(u,v) \in E^i$ iff $v_1,v_2,\dots,v_{2^{i+1}}$ is a path in $\mathcal{T}$ with $v_0=u$ and $v_{2^{i+1}}=v$. Clearly $\widetilde{T}^0=\mathcal{T}$, and $E^{i+1}$ is the set of all pairs $(u,v)$ such that $P=u,w,v$ is a path in $\widetilde{T}^i$. Show how to iteratively refine the value $R(v)$ for every node, starting from the initial approximation $R^{0}(v)=\SP{\ell(v)}=C'[\ell(v)]$ computed as in \Exe{9.9}. Describe the time and space complexity of your algorithm.

\item \label{prob:treeBWT_construction_smallSuffixes} Assume that we want to generalize the recursive, $O(\sigma+n)$-time algorithm for building the suffix array $\SA_{S\#}$ of a string $S$ to a similar algorithm for building the Burrows--Wheeler index of a labeled tree $\mathcal{T}$ described in \Sec{9.5}. Do the results in \Def{8.9}, \Lemma{8.10}, and \Lemma{8.11} still hold? Does the overall generalization still achieve linear time for any $\mathcal{T}$? If not, for which topologies or labelings of $\mathcal{T}$ does the generalization achieve linear time?

\item \label{prob:graphBWT_sampling} Assume that a numerical value $\mathtt{id}(v)$ must be associated with every vertex $v$ of a labeled, strongly distinguishable DAG $G$: for example, $\mathtt{id}(v)$ could be the probability of reaching vertex $v$ from $s$. Assume that, whenever there is exactly one path $P$ connecting vertex $u$ to vertex $v$, we have that $\mathtt{id}(v)=f(\mathtt{id}(u),|P|)$, where $f$ is a known function. Describe a method to augment the Burrows--Wheeler index of $G$ described in \Sec{9.6} with the values of $\mathtt{id}$, and its space and time complexity. \emph{Hint.} Adapt the strategy used for strings in \Sec{9.2.3}.

\item \label{exe:encodingLabels} Consider the Burrows--Wheeler index of a labeled, strongly distinguishable DAG described in \Sec{9.6}, and assume that $\mathtt{labels}$ is represented with $\sigma+1$ bitvectors $B_{c}[1 \ltdots m]$ for all $c \in [1 \ltdots \sigma+1]$, where $B_{c}[i]=1$ if and only if $\mathtt{labels}[i]=c$. Describe a more space-efficient encoding of $\mathtt{labels}$. Does it speed up the operations described in \Sec{9.6}?

\item Given any directed labeled graph $G=(V,E,\Sigma)$, \Algo{9.4} builds a reverse-deterministic graph $G'=(V',E',\Sigma)$ in which a vertex $v \in V'$ corresponds to \emph{a subset of $V$}. Adapt the algorithm so that a vertex $v \in G'$ corresponds to \emph{a subset of $E$}. Show an example in which the number of vertices in the reverse-deterministic graph produced by this version of the algorithm is smaller than the number of vertices in the reverse-deterministic graph produced by \Algo{9.4}.

\item \label{exe:noDoubleExponential} Recall that in \Sec{9.6.3} a labeled DAG $G$ is transformed into a reverse-deterministic DAG $G'$, and then $G'$ is itself transformed into a strongly distinguishable DAG $G^*$. Show that $|G^*| \in O(2^{|G|})$ in the worst case.

\item \label{prob:graphBWT_construction} Consider the algorithm to enforce distinguishability described in \Sec{9.6.3}.
\begin{enumerate}
\item Show that this algorithm does not also enforce reverse-determinism.
\item Assume that the input to this algorithm contains two arcs $(u,w)$ and $(v,w)$ such that $\ell(u)=\ell(v)$: give an upper bound on the number of vertices that result from the projection of $u$ and $v$ to the output.
\item Modify the algorithm to build a distinguishable, rather than a strongly distinguishable, DAG.
\item Modify the algorithm to decide whether the input graph is distinguishable or not.
\item Implement the algorithm using just sorts, scans, and joins of lists of tuples of integers, \emph{without storing or manipulating strings $\mathtt{path}$ explicitly}. Give the pseudocode of your implementation.
\item Give the time and space complexity of the algorithm as a function of the size of its input and its output.
\end{enumerate}

\item \label{exe:languages} Describe a labeled, strongly distinguishable DAG that recognizes an infinite language. Describe an infinite language that cannot be recognized by any labeled, stronglyvdistinguishable DAG.

\item \label{exe:dbgFrequencyIndependent} Consider the frequency-oblivious representation of a de Bruijn graph described in \Sec{9.7.1}. Show how to implement the function $\mathtt{getArc}$ when $\mathtt{labels}$ contains characters in $\Sigma \cup \Sigma'$.

\item \label{exe:firstK} Recall that marking the starting position of every interval in $\BWT_{T\#}$ that corresponds to a $k$-mer is a key step for building both the frequency-aware and the frequency-oblivious representation of a de Bruijn graph. Prove that \Lemma{9.22} performs this marking correctly.

\item \label{exe:dbgForSetsOfStrings} Some applications in high-throughput sequencing require the de Bruijn graph of \emph{a set of strings} $\mathcal{R}=\{R^1,R^2,\dots,R^r\}$. Describe how to adapt the data structures in Sections 9.7.1 and 9.7.2 to represent the de Bruijn graph of string $R=R^1 \# R^2 \# \cdots \# R^r \#$, where $\# \notin [1 \ltdots \sigma]$. Give an upper bound on the space taken by the frequency-oblivious and by the frequency-aware representation.


\item \label{dbg:collapse} Describe the frequency-oblivious and the frequency-aware representations of the de Bruijn graph $\DBG_{T,k}$ when every string of length $k$ on a reference alphabet $\Sigma$ occurs at most once in $T$.

\end{enumerate}

\end{document}  
