\documentclass[12pt]{article}
\usepackage{fancyhdr,fancybox,amssymb,epsfig,amsmath,latexsym,bm}
\usepackage{enumerate}
\usepackage{tikz}
\usepackage[all]{xy}
\usepackage{stackrel}
\usepackage[]{hyperref}
\usetikzlibrary{arrows}
\usetikzlibrary{decorations.markings}

\tikzset{big arrow/.style={decoration={markings,mark=at position 0.6
      with {\arrow[scale=2]{>}}}, postaction={decorate}, shorten >=1pt}}

% Code to make an augmented matrix (Usage: \begin{bmatrix}[ccc|c])
\makeatletter
\renewcommand*\env@matrix[1][*\c@MaxMatrixCols c]{%
  \hskip -\arraycolsep
  \let\@ifnextchar\new@ifnextchar
  \array{#1}}
\makeatother

\topmargin=-.5in
\headsep=0.2in
\oddsidemargin=0in
\textwidth=6.7in
\textheight=9.2in
\footskip=.5in

% Change this line to \def\bold{\mathbf} for ``upright boldface.''
\def\bold{\bm}

\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}

\def\b{\mathbf{b}}

\DeclareMathOperator{\A}{A}
\DeclareMathOperator{\C}{C}
\DeclareMathOperator{\G}{G}
\DeclareMathOperator{\T}{T}
\DeclareMathOperator{\U}{U}

\DeclareMathOperator{\AU}{AU}
\DeclareMathOperator{\CG}{CG}
\DeclareMathOperator{\GU}{GU}
\DeclareMathOperator{\GC}{GC}
\DeclareMathOperator{\UG}{UG}

\def\<{\langle}
\def\>{\rangle}
\def\longto{\longrightarrow}

\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\rank}{rank}
\newcommand{\vv}[2]{\begin{bmatrix} #1 \\ #2 \end{bmatrix}}
\newcommand{\vvv}[3]{\begin{bmatrix} #1 \\ #2 \\ #3 \end{bmatrix}}

\newcommand{\ds}{\displaystyle}

\renewcommand{\footrulewidth}{1pt}
\newenvironment{proof}[1][Proof.]{\smallskip\begin{trivlist}
    \item[\hskip \labelsep {\sffamily #1}]}{\qed\end{trivlist}\bigskip}
\newenvironment{sol}[1][Solution.]{\smallskip\begin{trivlist}
    \item[\hskip \labelsep {\sffamily #1}]}{\qed\end{trivlist}\bigskip}
\newenvironment{fminipage}
{\setlength{\fboxsep}{15pt}\begin{Sbox}\begin{minipage}}
{\end{minipage}\end{Sbox}\fbox{\TheSbox}}
\newcommand{\qed}{\hfill \ensuremath{\Box}}
\newcommand{\disp}{\displaystyle}


\pagestyle{fancy} \lhead{{\sf Homework 9 $|$ Due April 24 (Friday)
}} \rhead{\thepage} \cfoot{{\sf Math 4500 $|$ Mathematical Modeling
    $|$ Spring 2015 $|$ M.~Macauley}}


\begin{document}

$\;$

\noindent \emph{Read}: Algebraic and Discrete Mathematical Methods for
Modern Biology, Chapter 13 (pdf is on Blackboard): \emph{RNA Secondary
  Structures: Combinatorial Models and Folding Algorithms}, by Q.~He,
M.~Macauley, and R.~Davies. Pages 321--345. \\


\begin{enumerate}

\item Consider the following fold of the RNA sequence {\small
  GGGACCUUCCCCCCAAGGGGGGG}:
  \begin{center}
    \begin{tikzpicture}[scale=.4, shorten >= -2pt, shorten <= -2pt]
      \begin{scope}[shift={(0,0)}]
        \node (1) at (3,2.25) {$\G$};
        \node (2) at (4,2) {$\G$};
        \node (3) at (5,2) {$\G$};
        \node (4) at (6,2) {$\A$};
        \node (5) at (7,1.75) {$\C$};
        \node (6) at (7.75,1) {$\C$};
        \node (7) at (7,.25) {$\U$};
        \node (8) at (6,0) {$\U$};
        \node (9) at (5,0) {$\C$};
        \node (10) at (4,0) {$\C$};
        \node (11) at (3,0) {$\C$};
        \node (12) at (2,0) {$\C$};
        \node (13) at (1,0) {$\C$};
        \node (14) at (0,-.25) {$\C$};
        \node (15) at (-.75,-1) {$\A$};
        \node (16) at (0,-2) {$\A$};
        \node (17) at (1,-2) {$\G$};
        \node (18) at (2,-2) {$\G$};
        \node (19) at (3,-2) {$\G$};
        \node (20) at (4,-2) {$\G$};
        \node (21) at (5,-2) {$\G$};
        \node (22) at (6,-2.25) {$\G$};
        \node (23) at (7,-2.5) {$\G$};
        \draw (17) to (13);
        \draw (18) to (12);
        \draw (19) to (11);
        \draw (8) to (4);
        \draw (9) to (3);
        \draw (10) to (2);
        \node at (.75,3) {\footnotesize $5'$-end};
        \node at (9,-1.75) {\footnotesize $3'$-end};
      \end{scope}  
    \end{tikzpicture}
  \end{center}
  %%
  \begin{enumerate}[(i)]
    \item Draw the corresponding arc diagram.
    \item Write out this secondary structure in point-bracket notation.
    \item Draw the corresponding Motskin path. \\
    \end{enumerate}



\item Consider the following fold of the same RNA sequence from the
  previous problem:
  \begin{center}
    \begin{tikzpicture}[scale=.4, shorten >= -2pt, shorten <= -2pt]
      \begin{scope}[shift={(0,0)},shorten >= -3.5pt, shorten <= -3.5pt]
        \node (-2) at (0,2.25) {$\G$};
        \node (-1) at (1,2) {$\G$};
        \node (0) at (2,2) {$\G$};
        \node (1) at (3,2) {$\G$};
        \node (2) at (4,2) {$\G$};
        \node (3) at (5,2) {$\G$};
        \node (4) at (6,2) {$\A$};
        \node (5) at (7,1.75) {$\C$};
        \node (6) at (7.75,1) {$\C$};
        \node (7) at (7,.25) {$\U$};
        \node (8) at (6,0) {$\U$};
        \node (9) at (5,0) {$\C$};
        \node (10) at (4,0) {$\C$};
        \node (11) at (3,0) {$\C$};
        \node (12) at (2,0) {$\C$};
        \node (13) at (1,0) {$\C$};
        \node (14) at (0,-.25) {$\C$};
        \node (15) at (-.75,-1) {$\A$};
        \node (16) at (0,-2) {$\A$};
        \node (17) at (1,-2) {$\G$};
        \node (18) at (2,-2) {$\G$};
        \node (19) at (3,-2) {$\G$};
        \node (20) at (4,-2) {$\G$};
        \node (21) at (5,-2) {$\G$};
        \node (22) at (6,-2) {$\G$};
        \node (23) at (7,-1.75) {$\G$};
        \node (24) at (8,-1.5) {$\G$};
        \node (25) at (8.75,-.75) {$\G$};
        \draw (17) to (13);
        \draw (18) to (12);
        \draw (19) to (11);
        \draw (8) to (4);
        \draw (9) to (3);
        \draw (10) to (2);
        \draw (24) to (7);
        \draw (25) to (6);
        \node at (1.5,3.5) {\footnotesize $5'$-end};
        \node at (11,-1.75) {\footnotesize $3'$-end};
      \end{scope}  
    \end{tikzpicture}
  \end{center}
  
  \begin{enumerate}[(i)]
  \item Draw the corresponding arc diagram. What is the
    smallest $k$ for which this is $k$-noncrossing .
  \item What if the first $\G$ bonds with the $\C$ ``directly
    below'' it (vertex 17). Does this change the $k$ from the previous part?
  \item Draw a picture of a folded RNA strand (like the one above)
    that is $4$-noncrossing but not $3$-noncrossing. \\
  \end{enumerate}
  

  
\item Consider the RNA sequence $\b=\G\G\G\A\C\C\U\U\C\C$. Find all
  possible ways that it can fold into a secondary structure $S$,
  without leaving any ``allowed'' unpaired bases. Draw the arc diagram
  and a ``realistic sketch'' of the folded RNA strand. Compute the
  energy score $E(\b,S)$ of each.
  
  \newpage
  
  
\item Use dynamic programming to fill out the remaining table to
  find the optimal fold of the RNA sequence
  $\b=\G\G\G\A\C\C\U\U\C\C$. Then, do the trace-back step to
  recover a structure that achieves this maximum energy score.
  %%
  \begin{center}
    \begin{tikzpicture}[scale=.8]
      \begin{scope}[shift={(0,0)},scale=.6,shorten >= 0, shorten <= 0]     
        \foreach \x in {0,...,10}
                 {\draw[very thin] (\x,0)--(\x,10);}
        \foreach \y in {0,...,10}
                 {\draw[very thin] (0,\y)--(10,\y);}
                 %%
      \foreach \x in {0,...,8}
      {\draw[lightgray,fill=lightgray,opacity=.5] (\x,0) rectangle (\x+1,9-\x);}
      %%
      \foreach \x in {0,...,9}
      {\draw[very thick] (\x,10-\x-1)--(\x,10-\x);}
      \foreach \y in {0,...,9}
      {\draw[very thick] (10-\y-1,\y)--(10-\y,\y);}
      %%
      \foreach \x in {0,...,6}
      {\draw[very thick] (\x+4,10-\x-1)--(\x+4,10-\x);}
      \foreach \y in {0,...,6}
      {\draw[very thick] (10-\y-1,\y+4)--(10-\y,\y+4);}
      %%
      \draw (0,0) rectangle (10,10);
      %%
      \foreach \i in {0,...,9}
               {\node at (\i+.5,10-\i-.5) {\small $0$};}
      \foreach \i in {0,...,8}
               {\node at (\i+1.5,10-\i-.5) {\small $0$};}
      \foreach \i in {0,...,7}
               {\node at (\i+2.5,10-\i-.5) {\small $0$};}
      \foreach \i in {0,...,6}
               {\node at (\i+3.5,10-\i-.5) {\small $0$};}
      %%
      \node at (.5,10.5) {\small G};
      \node at (1.5,10.5) {\small G};
      \node at (2.5,10.5) {\small G};
      \node at (3.5,10.5) {\small A};      
      \node at (4.5,10.5) {\small C};
      \node at (5.5,10.5) {\small C};
      \node at (6.5,10.5) {\small U};
      \node at (7.5,10.5) {\small U};
      \node at (8.5,10.5) {\small C};
      \node at (9.5,10.5) {\small C};
      %%
      \node at (-.5,9.5) {\small G};
      \node at (-.5,8.5) {\small G};
      \node at (-.5,7.5) {\small G};
      \node at (-.5,6.5) {\small A};
      \node at (-.5,5.5) {\small C};
      \node at (-.5,4.5) {\small C};
      \node at (-.5,3.5) {\small U};
      \node at (-.5,2.5) {\small U};
      \node at (-.5,1.5) {\small C};
      \node at (-.5,.5) {\small C};
      %%
      \end{scope}
    \end{tikzpicture}
  \end{center} \smallskip
  

\item The \emph{Knudsen-Hein grammar} is a stochastic context free grammar
  (SCFG) defined by the following production rules:
  \begin{align*}
    &S\longto LS\;(p_1)\,|\,L\;(q_1) \\
    &L\longto dFd'\;(p_2)\,|\,s\;(q_2) \\
    &F\longto dFd'\;(p_3)\,|\,LS\;(q_3)
  \end{align*}
  Construct a derivation the hairpin loop $ssddsssd'd'ss$, and compute
  its probability.
  
\end{enumerate}


\end{document}


