\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}
\usepackage{url}

%%%%%%%%%% 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}}     
  \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, 2015}\\
\noindent {\sf www.genome-scale.info}\\
\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}
%%%%%%%%%% header %%%%%%%%%%

\section*{Exercises for Chapter 11. Genome analysis and comparison}

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

\item \label{exe:Iconstruction}
Give an algorithm to construct the indicator bitvector $I$ of \Algo{11.2} in $O((m+n) \log \sigma)$ time and $O((m+n) \log \sigma)$ bits of space. 

\item 
Modify the algorithm for maximal unique matches on two strings to use two bidirectional indexes instead of the indicator bitvector as in our solution for maximal exact matches.

\item \label{exe:multiMUMS}
Recall the algorithm to compute maximal unique matches for multiple strings through document counting in \Sec{8.4.3}. It is possible to implement this algorithm using $O(n \log \sigma)$ bits of space and $O(n \log \sigma \log n)$ time, but this requires some advanced data structures not covered in this book. Assume you have a data structure for solving the \emph{dynamic partial sums} problem, that is, to insert, delete, and query elements of a list of non-negative integers, where the queries ask to sum values up to position $i$ and to find the largest $i$ such that the sum of values up to $i$ is at most a given threshold $x$. There is a data structure for solving the updates and queries in $O(\log n)$ time using $O(n \log \sigma)$ bits of space, where $n$ is the sum of the stored values. Assume also that you have a succinct representation of $\LCP$ values. There is a representation that uses $2n$ bits, such that the extraction of $\LCP[i]$ takes the same time as the extraction of $\SA[i]$. Now, observe that the suffix array and the $\LCP$ array, with some auxiliary data structures, are sufficient to simulate the algorithm without any need for explicit suffix trees. Especially, differences between consecutive entries of string and node depths can be stored with the dynamic partial sums data structure. Fill in the details of this space-efficient algorithm.     


\item \label{exe:maw2} Prove \Thm{11.7} assuming that in the output a minimal absent word $aWb$ is encoded as a triplet $(i,j,|W|)$, where $i$ (respectively $j$) is the starting position of an occurrence of $aW$ in $S$ (respectively $Wb$ in $S$).   

\item \label{exe:maw1} 
Prove that only a maximal repeat of a string $S \in [1 \ltdots \sigma]^+$ can be the infix $W$ of a minimal absent word $aWb$ of $S$, where $a$ and $b$ are characters in $[1 \ltdots \sigma]$.

\item\label{exe:maws_UB} Show that the number of minimal absent words in a string 
of length $n$ over an alphabet $[1\ltdots\sigma]$ is $O(n\sigma)$. \emph{Hint}. Use 
the result of the previous exercise.

\item\label{exe:maws_LB} A $\sigma$-ary de Bruijn sequence of order $k$ is a circular sequence of length $\sigma^k$ 
that contains all the possible $k$-mers over alphabet $\Sigma=[1\ltdots\sigma]$. It can be constructed by spelling all the labels in an Eulerian cycle (a cycle that goes through all the edges) 
of a de Bruijn graph with parameters $\Sigma$ and $k$. The sequence can be easily transformed 
into a string (non-circular sequence) of length $\sigma^k+k-1$ that contains all the possible $k$-mers over alphabet $\Sigma$. 
\begin{itemize}
\item[a)] Describe the transformation from circular sequence to string. 
\item[b)] Show that the number of minimal absent words in this string is $\sigma^{k+1}$. 
\end{itemize}

\item\label{exe:matchinganchors}
Assume that you have a set of local alignments between two genomes $A$ and $B$, with an alignment score associated with each alignment.
Model the input as a bipartite graph where overlapping alignments in $A$ and in $B$ form a vertex, respectively, to two sides of the graph. Alignments form weighted edges. Which problem in \Chap{5} suits the purpose of finding anchors for rearrangement algorithms?

\item Recall that the formula $p_{S}(W)=f_{F}(W)/(|S|-|W|+1)$ used in \Sec{11.2} to estimate the empirical probability of substring $W$ of $S$ assumes that $W$ can occur at every position of $T$. Describe a more accurate expression for $p_{S}(W)$ that takes into account the \emph{shortest period} of $W$.


