# Three-Way Alignment Improves Multiple Sequence Alignment of Highly Diverged Sequences
## 2 Materials and Methods
### Three-Way Alignment Algorithm  
Let A, B, and C represent three sequences, and their lengths are denoted by \(n,\ m,\ \text{and}\ l\), respectively. For three residues of \(A_{i},\ B_{j}\), and \(C_{k}\) at position \((i,j,k)\), there are seven possible alignment configurations. \(M(i,j,k)\) represents the best score when three residues are aligned. \(I_{xy}(i,j,k)\), \(I_{xz}(i,j,k)\), and \(I_{yz}(i,j,k)\) are the scores of introducing one gap in \(C_{k}\), \(B_{j}\), and \(A_{i}\) respectively. Similarly, \(I_{x}(i,j,k)\), \(I_{y}(i,j,k)\), and \(I_{z}(i,j,k)\) represent the scores for aligning a residue in \(A_{i}\), \(B_{j}\), and \(C_{k}\) while introducing gaps in the other two sequences. The 3-way alignment algorithm was formulated by [PERSON] [31] for the affine gap penalty. By convention, the criterion for choosing the best alignment among all possible ones is equivalent to maximum parsimony, i.e., the alignment with the smallest alignment cost incurred by indels and mismatches is the best alignment. Expressed alternatively, the best alignment is the one with the highest alignment score as a function of matches and mismatches, as well as gap open and gap extension penalties. With three sequences, an aligned site with two residues in the first two sequences and a gap in the third sequence is interpreted as having a single change (a deletion in the third sequence), with \(u_{D}\) representing the deletion cost. Similarly, an aligned site with a single residue in sequence 1 and a gap in the two other sequences is also interpreted as a single change, i.e., a single insertion in sequence 1, with \(u_{I}\) representing this insertion cost. [PERSON] [31] used \(u_{D}=u_{I}=u\) in his alignment algorithm, with the implicit assumption that insertions and deletions occur equally frequently. This was also adopted by [PERSON] [33]. However, [PERSON] and [PERSON] [29] treated \(u_{D}\) and \(u_{I}\) differently. We defined Equations (10)-(16) in a similar way to those in [29], with a slight modification to facilitate the implementation of the Carrillo-Lipman algorithm, as follows:  
\[M(i,j,k)=\left[max\left\{ \begin{array}{l}M(i-1,j-1,k-1)\\ I_{xy}(i-1,j-1,k-1)\\ I_{yz}(i-1,j-1,k-1)\\ I_{yz}(i-1,j-1,k-1)\\ I_{x}(i-1,j-1,k-1)\\ I_{y}(i-1,j-1,k-1)\\ I_{z}(i-1,j-1,k-1)\\ \end{array} \right]+S\big{(}A_{i},B_{j},C_{k}\big{)}, \tag{10}\]  
\[I_{xy}(i,j,k)=\left[max\left\{ \begin{array}{l}M(i-1,j-1,k)-2 GO\\ I_{xz}(i-1,j-1,k)-2 GO\\ I_{yz}(i-1,j-1,k)-2 GO\\ I_{zy}(i-1,j-1,k)-2 GO\\ I_{xy}(i-1,j-1,k)-2 GE\\ I_{x}(i-1,j-1,k)-2 GE\\ I_{y}(i-1,j-1,k)-2 GE\\ \end{array} \right]+S\big{(}A_{i},B_{j}\big{)}, \tag{11}\]  
\[I_{xz}(i,j,k)=\left[max\left\{ \begin{array}{l}M(i-1,j,k-1)-2 GO\\ I_{xy}(i-1,j,k-1)-2 GO\\ I_{yz}(i-1,j,k-1)-2 GO\\ I_{y}(i-1,j,k-1)-2 GO\\ I_{yz}(i-1,j,k-1)-2 GE\\ I_{x}(i-1,j,k-1)-2 GE\\ \end{array} \right]+S(A_{i},C_{k}), \tag{12}\]  
\[I_{yz}(i,j,k)=\left[max\left\{ \begin{array}{l}M(i,j-1,k-1)-2 GO\\ I_{xy}(i,j-1,k-1)-2 GO\\ I_{xz}(i,j-1,k-1)-2 GO\\ I_{x}(i,j-1,k-1)-2 GO\\ I_{yz}(i,j-1,k-1)-2 GE\\ I_{z}(i-1,j,k-1)-2 GE\\ \end{array} \right]+S\big{(}B_{j},C_{k}\big{)}, \tag{13}\]\[I_{x}(i,j,k)=max\left\{ \begin{array}{l}M(i-1,j,k)-2 GO\\ I_{yz}(i-1,j,k)-2 GO.\\ I_{xy}(i-1,j,k)-GO-GE\\ I_{xz}(i-1,j,k)-GO-GE\\ I_{y}(i-1,j,k)-GO-GE\\ I_{z}(i-1,j,k)-GO-GE\\ I_{x}(i-1,j,k)-2 GE\end{array} \right., \tag{14}\]  
\[I_{y}(i,j,k)=max\left\{ \begin{array}{l}M(i,j-1,k)-2 GO\\ I_{xz}(i,j-1,k)-2 GO\\ I_{xy}(i,j-1,k)-GO-GE\\ I_{yz}(i,j-1,k)-GO-GE\\ I_{x}(i,j-1,k)-GO-GE\\ I_{z}(i,j-1,k)-GO-GE\\ I_{y}(i,j-1,k)-2 GE\end{array} \right., \tag{15}\]  
\[I_{z}(i,j,k)=max\left\{ \begin{array}{l}M(i,j,k-1)-2 GO\\ I_{xy}(i,j,k-1)-2 GO\\ I_{xz}(i,j,k-1)-GO-GE\\ I_{yz}(i,j,k-1)-GO-GE\\ I_{x}(i,j,k-1)-GO-GE\\ I_{y}(i,j,k-1)-GO-GE\\ I_{z}(i,j,k-1)-2 GE\end{array} \right., \tag{16}\]  
In the formulae above, \(GO\) and \(GE\) are gap open and gap extension penalties, and \(S(\alpha,\beta)\) denotes the score of aligning two residues, which is determined using a scoring matrix such as PAM or BLOSUM.