\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{\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 14. Genomics}

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

\item \label{exe:snpcalling}
Calculate the probability of an SNP given a read pileup taking into account the measurement errors.
\item\label{exe:variantannotation}
\emph{Variant annotation} is the process of assigning a function for each detected variant. For example, a 1-base deletion
inside an exon creates a frame-shift and may cause an abnormal protein product to be translated. Consider different variants
that might appear and think about why some variants can be called \emph{silent mutations}. Browse the literature to find out what \emph{nonsense mutations}, \emph{missense mutations}, and \emph{regulatory variants} are.
\item\label{exe:greedyexactcover}
A greedy algorithm to solve \Prob{14.1} is to start with empty $E'$, choose $h\in H$ with most incoming edges not in $E'$, add those unmatched edges to $E'$, and iterate the process until all $r \in R$ are incident to an edge in $E'$.
Show that this can produce a solution whose size is $O(|H|)$ times the optimal solution size.
\item \label{genomics:exe-set-cover} Consider the following algorithm for the minimum-cost set cover problem. Start with an empty $C$ and iteratively add to $C$ the most cost-effective set $H_i$, that is, the set $H_i$ maximizing the ratio between $c(H_i)$ and the number of un-covered elements of $\{r_1,\dots,r_m\}$ that $H_i$ covers. This is repeated until all elements are covered by some set in $C$. Show that this algorithm always produces a solution whose cost is $O(\log m)$ times the cost of an optimal solution.


\item Show that \Prob{14.3} 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 haploid prediction to labeled DAG of diploid ground-truth give $O(dn)$ running time, 
where $d$ is the resulting edit distance and $n$ is the maximum of the DAG size and haploid length?
\item\label{genomics:exe-HA-NP-hard}
Complete the proof of \Thm{14.3}, by proving that if $A$ and $B$ are two haplotypes obtained with $|V||E| - 2t$ bit flips from $M$, then the set $C = \{i \st A[2i-1] = A[2i] = 0\} \subseteq V$ has the property that there are $t$ edges between $C$ and $V \setminus C$. Obtain this proof by showing the following intermediary properties:
\begin{itemize}
\item $A[2i-1] = A[2i]$, for all $i \in \{1,\dots,|V|\}$;
\item $B[2i-1] = B[2i]$, for all $i \in \{1,\dots,|V|\}$;
\item $A$ is the bitwise complement of $B$.
\end{itemize}

\item\label{exe:haplotypeassembly}
Show that the algorithm given for the haplotype assembly under minimum error correction problem can be optimized to run in $O((2^K+r)s)$ time. How could you get the time complexity down to $O(2^Ks)$?

\item \label{exe:haplotypeassembly-memory} Show how the algorithm given for the haplotype assembly under minimum error correction problem can be implemented to use $O(2^K\sqrt{s})$ memory, while maintaining the same asymptotic time complexity. \emph{Hint.} Use the same idea as in \Exe{7.2}.

\item\label{exe:haplotypeassembly-error}
Let $T$ denote the maximum number of bit flips needed in any column of the matrix $M$ in an optimal solution to \Prob{14.4}. Show that the algorithm given for this problem can be modified to run in time $O((K^T+r)s)$, and even in time $O(K^Ts)$ (see also Exercise~\ref{exe:haplotypeassembly} above).

\item\label{exe:haplotypeassembly-weight}
Consider the problem of haplotype assembly under minimum error correction problem in which each cell of $M$ has also a cost of flipping, and one is looking for a partition of the rows of $M$ that is compatible with two haplotypes and minimizes the sum of the costs of all bit flips. What changes to the algorithm we presented are needed in order to solve this more general problem with the same time complexity?

\end{enumerate}

\end{document}  