\item \label{exe:kmerKernelJaccard} 
The \emph{Jaccard distance} between two sets $\mathcal{S}$ and $\mathcal{T}$ is defined as $J(\mathcal{S},\mathcal{T}) = |\mathcal{S} \cap \mathcal{T}|/|\mathcal{S} \cup \mathcal{T}|$. Adapt the algorithms in \Sec{11.2.1} to compute $J(\mathcal{S},\mathcal{T})$, both in the case where $\mathcal{S}$ and $\mathcal{T}$ are the sets of all distinct $k$-mers that occur in $S$ and in $T$, respectively, and in the case in which $\mathcal{S}$ and $\mathcal{T}$ are the sets of all distinct \emph{substrings}, of any length, that occur in $S$ and in $T$, respectively.

\item \label{exe:probKmerKernel} Adapt \Lemma{11.11} to compute a variant of the $k$-mer kernel in which $\mathbf{S}_{k}[W]=p_{S}(W)$ and $\mathbf{T}_{k}[W]=p_{T}(W)$ for every $W \in [1 \ltdots \sigma]^k$.

\item \label{exe:probSubstringKernel} Adapt \Cor{11.13} to compute a variant of the substring kernel in which $\mathbf{S}_{\infty}[W]=p_{S}(W)$ and $\mathbf{T}_{\infty}[W]=p_{T}(W)$ for every $W \in [1 \ltdots \sigma]^k$.

\item \label{exe:kEntropy} 
Given a string $S$ on alphabet $[1 \ltdots \sigma]$ and a substring $W$ of $S$, let $\mathtt{right}(W)$ be the set of characters that occur in $S$ after $W$. More formally, $\mathtt{right}(W) = \{a \in [1 \ltdots \sigma] \st f_{S}(Wa)>0\}$. The \emph{$k$th order empirical entropy} of $S$ is defined as follows:
$$
\mathsf{H}(S,k) = \frac{1}{|S|}\sum_{W \in [1 \ltdots \sigma]^k} \sum_{a \in \mathtt{right}(W)} f_{S}(Wa) \log \left( \frac{f_{S}(W)}{f_{S}(Wa)} \right).
$$
Intuitively, $\mathsf{H}(S,k)$ measures the amount of uncertainty in predicting the character that follows a context of length $k$, thus it is a lower bound for the size of a compressed version of $S$ in which every character is assigned a codeword that depends on the preceding context of length $k$. Adapt the algorithms in \Sec{11.2.1} to compute $\mathsf{H}(S,k)$ for $k \in [k_1 \ltdots k_2]$ using the bidirectional BWT index of $S$, and state the complexity of your solution.

\item \label{exe:D2statistics}

Let $S$ and $T$ be two strings on alphabet $[1 \ltdots \sigma]$, and let $\mathbf{S}$ and $\mathbf{T}$ be their composition vectors indexed by all possible $k$-mers. When the probability distribution of characters in $[1 \ltdots \sigma]$ is highly nonuniform, the inner product between $\mathbf{S}$ and $\mathbf{T}$ (also known as the \emph{$D_2$ statistic}) is known to be dominated by noise. To solve this problem, raw counts are typically corrected by \emph{expected counts} that depend on $p(W)=\prod_{i=1}^{|W|}p(W[i])$, the probability of observing string $W$ if characters at different positions in $S$ are independent, identically distributed, and have empirical probability $p(a)=f_{ST}(a)/(|S|+|T|)$ for $a \in [1 \ltdots \sigma]$. For example, letting $\tilde{\mathbf{S}}[W]=\mathbf{S}[W]-(|S|-k+1)p(W)$, the following variants of $D_2$ have been proposed:
\begin{eqnarray*}
D_2^s & = & \sum_{W \in [1 \ltdots \sigma]^k} \frac{\tilde{\mathbf{S}}[W] \tilde{\mathbf{T}}[W]}{\sqrt{\tilde{\mathbf{S}}[W]^2 + \tilde{\mathbf{T}}[W]^2}}, \\
D_2^* & = & \sum_{W \in [1 \ltdots \sigma]^k} \frac{\tilde{\mathbf{S}}[W] \tilde{\mathbf{T}}[W]}{\sqrt{(|S|-k+1)(|T|-k+1)} \cdot p(W)}.
\end{eqnarray*}
Adapt the algorithms described in \Sec{11.2.1} to compute $D_2^s$, $D_2^*$, and similar variants based on $p(W)$, using the bidirectional BWT index of $S$ and $T$, and state their complexity.

