\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{\Thm}[1]{Theorem~{#1}}
  \newcommand{\Sec}[1]{Section~{#1}}   
  \newcommand{\Prob}[1]{Problem~{#1}}  
  \newcommand{\Exe}[1]{Exercise~{#1}}  
  \newcommand{\Algo}[1]{Algorithm~{#1}}
  \newcommand{\ltdots}{..}  
  \newcommand{\st}{\:|\:}  
  \newcommand{\Eq}[1]{Equation~({#1})} 
  \newcommand{\Chap}[1]{Chapter~{#1}}
  \newcommand{\Ex}[1]{Example~{#1}}
  \renewcommand{\pageref}[1]{{#1}}
%%%%%%%%%% 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 6. Alignments}

\begin{enumerate}[label=6.\arabic*]
\item \label{exe:editDistanceIsMetric} Show that the edit distance is a \emph{metric}, namely that it satisfies:
\begin{enumerate}
\renewcommand{\theenumi}{(\roman{enumi})}
\item $D(A,B)\geq 0$,
\item $D(A,B) = 0$, if and only if $A = B$,
\item $D(A,B) = D(B,A)$,
\item $D(A,B) \leq D(A,C) + D(C,B)$.
\end{enumerate}
\item \label{exe:dpcolumns}
Modify \Algo{6.1} on page \pageref{74} to use only one vector of length $m+1$ in the computation.
\item \label{exe:detour}
The shortest-detour algorithm is able to compute the dynamic programming matrix only partially. However, just
allocating space for the rectangular matrix of size $m\times n$ requires $O(mn)$ time. Explain how one can allocate just the cells that are to be computed. Can you do the evaluation in $O(d)$ space, where $d=D(A,B)$?
\item \label{exe:myerssearch}Modify Myers' bitparallel algorithm to solve the $k$-errors problem on short patterns.
\item Optimize Myers' bitparallel algorithm to use fewer basic operations.
\item Write a program to automatically verify each row in the truth tables in the lemmas proving the correctness of
Myers' bitparallel algorithm.
\item Write a program to automatically discover the four ``easy'' operations (those of the four first lemmas) in Myers' bitparallel algorithm.
\item \label{exe:myerstrace}
Describe how to traceback an optimal alignment with Myers' bitparallel algorithm.
\item \label{exe:myerstrace2}
Consider \Exe{exe:hirschberg}. Show that the same technique can be combined with Myers' bitparallel algorithm to obtain linear space traceback together with the bitparallel speed-up. \emph{Hint.} Compute the algorithm also for the reverse of the strings. Then you can deduce $j_\mathtt{mid}$ from forward and reverse computations. See \Sec{7.4} for an analogous computation.   
\item\label{exe:fourrussianseditdistance}
The four Russians technique we studied in \Sec{3.2} leads to an alternative way to speed up edit distance computation. The idea is to encode each column as in Myers' bitparallel algorithm with two bitvectors $R^+_j$ and $R^-_j$ and partition these bitvectors to blocks of length $b$. Each such pair of bitvector blocks representing an \emph{output encoding} of a block $d_{i-b+1 \ltdots i,j}$ in the original dynamic programming matrix is uniquely defined by the \emph{input parameters} $A_{i-b+1 \ltdots i}$, $b_j$, $d_{i-b,j-1}$, and $d_{i-b,j}$ and the bitvector blocks representing the block $d_{i-b+1 \ltdots i,j-1}$. Develop the details and choose $b$ so that one can afford to precompute a table storing for all possible input parameters the output encoding of a block. Show that this leads to an $O(mn / \log_\sigma n)$ time algorithm for computing the Levenshtein edit distance.
\item \label{exe:did_lcs} Prove \Thm{6.10}.
\item \label{exe:sparseset}
Show that the set $M=M(A,B)=\{(i,j)\st a_i=b_j\}$ which is needed for sparse dynamic programming \textsf{LCS} computation, sorted in reverse column-order, can be constructed in
$O(\sigma+|A|+|B|+|M|)$ time on a constant alphabet and in $O((|A|+|B|)\log |A| + |M|)$ time on an ordered alphabet.
Observe also that this construction can be run in parallel with \Algo{6.3} to improve the space requirement of
\Thm{6.12} to $O(m)$.
\item The sparse dynamic algorithm for distance $D_\mathtt{id}(A,B)$ can be simplified significantly if derived directly for computing
$|\mathsf{LCS}(A,B)|$. Derive this algorithm. \emph{Hint.} The search tree can be modified to answer range maximum queries instead of range minimum queries (see \Sec{6.4.5}).
\item Give a pseudocode for local alignment using space $O(m)$.
\item \label{exe:local1}
Give a pseudocode for tracing an optimal path for the maximum-scoring local alignment, using space quadratic in the alignment length.
\item \label{exe:hirschberg}
Develop an algorithm for tracing an optimal path for the maximum-scoring local alignment, using space linear in the alignment length.
\emph{Hint.} Let $[i' \ltdots i] \times [j' \ltdots j]$ define the rectangle containing a local alignment. Assume you know $j_\mathtt{mid}$ for row $(i-i')/2$ where the
optimal alignment goes through. Then you can independently recursively consider rectangles defined by $[i' \ltdots (i-i')/2] \times [j' \ltdots j_\mathtt{mid}]$ and
$[(i-i')/2] \times [j_\mathtt{mid} \ltdots j]$. To find $j_\mathtt{mid}$ you may, for example, store, along with the optimum value, the index $j$ where
that path crosses the middle row.
\item 
Prove the correctness of Algorithms~{6.5} and {6.6}.
\item The sequencing technology \texttt{SOLiD}$^\textrm{TM}$ from Applied Biosystems produces short reads of DNA in \emph{color-space} with a two-base encoding defined by the following matrix (row\;=\;first base, column\;=\;second base):
\begin{center}
\begin{tabular}{l}
\verb+  A C G T+\\
\verb+A 0 1 2 3+\\
\verb+C 1 0 3 2+\\
\verb+G 2 3 0 1+\\
\verb+T 3 2 1 0+\\
\end{tabular}
\end{center}
For example, \texttt{T012023211202102} equals \texttt{TTGAAGCTGTCCTGGA} (the first base is always given).
Modify the overlap alignment algorithm to work properly in the case where one of the sequences is a \texttt{SOLiD} read and the other is a normal sequence.

\item \label{exe:KLdivergence}
Show that the relative entropy used in \Eq{6.15} is non-negative.
\item Give a pseudocode for prokaryote gene alignment.
\item Give a pseudocode for eukaryote gene alignment with affine gaps.
\item Give a pseudocode for the $O(mn\cdot\mathtt{maxin})$ time algorithm for eukaryote gene alignment with limited introns.
\item Modify the recurrence for gene alignment with limited introns so that the alignment must start with a start codon, end with a stop codon, and contain \texttt{GT} and
\texttt{AG} dinucleotides at intron boundaries. Can you still solve the problem in $O(mn\cdot\mathtt{maxin})$ time? Since there are rare exceptions when dinucleotides at intron boundaries are something else, how can you make the requirement softer?
\item \label{exe:lcsreduction}
Give an alternative proof for the NP-hardness of the longest common subsequence problem on multiple sequences, by using a reduction from the vertex cover problem. \emph{Hint.} From a graph $G=(V=\{1,\ldots,|V|\},E)$ and integer $k$, construct $|E|+1$ sequences having LCS of length $|V|-k$ if and only if there is vertex cover of size $k$ in $G$. Recall that vertex cover $V'$ is a subset of $V$ such that all edges in $E$ are incident to at least one vertex in $V$.
\item Develop a sparse dynamic programming solution for computing the longest common subsequence of multiple sequences. What is the expected size of the match set on random sequences from an alphabet of size $\sigma$? \emph{Hint.} The search tree can be extended to higher-dimensional range queries using recursion (see the range trees from the computational geometry literature).
\item Reformulate the DAG-path alignment problem (\Prob{6.19} on page \pageref{105}) as a local alignment problem. Show that the Smith-Waterman approach extends to this, but is there a polynomial algorithm if one wishes to report alignments with negative score? Can the affine gap cost alignment be extended to the DAG-path alignment? Can one obtain a polynomial time algorithm for that case?
\item\label{exe:codonDAG}
Show how to use DAG-path alignment to align a protein sequence to DNA. \emph{Hint.} Represent the protein sequence as a \emph{codon-DAG} replacing each amino acid by a sub-DAG representing its codons. 
\item Consider a DAG with predicted exons as vertices and arcs formed by pairs of exons predicted to appear inside a transcript: this is the \emph{splicing graph} considered in \Chap{15}. 
Detail how DAG-path alignment on splicing graph and the codon-DAG of previous assignment solves eukaryote gene alignment problem.
\label{exe:cyclic-saving-space}
Show that the array $S[0..m]$ is not required to obtain the $O(|E|m)$ time approximate matching on graphs, so that the algorithm uses only $O(|V|)$ space. 
\item
\label{exe:cyclic-traceback}
Show how to traceback an optimal alignment using $O(\sqrt{m}|V|)$ space after conducting the $O(|E|m)$ time approximate matching on graphs. 
\item
\label{exe:jumpingalignment}
Reformulate jumping alignment so that $A$ is just aligned to the sequences forming the multiple alignment and not to the existing gaps inside the multiple alignment, as in \Ex{6.22}. Show that the reformulated problem can be solved as fast as the original one.

\section*{Additional exercises not in the book}

\item Compute the global alignment scores $s_{ij}$ and especially $s_{mn} = S(A,B)$ for $A=$\texttt{ACCGATG} and $B=$\texttt{ACGGCTA} using indel penalty $-d$, where $d=1$, and the 
substitution matrix:
\begin{center}
\begin{tabular}{c|rrrr}
$s(a,b)$ & \texttt{A} & \texttt{C} & \texttt{G} & \texttt{T} \\
\hline
\texttt{A} & $1$ & $-1$ & $-0.5$ & $-1$ \\
\texttt{C} & $-1$ & $1$ & $-1$ & $-0.5$ \\
\texttt{G} & $-0.5$ & $-1$ & $1$ & $-1$ \\
\texttt{T} & $-1$ & $-0.5$ & $-1$ & $1$ \\
\end{tabular}
\end{center}
Trace an optimal alignment. 

Rather than simulating on paper, you can also opt to implement. You may use the edit distance code at 
\begin{center}
\url{http://www.genome-scale.info/implementations/dp2tikz.py}
\end{center}
as a basis. The resulting TikZ-code can be included in a \LaTeX document to visualize the result:
\begin{verbatim}
\documentclass{article}
\usepackage{tikz}

\begin{document}

\begin{tikzpicture}[scale=6.0]
\input{dp.tikz}
\end{tikzpicture}

\end{document}
\end{verbatim}

\item 
Compute the local alignment scores $l_{i,j}$ for the same example as above. Trace an optimal local alignment.

\item

In the affine gap model, the gaps are defined as runs of indels. Consider the alternative definition of gaps as runs of insertions or runs of deletions, briefly discussed in the main text. 
Derive the details of the basic recurrence to solve this variant.

\item 

Consider the setting above. Modify Gotoh's algorithm to handle the runs of insertions and runs of deletions separately. \emph{Hint.} You will need three tables.

\item 

Consider the setting above. Modify the invariant-based algorithm to handle runs of insertions and runs of deletions separately.

\item 

Write a program (e.g.~in Python) to read the $k$-th order distribution of a given DNA sequence (for given $k$), and 
to generate a new sequence of the same length simulating the output of this \emph{$k$-th order Markov chain}.

\item 

\texttt{BLAST} is a heuristic aligner that makes local alignment feasible in large sequence databases. The following describes the main principles of \texttt{BLAST} with some simplifications. The database is indexed using a \emph{$k$-mer index}, where each substring $W$ of length $k$ is associated with a 
list of pointers to the occurrence of $W$ in the database. The lists of pointers of $k$-mers that are within 
Hamming distance $1$ from some substring of a \emph{query} sequence give the \emph{candidate occurrences}. Dynamic programming is applied to extend candidate occurrences and to join nearby candidates, to form the final alignment results.

Show that \texttt{BLAST} is a \emph{lossy filter}, meaning that it might miss some optimal local alignments.

\item 

Implement the $k$-mer index, e.g.~by modifying your code for the $k$-th order Markov chain assignment above. The basic version is enough 
without considering how to compress the lists of occurrences (see Chapter 8. Classical indexes for more details about $k$-mer indexes). 

\item 

Implement \texttt{BLAST}-like search on top of the $k$-mer index of the previous assignment to report candidate occurrences. You can ignore the dynamic programming part.
   
\item 

While there are many alternatives to \texttt{BLAST} that obtain better filtering accuracy, speed, and space, the popularity of \texttt{BLAST} is mostly explained by its handling of statistical significance of the found alignments. Rather than ranking alignments directly by maximum score, it takes into account the probability of finding equally good alignments by chance. Get familiar with this process by reading this tutorial \url{http://www.ncbi.nlm.nih.gov/BLAST/tutorial/}. Be ready to explain the main concepts. 

\end{enumerate}

\end{document}  
