%!TEX root = ../main.tex

\chapter{FFTbor2D Appendix}
\label{ch:ffttwoapp}

\lhead{FFTbor\twoD Appendix}

\section{Full recursions for \texorpdfstring{\emZ{i,j}}{}
for the Turner energy model}
\label{sec:ffttwo:turner}

To compute $\emZ{} = \emZ{1,n}$ given input structures \strAB,
we use the recursions

\begin{align}
\label{eq:ffttwoapp:zx}
\emZ{i,j} = \emZ{i,j-1} \cdot x^{\ab{0}} +
\sum_{\mathclap{\substack{(s_k,s_j) \in \bpSet, \\ i \leq k < j}}}\enspace
\Big( \emZ{i,k-1} \cdot \emZB{k,j} \cdot \boltzE{E_d} \cdot
x^{\ab{1}} \Big),
\end{align}

where
$\alpha_0 = 1$ if $j$ is base paired in $\strA_{[i,j]}$ and $0$ otherwise,
$\beta_0 = 1$ if $j$ is base paired in $\strB_{[i,j]}$ and $0$ otherwise,
$\alpha_1 = \dBP{\strA_{[i,j]}}{\strA_{[i,k-1]} \cup \strA_{[k,j]}}$,
$\beta_1 = \dBP{\strB_{[i,j]}}{\strB_{[i,k-1]} \cup \strB_{[k,j]}}$,
and $E_d$ is the energy contribution due to dangling ends (energy
contributions from single bases stacking on adjacent base pairs) and
closing AU base pairs (since a non GC base pair closing a stem has a
destabilizing effect).  The sum is taken over all possible
base pairs $(k,j)$ with $i \leq k < j$.

We compute \emZB{} using the recursion

\begin{align}
\label{eq:ffttwoapp:zbx}
\begin{split}
\emZB{i,j} &= \boltzE{EH(i,j)} \cdot x^{\ab{2}} \\
&+ \sum_{\mathclap{\substack{(s_k,s_l) \in \bpSet, \\ i < k < l < j }}}\enspace
\emZB{k,l} \cdot \boltzE{EI(i,j,k,l)} \cdot x^{\ab{3}} \\
&+ \sum_{\mathclap{\substack{(s_k,s_l) \in \bpSet, \\ i < k < l < j }}}\enspace
\Big( \emZM{i+1,k-1} \cdot \emZB{k,l} \cdot \boltzE{(a+b+c(j-l-1))}
\cdot x^{\ab{4}} \Big)
\end{split}
\end{align}

where
$EH(i,j)$ is the energy of the hairpin loop with closing base pair $(i,j)$,
$\alpha_2 = \dBP{\strA_{[i,j]}}{\{(i,j)\}}$,
$\beta_2 = \dBP{\strB_{[i,j]}}{\{(i,j)\}}$,
$EI(i,j,k,l)$ is the energy of the stack, bulge or
interior loop with the closing base pair $(i,j)$ and the interior
base pair $(k,l)$,
$\alpha_3 = \dBP{\strA_{[i,j]}}{\strA_{[k,l]} \cup \{(i,j)\}}$,
$\beta_3 = \dBP{\strB_{[i,j]}}{\strB_{[k,l]} \cup \{(i,j)\}}$,
$\alpha_4 = \dBP{\strA_{[i,j]}}{\strA_{[i+1,k-1]} \cup
\strA_{[k,l]} \cup\{(i,j)\}}$, and
$\beta_4 = \dBP{\strB_{[i,j]}}{\strB_{[i+1,k-1]} \cup
\strB_{[k,l]} \cup\{(i,j)\}}$.
The first term in the
recursion takes care of the case where $(i,j)$ is the only base pair
in $[i,j]$, i.e. $(i,j)$ closes a hairpin loop. The second term
handles the case where there is an interior loop (or a bulge or a
stack) closed by $(i,j)$ and $(k,l)$. The third term takes care of
all the structures where $(i,j)$ closes a multiloop. To reduce
complexity of the algorithm, the interior and bulge loop size can be
limited to a maximum size of $L$ (taken by default to be $30$),
by requiring that $l>j-L$ in the above recursion.

The final recursion, for computing \emZM{}, is

