# Three-Way Alignment Improves Multiple Sequence Alignment of Highly Diverged Sequences
## 2 Materials and Methods  
### Carrillo-Lipman Algorithm for Three Sequences  
In this section, we restate the Carrillo-Lipman equations for three sequences [32]. Suppose we have three sequences, \(s_{1}\), \(s_{2}\), and \(s_{3}\). The optimal alignment for these three sequences has the highest score based on the SPS criterion. Therefore, any other alignment has a lower score, leading to the following inequality:  
\[S(\gamma^{*})-S(\gamma^{\ell})\geq 0, \tag{1}\]  
where \(\gamma^{*}\) and \(\gamma^{\ell}\) are the optimal and arbitrary alignments, respectively. The SPS of a 3-way alignment is as follows:  
\[S(\gamma^{*})=S(\gamma_{12})+S(\gamma_{13})+S(\gamma_{23}), \tag{2}\]  
\[S(\gamma_{12})+S(\gamma_{13})+S(\gamma_{23})-S(\gamma^{\ell})\geq 0, \tag{3}\]where the \(\gamma_{12}\) is the pairwise alignment of \(s_{1}\) and \(s_{2}\), \(\gamma_{13}\) is the pairwise alignment of \(s_{1}\) and \(s_{3}\), and \(\gamma_{23}\) is the pairwise alignment of \(s_{2}\) and \(s_{3}\). In other words, any of these pairwise alignments can be considered the projection of \(\gamma^{*}\) on the three surfaces of 3D-DP. Based on Equation (3), we can write the following three inequalities for each projection of \(\gamma^{*}\):  
\[ \begin{array}{l}S(\gamma_{12})\geq S(\gamma^{e})-\left(S(\gamma_{13})+S( \gamma_{23})\right)\\ S(\gamma_{13})\geq S(\gamma^{e})-\left(S(\gamma_{12})+S(\gamma_{23})\right)\\ S(\gamma_{23})\geq S(\gamma^{e})-\left(S(\gamma_{12})+S(\gamma_{13})\right) \end{array}  \tag{4}\]  
For each pair of sequences, we can find the optimal alignment which has the highest SPS, so we can write the following:  
\[ \begin{array}{l}S\big{(}\gamma_{12}^{*}\big{)}\geq S(\gamma_{12})\\ S\big{(}\gamma_{13}^{*}\big{)}\geq S(\gamma_{13})\\ S(\gamma_{23}^{*}\big{)}\geq S(\gamma_{23})\end{array}  \tag{5}\]  
where \(\gamma_{12}^{*}\), \(\gamma_{13}^{*}\), and \(\gamma_{23}^{*}\) are the optimal pairwise alignments. Using these three inequalities, we can rewrite the Equation (4) as the following inequalities:  
\[ \begin{array}{l}S(\gamma_{12})\geq S(\gamma^{e})-\left(S\big{(}\gamma_{13}^ {*}\big{)}+S(\gamma_{23}^{*})\right)\\ S(\gamma_{13})\geq S(\gamma^{e})-\left(S\big{(}\gamma_{12}^{*}\big{)}+S(\gamma_ {23}^{*})\right)\\ S(\gamma_{23})\geq S(\gamma^{e})-\left(S\big{(}\gamma_{12}^{*}\big{)}+S\big{(} \gamma_{13}^{*}\big{)}\right)\end{array}  \tag{6}\]  
The Carrillo-Lipman algorithm defines the following three boundaries based on the above inequalities:  
\[ \begin{array}{l}L_{12}=S(\gamma^{e})-\left(S\big{(}\gamma_{13}^{*}\big{)}+S (\gamma_{23}^{*})\right)\\ L_{13}=S(\gamma^{e})-\left(S\big{(}\gamma_{12}^{*}\big{)}+S(\gamma_{23}^{*}) \right)\\ L_{23}=S(\gamma^{e})-\left(S\big{(}\gamma_{12}^{*}\big{)}+S\big{(}\gamma_{13} ^{*}\big{)}\right)\end{array}  \tag{7}\]  
\(L_{12}\) is the lower bound for the score of the pairwise alignment of \(S_{1}\) and \(S_{2}\), \(L_{13}\) is the lower bound for the score of the pairwise alignment of \(S_{1}\) and \(S_{3}\), and \(L_{23}\) is the lower bound for the score of the pairwise alignment of \(S_{2}\) and \(S_{3}\). In other words, \(L_{12}\), \(L_{13}\), and \(L_{23}\) are the lower bounds for the measure of the projection of any 3-dimensional optimal path into the planes determined by each pair of sequences. Then, when looking for \(\gamma^{*}\), we need only consider those paths in the cubic that their pairwise alignment satisfies the related inequality. Similar to the Carrillo-Lipman algorithm, we call the set of paths for which their projection on the planes \((S_{1},S_{2})\), \((S_{1},S_{3})\), and \((S_{2},S_{3})\) satisfies the inequality (6), \(X_{12}\), \(X_{13}\), and \(X_{23}\) respectively. Thus, the paths in the set, as follows:  
\[X=X_{12}\cap X_{13}\cap X_{23}, \tag{8}\]  
are the only possible candidates to be an optimal path. To consider only the paths in \(X\) means having to apply the dynamic programming procedure to find \(\gamma^{*}\) only in subregion \(Y\) of the cubic.