\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 16. Transcriptomics}

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

\item Work out the calculations for deriving the system of equations ({16.3}), using the formula %
\label{exe:trans-partial-deriv}

\begin{align*}
\frac{\partial \left(w_i - \alpha_{i,1}e_1 - \alpha_{i,2}e_2 - \dots - \alpha_{i,k}e_k\right)^2}{\partial e_j} =& 2\left(w_i - \alpha_{i,1}e_1 - \alpha_{i,2}e_2 - \dots - \alpha_{i,k}e_k\right) \cdot\\
& \cdot \frac{\partial \left(w_i - \alpha_{i,1}e_1 - \alpha_{i,2}e_2 - \dots - \alpha_{i,k}e_k\right)}{\partial e_j} \\
= & - 2\alpha_{i,j}\left(w_i - \alpha_{i,1}e_1 - \alpha_{i,2}e_2 - \dots - \alpha_{i,k}e_k\right).
\end{align*}

\item \label{ex:transcriptomics-exon-detection} Formalize the exon detection phase described using HMMs (recall \Btw{14.1} and \Chap{7}).

\item \label{exe:trans-LR-no-weights} Consider the following version of \Prob{16.3} in which there are no costs associated with the arcs for the DAG and in which we need to cover only a given collection of paths. Given a DAG $G = (V,E)$, a set $S \subseteq V$ of possible start vertices, a set $T \subseteq V$ of possible end vertices, and a collection $\mathcal{P}^{in} = \{P_1^{in},\dots,P_t^{in}\}$ of directed paths in $G$, find the minimum number $k$ of paths $P_1^{sol},\dots,P_k^{sol}$ such that
\begin{itemize}
\item every $P_i^{sol}$ starts in some vertex of $S$ and ends in some vertex of $T$,
\item every path $P^{in} \in \mathcal{P}^{in}$ is entirely contained in some $P^{sol}_i$.
\end{itemize}
Assume also that no $P_i^{in}$ is entirely included in another $P_j^{in}$ (otherwise $P_i^{in}$ can be removed from $\mathcal{P}^{in}$). Show that this problem can be solved by a reduction to a minimum-cost flow problem (without having to iteratively merge paths with longest suffix-prefix overlaps). 
What features does the resulting flow network have? Can you apply a specialized minimum-cost flow algorithm with a better complexity for such a network?

\item Given an input for the problem of transcript assembly with paired-end reads, show that we can decide in polynomial time whether it admits a solution with two paths, and if so, find the two solution paths.


\item Using the reduction in the proof of \Thm{16.4}, conclude that there exists for no $\varepsilon>0$ an algorithm returning a solution with $k$ paths for the problem of transcript assembly with paired-end reads, where $k$ is greater than the optimal number of paths by a multiplicative factor $\frac{4}{3} -\varepsilon$.

\item Argue that the reduction of \Prob{16.5} to a network flow problem with convex costs  is correct.
\label{exe:TAEE}

\item Show that the function $g$ defined in ({16.7}) is a flow on $G$, namely that
\begin{itemize}
\item for all $y \in V(G) \setminus (S \cup T)$, $\sum_{x \in N^-(y)}g(x,y) = \sum_{x \in N^+(y)}g(y,x)$;
\item $\sum_{s \in S}\sum_{y \in N^+(s)}g(s,y) = \sum_{t \in T}\sum_{x \in N^-(t)}g(x,t)$.
\end{itemize}
\label{transcriptomics:exe-flow-g}

\item Explain what changes need to be made to the flow network $N$, if in \Prob{16.6} we also get in the input a coefficient $\alpha(x,y)$ for every arc $(x,y)$ of $G$, and we are asked to find the paths and their expression levels which minimize
\[\sum_{(x,y) \in E}\alpha(x,y)\left|w(x,y) - \sum_{j \wt (x,y) \in P_j}e_j\right|.\]
\label{transcriptomics:exe:coeff}

\item Consider a variant of \Prob{16.6} in which we want to minimize the absolute differences between the total coverage (instead of the average coverage) of an exon and its predicted coverage. Explain how this problem can be reduced to the one in Exercise~\ref{transcriptomics:exe:coeff} above, for an appropriately chosen function $\alpha$.

\item Adapt the reduction to a minimum-cost flow problem from \Sec{16.3} to solve the following problem. Given a DAG $G = (V,E)$, a set $S \subseteq V$ of possible start vertices, a set $T \subseteq V$ of possible end vertices, and a weight function $w : E \rightarrow \mathbb{Q}_{+}$, find a collection of paths $P_1,\dots,P_k$ in $G$, and their corresponding expression levels $e_1,\dots,e_k$, such that
\begin{itemize}
\item every $P_i$ starts in some vertex of $S$ and ends in some vertex of $T$,
\end{itemize}
and the following function is minimized:
\begin{equation*}
\sum_{(x,y) \in E}\left|w(x,y) - \sum_{j \wt (x,y) \in P_j}e_j\right| + \lambda\sum_{i=1}^k e_i.
\end{equation*}

