\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}}     
  \DeclareMathOperator*{\argmax}{argmax}  
  \newcommand{\SA}{\ensuremath{\mathsf{SA}}}  
  \newcommand{\LCP}{\ensuremath{\mathsf{LCP}}}  
  \newcommand{\ST}{\ensuremath{\mathsf{ST}}} 
  \newcommand{\MS}{\ensuremath{\mathsf{MS}}}   
  \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 17. Metagenomics}

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

\item Show that \Prob{17.1} can be reduced to a minimum-cost network flow problem, by extending the reduction constructed in \Sec{5.3.3} for \Prob{5.7}.
\label{exe:metagenomics-CSAE}
\item Show that you can reduce \Prob{17.1} to one in which every read vertex in $A$ has at least two incident edges.
\item Discuss how to modify the statement of \Prob{17.1} if the probability of sequencing a read from a certain location inside each genome is no longer uniform for all locations, but follows a different distribution function, which is known beforehand.
\item Explain what changes you need to make to the reduction constructed in Exercise~\ref{exe:metagenomics-CSAE} if the objective function in \Prob{17.1} is
\begin{equation}
(1-\alpha) \!\!\!\!\sum_{(x,y) \in M} c(x,y) + \alpha \sum_{i = 1}^{m}\sum_{j=1}^{s_i}\left(\frac{c_i}{s_i} - d_M(y_{i,j})\right)^2.
\end{equation}
\emph{Hint.} Recall \Exe{5.16}.
\item What can you say about the complexity of \Prob{17.2} for $\alpha = 0$? What about $\alpha = 1$?

\item \label{exe:bwtOfHighFrequencySpecies} Describe an algorithm to compute the BWT of the reads that are kept and of the reads that are filtered out in \Sec{17.2.1}, by reusing the BWT of the original file. Recall that reads in the input file $R$ are separated by distinct binary strings on the artificial characters $\#_0$ and $\#_1$ which do not belong to $[1 \ltdots \sigma]$.

\item \label{exe:discardKmers} Given the concatenation $R$ of all reads in a metagenomic sample as defined in \Sec{17.2}, consider the interval of a $k_2$-mer $W$ in $\BWT_R$. \Sec{17.2.2} claims that, during the creation of pre-clusters, we can discard any $k_2$-mer $V$ whose interval in $\BWT_R$ coincides with the interval of $aW$ for some $a \in [1 \ltdots \sigma]$. Prove this claim, and describe an algorithm that implements it in linear time using just one scan of the bitvector $\mathtt{intervals}$.

\item \label{exe:clusteringWithTwoKmers} With reference to \Sec{17.2.2}, describe an algorithm to create pre-clusters in which two reads are merged if they share \emph{at least two} distinct $k_2$-mers. Assume that you have $|R|\log r$ bits of main memory in addition to the space required by \Lemma{17.5}, and assume that you have an algorithm that sorts tuples in external memory as a black box. Describe how to implement additional conditions on top of your algorithm, for example that the two shared $k_2$-mers are in the same order in both reads, that they do not overlap, or that they are offset by exactly one position.

\item \label{exe:reverseComplementClustering} With reference to \Sec{17.2.2}, describe an algorithm to create pre-clusters in which two reads are merged if they share a $k_2$-mer \emph{or its reverse complement}. Note that in this case we cannot discard $k_2$-mers that occur exactly once in $R$, since they could occur twice in $R \cdot \REV{R}$. Describe a solution that takes $K+K'\log r$ bits of space in addition to the bidirectional BWT index of $R$, where $K$ is the number of distinct $k_2$-mers in $R$, and $K'$ is the number of distinct $k_2$-mers that occur at least twice in $R \cdot \REV{R}$. This algorithm should perform $k_2+1$ operations for every position of the input file. Adapt your solution to filter out reads such that all their $k_1$-mers occur less than $\tau_1$ times in $R \cdot \REV{R}$, as described in \Sec{17.2.1}. Finally, describe another solution for creating pre-clusters that uses string $R \cdot \REV{R}$ as input and that takes approximately twice the time and the space of \Lemma{17.5}.

\item Describe a way to parallelize the algorithm in \Lemma{17.5} by using samples of $\SA_R$ (see \Sec{9.2.3}).

\item \label{exe:markers} Adapt the algorithm for document counting described in \Sec{8.4.2} such that, given a reference taxonomy $\mathcal{T}$, it computes the markers of every taxon $v \in \mathcal{T}$.

\item \label{exe:markers2} Let $\MS_{S,T,\tau}$ be the following generalization of the matching statistics vector described in \Sec{11.2.3}: $\MS_{S,T,\tau}[i]$ is the longest prefix of suffix $S[i \ltdots |S|]\#$ that occurs at least $\tau$ times in $T$. Similarly, let $\SUS_{T,\tau}[i]$ be the shortest prefix of $T[i \ltdots |T|]\#$ that occurs at most $\tau$ times in $T$. Describe an algorithm that computes the markers of every taxon $v$ in a reference taxonomy $\mathcal{T}$ using the shortest unique substring vector $\SUS_{S,\tau}$, the matching statistics vector $\MS_{S,T,\tau+1}$, and a bitvector $\mathtt{flag}_{S,T,\tau}[1 \ltdots |S|]$ such that $\mathtt{flag}_{S,T,\tau}[i]=1$ if and only if $S[i \ltdots i+\MS_{S,T,1}[i]-1]$ occurs at most $\tau$ times in $T$, for every genome $T \neq S$ in the database.

\item \label{exe:upperBoundMaxRepeats} Prove that the number of $k$-submaximal repeats of a string $S$ is upper-bounded by the number of distinct $k$-mers that occur at least twice in $S$.

\item \label{exe:unionFind} With reference to \Btw{17.1}, prove that attaching the root of the smallest subtree to the root of the largest subtree guarantees $O(\log n)$ time for $\mathtt{find}$.

\item \label{exe:maxRepeatsInPreclusters} With reference to \Sec{17.2.3}, give the pseudocode of an algorithm that extracts all the maximal repeats of length at least $k_4$ from all pre-clusters, using a single enumeration of all the internal nodes of the suffix tree of $R$.

\item \label{exe:overlapGraph} With reference to \Sec{17.3.2}, describe a way to approximate $\mathcal{R} \otimes \mathcal{Q}$ that is more accurate than just computing $\mathcal{R} \odot \mathcal{Q}$. \emph{Hint.} Use the operator $\odot$ iteratively on suitable subsets of $\mathcal{R}$ and $\mathcal{Q}$. 
Then, give the pseudocode of an algorithm that, given vector $\MS_{R^i}$ for a read $R^i$, finds a set of nonoverlapping substrings of length $k$ of maximum size.

\end{enumerate}

\end{document}  