\begin{align}
\label{eq:ffttwoapp:zmx}
\begin{split}
\emZM{i,j} &= \emZM{i,j-1} \cdot \boltzE{c} \cdot x^{\ab{0}} \\
&+ \sum_{\mathclap{\substack{(s_k,s_j) \in \bpSet, \\ i \leq k < j }}}\enspace
\Big( \emZB{k,j} \cdot \boltzE{(b+c(k-i))} \cdot x^{\ab{5}} \\
&+ \emZM{i,k-1} \cdot \emZB{k,j} \cdot \boltzE{b} \cdot x^{\ab{6}} \Big)
\end{split}
\end{align}

where
$\alpha_5 = \dBP{\strA_{[i,j]}}{\strA_{[k,j]}}$,
$\beta_5 = \dBP{\strB_{[i,j]}}{\strB_{[k,j]}}$,
$\alpha_6 =\dBP{\strA_{[i,j]}}{\strA_{[i,k-1]} \cup \strA_{[k,j]}}$, and
$\beta_6 =\dBP{\strB_{[i,j]}}{\strB_{[i,k-1]} \cup \strB_{[k,j]}}$.
Note that since $\emZM{i,j}$ computes the partition function
contribution under the assumption that $[i,j]$ is part of a
multiloop, there will be exactly one stem-loop structure in this
region (the \emZB{} term) or
more than one (the \emZM{}--\emZB{} term).
Justification of recursions (\ref{eq:ffttwoapp:zx}),
(\ref{eq:ffttwoapp:zbx}), and
(\ref{eq:ffttwoapp:zmx})
follow by induction, as in the proof of Theorem \ref{thm:ffttwo:recursions}.

\section{Proof for Theorem \ref{thm:ffttwo:recursions}}
\label{sec:ffttwo:recursions}

\begin{proof}
Recall that if $F$ is an arbitrary
polynomial [resp. analytic] function, then $[x^{rn+s}]F(x)$
denotes the coefficient of monomial $x^{rn+s}$ in the
Taylor expansion of $F(x)$. For instance, in
\eqnref{ffttwo:pOfX}, $[x^{rn+s}]p(x) = p_{rn+s}$, and in
\eqnref{ffttwo:zOfX}, $[x^{rn+s}]\fullZx = z_{rn+s}$.

By definition, it is clear that $\emZ{i,j}=1$ if $i \leq j \leq i + \theta$,
where we recall that $\theta = 3$ is the minimum number of unpaired bases in
a hairpin loop. For $j > i + \theta$, we have

\begin{align}
\begin{split}
[x^{rn+s}] \emZ{i,j} &= z_{rn+s}(i,j) = \bfZ{rn+s}{i,j} \\
&= \bfZ{(r-\alpha_0)n+(s-\beta_0)}{i,j-1} \\
&+
\sum_{k=i}^{j-1}\enspace
\sum_{u_0+u_1=r-\alpha(k)}\enspace
\sum_{v_0+v_1=s-\beta(k)}
\left( \boltzNuss{k,j}
\cdot \bfZ{u_0 n+v_0}{i,k-1} \cdot \bfZ{u_1 n+v_1}{k+1,j-1} \right) \\
&= [x^{(r-\alpha_0)n+(s-\beta_0)}] \emZ{i,j-1} \\
&+ \sum_{k=i}^{j-1}\enspace
\sum_{u_0+u_1=r-\alpha(k)}\enspace
\sum_{v_0+v_1=s-\beta(k)}
\left( \boltzNuss{k,j} \right. \\
&\left. \cdot \left( [x^{u_0 n+v_0}] \emZ{i,k-1} \right) \cdot
\left( [x^{u_1 n+v_1}] \emZ{k+1,j-1} \right)
\vphantom{\boltzNuss{k,j}} \right) \\
&= [x^{(r-\alpha_0)n+(s-\beta_0)}] \emZ{i,j-1} \\
&+ \sum_{k=i}^{j-1}\enspace
\sum_{u_0+u_1=r-\alpha(k)}\enspace
\sum_{v_0+v_1=s-\beta(k)}
\left( \boltzNuss{k,j} \right. \\
&\left. \cdot [x^{(u_0+u_1)n+(v_0+v_1)}] \left( \emZ{i,k-1} \cdot \emZ{k+1,j-1} \right)
\vphantom{\boltzNuss{k,j}} \right) \\
&= [x^{(r-\alpha_0)n+(s-\beta_0)}] \emZ{i,j-1} \\
&+ \sum_{k=i}^{j-1} \left( \boltzNuss{k,j}
\cdot [x^{(r-\alpha(k))n+(s-\beta(k))}] \left( \emZ{i,k-1} \cdot \emZ{k+1,j-1}
\right) \right) \\
&= [x^{rn+s}] \left( \emZ{i,j-1} \cdot x^{\ab{0}} \right) \\
&+ \sum_{k=i}^{j-1} \left( \boltzNuss{k,j}
\cdot [x^{rn+s}] \left( \emZ{i,k-1} \cdot \emZ{k+1,j-1} \cdot
x^{\alpha(k)n+\beta(k)} \right) \right) \\
&= [x^{rn+s}] \left( \vphantom{\sum_{k=i}^{j-1}} \emZ{i,j-1} \cdot x^{\ab{0}} \right. \\
&\left. + \sum_{k=i}^{j-1} \left( \boltzNuss{k,j}
\cdot \emZ{i,k-1} \cdot \emZ{k+1,j-1} \cdot
x^{\alpha(k)n+\beta(k)} \right) \right) \\
\end{split}
\end{align}
\end{proof}