What can you say about the problem in which we use the squared difference, instead of the absolute value of the difference?
\label{exe:FlipFlop}

\item Show that the following problem is NP-hard, for any fixed $\beta \geq 1$. Given a DAG $G = (V,E)$, a set $S \subseteq V$ of possible start vertices, a set $T \subseteq V$ of possible end vertices, a weight function $w : E \rightarrow \mathbb{Q}_{+}$, and an integer $k$, find a collection of paths $P_1,\dots,P_k$ in $G$, and their corresponding expression levels $e_1,\dots,e_k$, such that
\begin{itemize}
\item every $P_i$ starts in some vertex of $S$ and ends in some vertex of $T$,
\end{itemize}
and the following function is minimized:
\begin{equation*}
\sum_{(x,y) \in E}\left|w(x,y) - \sum_{j \wt (x,y) \in P_j}e_j\right|^\beta.
\end{equation*}
\label{exe:WABI-NP-complete}
\emph{Hint.} Use \Thm{5.3} or its proof.

\item Show that, given $k \geq 1$ and given $e_1,\dots,e_k$, the following problem is solvable in time $O(n^{2k+2})$. Given a DAG $G = (V,E)$, a set $S \subseteq V$ of possible start vertices, a set $T \subseteq V$ of possible end vertices, weight function $w : E \rightarrow \mathbb{Q}_{+}$, and an integer $k$, find a collection of paths $P_1,\dots,P_k$ in $G$, such that:
\begin{itemize}
\item every $P_i$ starts in some vertex of $S$, and ends in some vertex of $T$,
\end{itemize}
and the following function is minimized
\begin{equation}
\label{eq:WABI-DP}
\sum_{(x,y) \in E}\left|w(x,y) - \sum_{j \wt (x,y) \in P_j}e_j\right|.
\end{equation}
\emph{Hint.} Use dynamic programming and consider the optimal $k$ paths ending in every tuple of $k$ vertices.
\label{exe:WABI-DP}

\item Show that, given an error function $\delta : \mathbb{Q}_+ \times \mathbb{Q}_+ \rightarrow \mathbb{Q}_+$, the problem considered in Exercise~\ref{exe:WABI-DP} in which the objective function the above equation (\ref{eq:WABI-DP}) is replaced with
\begin{equation}
\sum_{(x,y) \in E}\delta\left(w(x,y),\sum_{j \wt (x,y) \in P_j}e_j\right)
\label{}
\end{equation}
is solvable with the same time complexity $O(n^{2k+2})$ (assuming $\delta$ is computable in time $O(1)$).
\label{exe:WABI-DP*}

\item Consider the following problem of \emph{transcript assembly and expression estimation with outliers}, in which the weights of the arcs not belonging to any solution path do not contribute in the objective function. Given $k \geq 1$, a DAG $G = (V,E)$, a set $S \subseteq V$ of possible start vertices, a set $T \subseteq V$ of possible end vertices, a weight function $w : E \rightarrow \mathbb{Q}_{+}$, and an integer $k$, find a collection of paths $P_1,\dots,P_k$ in $G$, such that
\begin{itemize}
\item every $P_i$ starts in some vertex of $S$ and ends in some vertex of $T$,
\end{itemize}
and the following function is minimized:
\begin{equation*}
\sum_{(x,y) : \text{ exists } P_i \text{ with } (x,y) \in P_i}\left|w(x,y) - \sum_{j \wt (x,y) \in P_j}e_j\right|.
\end{equation*}
Show that this problem is NP-hard. \emph{Hint.} Use \Thm{5.3} or its proof.
\label{exe:WABI-DP-OUTLIER}

\item Reduce the problem of transcript assembly and expression estimation with outliers from Exercise~\ref{exe:WABI-DP-OUTLIER} to the generalized problem from Exercise~\ref{exe:WABI-DP*}, by showing an appropriate error function $\delta$.

\item \label{exe:chaining_caseaenough}
Prove that the co-linear chaining algorithm works correctly even when there are tuples containing other tuples in $T$ or in $R$, that is,
tuples of type $(x,y,c,d)$ and $(x',y',c',d')$ such that either $x<x'\leq y'<y$ or $c<c'\leq d'<d$ (or both).
\item \label{exe:transcript-co-linear-variants} Modify the co-linear chaining algorithm to solve the following variations of the ordered coverage problem.
\begin{itemize}
\item[a)] Find the maximum ordered coverage of $R$ such that all the tuples involved in the coverage must overlap in $R$.
\item[b)] Find the maximum ordered coverage of $R$ such that the distance in $R$ between two consecutive tuples 
involved in the coverage is at most a given threshold value $\alpha$. 
\item[c)] Find the maximum ordered coverage of $R$ such that the distance in $T$ between two consecutive tuples 
involved in the coverage is at most a given threshold value $\beta$. 
\end{itemize} 

\item Co-linear chaining gives a rough alignment between the transcript and the genome as a list of subregion correspondences. Consider how this rough alignment can be fine-grained into a sequence level alignment. 


\end{enumerate}

\end{document}  