\item \label{exe:choosingK} Show how to implement the computations described in \Btw{11.3} using the bidirectional BWT index of $S \in [1 \ltdots \sigma]^n$. More precisely, do the following.
\begin{itemize}
\item[a)] Show how to compute the number of distinct $k$-mers that appear at least twice 
(repeating $k$-mers) in time $O(n\log\sigma)$ and space $O(n\log\sigma)$ bits. 
\item[b)] Suppose that we want to compute the number of repeating $k$-mers 
for all values of $k$ in a given range $[k_1 \ltdots k_2]$. A naive extension of the 
algorithm in (a) would take time $O((k_1-k_2)n\log\sigma)$ and it would use an additional 
$O((k_1-k_2)\log n)$ bits of space to store the result. Show how to improve this running time to $O(n\log\sigma)$, using the same space.
\item [c)] 
Show how to compute the Kullback--Leibler divergence described in Insight 11.3, simultaneously for all values of $k$ in $[k_1 \ltdots k_2]$, in time $O(n\log\sigma)$ and an additional $O(k_{1}-k_{2})$ computer words of space to store
the result.
\end{itemize}

\item \label{exe:whyCosine} Assume that vectors $\mathbf{S}$ and $\mathbf{T}$ have only two dimensions. Show that \Eq{11.1} is indeed the cosine of the angle between $\mathbf{S}$ and $\mathbf{T}$.

\item \label{exe:kernelsWithSuffixTrees} Write a program that computes all kernels and complexity measures described in \Sec{11.2.1}, given the suffix tree of the only input string, or the generalized suffix tree of the two input strings.

\item \label{exe:denas} Adapt the algorithm in \Sec{11.2.2} to compute the substring kernel with Markovian corrections in $O(n\log\sigma)$ time and space, where $n$ is the sum of the lengths of the input strings.

\item 
Given strings $W$ and $S$, and characters $a$ and $b$ on an alphabet $\Sigma=[1 \ltdots \sigma]$, consider the following expected probability of observing $aWb$ in $S$, analogous to \Eq{11.2}: 
$$
\tilde{p}_{W,S}(a,b)=\frac{p_{S}(aW) \cdot p_{S}(Wb)}{p_{S}(W)}.
$$
Moreover, consider the Kullback--Leibler divergence between the observed and expected distribution of $\tilde{p}_{W,S}$ over pairs of characters $(a,b)$:
$$
\KL_{S}(W) = \sum_{(a,b) \in \Sigma \times \Sigma} p_{W,S}(a,b) \cdot \ln \left( \frac{p_{W,S}(a,b)}{\tilde{p}_{W,S}(a,b)} \right),
$$
where we set $\ln(p_{W,S}(a,b)/\tilde{p}_{W,S}(a,b))=0$ whenever $\tilde{p}_{W,S}(a,b)=0$. Given strings $S$ and $T$, let $\mathbf{S}$ and $\mathbf{T}$ be infinite vectors indexed by all strings on alphabet $[1 \ltdots \sigma]$, such that $\mathbf{S}[W]=\KL_{S}(W)$ and $\mathbf{T}[W]=\KL_{T}(W)$. Describe an algorithm to compute the cosine of vectors $\mathbf{S}$ and $\mathbf{T}$ as defined in \Eq{11.1}.

\item \label{exe:sus}
Recall that the \emph{shortest unique substring array} $\SUS_{S}[1 \ltdots n]$ of a string $S \in [1 \ltdots \sigma]^n$ is such that $\SUS_{S}[i]$ is the length of the shortest substring that starts at position $i$ in $S$ and that occurs exactly once in $S$. 
\begin{enumerate}
\item Adapt to $\SUS_{S}$ the left-to-right and right-to-left algorithms described in \Sec{11.2.3} for computing matching statistics.
\item Describe how to compute $\SUS_{S}$ by an $O(n)$ bottom-up navigation of the suffix tree of $S$.
\end{enumerate}

\item \label{exe:msAlpha} Show how to compute $\sum_{j=|\ell(u)|+1}^{|W|}\alpha(W[1 \ltdots j])$ in constant time for all the weighting schemes described in \Sec{11.2.3}. More generally, show that if $\alpha(W)$ depends just on the length of $W$ rather than on its characters, and if $\alpha(W)=0$ for $|W|$ bigger than some threshold $\tau$, we can access $\sum_{j=|\ell(u)|+1}^{|W|}\alpha(W[1 \ltdots j])$ in constant time after an $O(\tau)$-time and $O(\tau\log\tau)$-space precomputation. 

