Alignment of 3 sequences can be solved by 3 dimensional DP. The gap should be carefully treated.

DP for 3 sequences with linear gap cost

General equation

The iteration for alignment of 3 sequences with linear gap costs is written as:
\[
\mbox{ for } i=1, \ldots \ell;
\mbox{ for } j=1, \ldots m;
\mbox{ for } k=1, \ldots n; \\
F_{i,j,k}= \max
\left[ \begin{array}{l}
F_{i-1,j-1,k-1} + s(x_i,y_j,z_k),\\
F_{i,j-1,k-1} + s(-,y_j,z_k),\\
F_{i-1,j,k-1} + s(x_i,-,z_k),\\
F_{i-1,j-1,k} + s(x_i,y_j,-),\\
F_{i-1,j,k} + s(x_i,-,-),\\
F_{i,j-1,k} + s(-,y_j,-),\\
F_{i,j,k-1} + x(-,-,z_k)\\
\end{array} \right.
\]

Sum of Pairs Score (SPS)

The above equation implies that the gap costs are linear, but they are not explicitly shown.
The gap costs are implicitly included in \( s(,,) \)’s. We have to give the gap costs by defining the \( s(,,) \)’s including ‘-‘.
For example, \( s(-,y_j,z_k) \) in the score that \(y_j\) is aligned to \(z_k\) and a gap is inserted in sequence \(x\).
For multiple sequence alignment problem (alignment for more than 2 sequences), ‘Sum of Pairs Score (SPS)’ is often used.
The SPS for an aligned column including \(n\) sequences is defined as the sum of all the pairwise scores:
\[
\newcommand{\sum}{\mathop{\rm \Sigma}\limits}
s(x^1,\ldots,x^n) = \sum_{i \ne j} s(x^i,x^j)
\]
If SPS and the linear gap cost are used,
\[
s(-,y_j,z_k) = s(y_j,z_k) + s(-,z_k) + s(-,y_j) = s(y_j,z_k) – 2d.
\]
Similarly, \(s(x_i,-,-)\) can be written as:
\[
s(x_i,-,-) = s(-,-) + s(x_i,-) + s(x_i,-) = -2d,
\]
because \(s(-,-)\) is the score for aligning nothing and it should be zero.
Based on the above analysis, the iterative equation of sequence alignment of 3 sequences with SPS score and linear gap is:
\[
\mbox{ for } i=1, \ldots \ell;
\mbox{ for } j=1, \ldots m;
\mbox{ for } k=1, \ldots n; \\
F_{i,j,k}= \max
\left[ \begin{array}{l}
F_{i-1,j-1,k-1} + s(y_j,z_k) + s(x_i,z_k) + s(x_i,y_j),\\
F_{i,j-1,k-1} + s(y_j,z_k) – 2d,\\
F_{i-1,j,k-1} + s(x_i,z_k) – 2d,\\
F_{i-1,j-1,k} + s(x_i,y_j) – 2d,\\
F_{i-1,j,k} – 2d,\\
F_{i,j-1,k} – 2d,\\
F_{i,j,k-1} – 2d\\
\end{array} \right.
\]

Initialization

The initial values on the 3 axes, x-axe, y-axe, z-axe, are easy：
\[
\begin{array}{l}
F_{0,0,0} = 0;\\
F_{i,0,0} = -2id \mbox{ for } i=1, \ldots \ell;\\
F_{0,j,0} = -2jd \mbox{ for } j=1, \ldots m;\\
F_{0,0,k} = -2kd \mbox{ for } k=1, \ldots n;\\
\end{array}
\]
The initial values on the 3 planes, y-z-play, x-z-play, x-y-play, are complicated and require DPs.
For example \(F_{0,j,k}\)’s are calculated by the following iterations.
\[
\mbox{ for } j=1, \ldots m;
\mbox{ for } k=1, \ldots n; \\
F_{0,j,k}= \max
\left[ \begin{array}{l}
F_{0,j-1,k-1} + s(y_j,z_k),\\
F_{0,j-1,k} – 2d,\\
F_{0,j,k-1} – 2d,\\
\end{array} \right.
\]