\section{Proof for Lemma \ref{lem:ffttwo:lemma3}}
\label{sec:ffttwo:lemma3proof}

\begin{proof}
The lemma states that if the \bpd $d_0$ between reference
structures \strAB is even, then $\emZof{}{-\alpha}=\emZof{}{\alpha}$, while if
the distance is odd, then $\emZof{}{-\alpha}=-\emZof{}{\alpha}$.
Suppose first that $d_0$ is even. By Lemma \ref{lem:ffttwo:lemma1},
$\emZ{} = z_0 + z_2 x^2 + z_4 x^4 + \dots +
z_{M-2} x^{M-2)}$, and so $\emZof{}{-\alpha}=\emZof{}{\alpha}$.
Suppose now that
$d_0$ is odd. By Lemma \ref{lem:ffttwo:lemma1},
$Z(x) = z_1 x^1 + z_3 x^3 + z^5 x^5 \dots +
z_{M-1} x^{M-1}$, and so $\emZof{}{-\alpha}=-\emZof{}{\alpha}$.
\end{proof}

\section{Proof for Lemma \ref{lem:ffttwo:lemma4}}
\label{sec:ffttwo:lemma4proof}

\begin{proof}
Recall Euler's formula in complex analysis:
$\exp(ix) = \cos(x) + i \sin(x)$. As well, recall that
$\sin(\pi)=0$, $\cos(\pi)=-1$, and the trigonometric
addition formulas:

\begin{align}
\begin{split}
\cos(\alpha-\beta) &= \cos(\alpha) \cos(\beta) + \sin(\alpha) \sin(\beta) \\
\sin(\alpha-\beta) &= \sin(\alpha) \cos(\beta) - \sin(\beta) \cos(\alpha).
\end{split}
\end{align}

Then we have

\begin{align}
\begin{split}
\nu^{M_0-k} &= \exp\left(\frac{2 \pi i (M_0-k)}{M}\right) \\
&= \cos\left(\frac{2 \pi (M_0-k)}{M}\right) + i
\sin\left(\frac{2 \pi (M_0-k)}{M}\right) \\
&= \cos\left(\pi - \frac{2 \pi k}{M}\right) + i
\sin\left(\pi - \frac{2 \pi k}{M}\right) \\
&=
\left[
\cos(\pi) \cos\left(\frac{2 \pi k}{M}\right) +
\sin(\pi) \sin\left(\frac{2 \pi k}{M}\right)
\right] \\
&+
i \left[
\sin(\pi) \cos\left(\frac{2 \pi k}{M}\right) -
\sin\left(\frac{2 \pi k}{M}\right) \cos(\pi)
\right] \\
&=
-\cos\left(\frac{2 \pi k}{M}\right) + i
\sin\left(\frac{2 \pi k}{M}\right) \\
&=
-1 \left[ \cos\left(\frac{2 \pi k}{M}\right) - i
\sin\left(\frac{2 \pi k}{M}\right) \right] \\
&=
-1 \cdot \overline{\cos\left(\frac{2 \pi k}{M}\right) + i
\sin\left(\frac{2 \pi k}{M}\right)}  \\
&=
-1 \cdot \overline{\exp\left(\frac{2 \pi i k}{M}\right)} = - \overline{\nu^k} . \\
\end{split}
\end{align}

It follows that
$\nu^{M_0-k} = -\overline{\nu^k}$, so
$\nu^{k} = \overline{- \nu^{(M_0-k)}} = -\overline{\nu^{(M_0-k)}}$.

This completes the proof of the lemma.
\end{proof}