\item \label{exe:msDictionary} Let $S$ and $T$ be strings, and let $D=\{d_1,d_2,\dots,d_k\}$ be a fixed set of strings with weights $\{w_1, w_2, \dots, w_k\}$. Show how to compute the kernel $\kappa(S,T)$ in \Eq{11.4} restricted to the strings in $D$, using matching statistics and with the same time complexity as that of \Thm{11.22}.

\item Given strings $S$ and $T$ and a window size $w \in [1 \ltdots |S|-1]$, describe an algorithm that computes the kernel $\kappa(S[i \ltdots i+w-1],T)$ in \Eq{11.4} for all $i \in [1 \ltdots |S|-w+1]$, performing fewer than $m$ operations per position. \emph{Hint}. Adapt the approach in \Thm{11.22}.

\item \label{exe:dawg} Consider the suffix-link tree $\SLT_T$ of a string $T$, augmented with implicit Weiner links and their destinations. Describe an algorithm that adds to the suffix tree $\ST_{\REV{T}}$ a node for every label $W$ of a node in $\SLT_T$ (if string $W$ is not already the label of a node in $\ST_{\REV{T}}$), and that adds to every node of this augmented suffix tree a pointer to its closest ancestor labeled by a string in $\SLT_T$. The relationship between $\SLT_T$ and $\ST_{\REV{T}}$ is further explored in \Exe{8.19}.

\item \label{exe:mismatchKernels} 

Given two $k$-mers $V$ and $W$ on alphabet $[1 \ltdots \sigma]$, recall that $D_{\mathsf{H}}(V,W)$ is the Hamming distance between $V$ and $W$, and that $B(W,m)$ is the subset of $[1 \ltdots \sigma]^k$ that lies at Hamming distance at most $m$ from $W$. Give a closed-form expression for the size of $B(V,m) \cap B(W,m)$ for every possible value of $D_{\mathsf{H}}(V,W)$ when $m=2$.

\item \label{ex:gappedKernel} 

Given a string $S$ on alphabet $[1 \ltdots \sigma]$, and given a string $W$ of length $k$, let $f_{S}(W,m)$ be the number of substrings of $S$ of length $k+m$ that contain $W$ as a \emph{subsequence}. Consider the following \emph{gapped kernel} between two strings $S$ and $T$:
$$
\kappa(S,T,k,m) = \sum_{W \in [1 \ltdots \sigma]^k} f_{S}(W,m) \cdot f_{T}(W,m).
$$
Adapt the approach described in \Sec{11.2.4} to compute the gapped kernel, and state its complexity.

\item \label{exe:neighborhoodKernel} In the \emph{neighborhood kernel}, the similarity of two strings $S$ and $T$ is expressed in terms of the similarities of their \emph{neighborhoods} $N(S)$ and $N(T)$, where $N(S)$ contains a given set of strings that the user believes to be similar or related to $S$. The neighborhood kernel is defined as
$$
\kappa_{N}(S,T)=\sum_{U \in N(S)}\sum_{V \in N(T)}\kappa(U,V),
$$
where $\kappa(U,V)$ is a given kernel. Describe how to adapt the approaches described in \Sec{11.2.4} to compute the neighborhood kernel.

\item \label{exe:distributivity} Prove that $C(ST)+C(U) \leq C(SU)+C(TU)$, by using the symmetry of $C$.

\item \label{exe:ncd} Complete the proof of \Thm{11.31} with the two missing cases, using the distributivity of $C$.

\section*{Additional exercises not in the book}

\item 

Simulate Algorithm 11.1 (maximal repeat computation using the bidirectional BWT index) on text \texttt{TACAGACAC}.

\item 

Read the paper 
\begin{itemize}
\item Richard Durbin. Efficient haplotype matching and storage using the positional Burrows-Wheeler transform (PBWT). 
\emph{Bioinformatics}, 30(9): 1266-1272 (2014). \url{http://dx.doi.org/10.1093/bioinformatics/btu014}.
\end{itemize}

What is the difference between PBWT and normal BWT? How is the input to the algorithm produced?


\end{enumerate}

\end{document}  
