# Three-Way Alignment Improves Multiple Sequence Alignment of Highly Diverged Sequences
## 1 Introduction  
Inferring evolutionary relationships among various species from molecular data, such as protein, DNA, and RNA sequences, is a basic problem in evolutionary biology. Multiple sequence alignment (MSA) is a primary step in phylogenetic reconstruction, and the accuracy of MSA directly affects the accuracy of reconstructing a phylogeny, especially a deep phylogeny [1, 2, 3, 4]. The most common method for aligning two sequences (pairwise sequence alignment, or PSA) is the Needleman-Wunsch algorithm [5], which is a dynamic programming (DP) approach that finds the optimal alignment based on a given scoring scheme [6, 7, 8]. Using DP in PSA is feasible in quadratic time and memory, which can even be reduced to linear memory requirement [9]. The idea of using DP for sequence alignment can be easily extended to MSA. However, multi-dimensional DP is practically infeasible even for a small number of sequences, due to time and space complexity [10]. As an alternative, a progressive alignment approach was proposed for MSA [11] and implemented in many alignment tools, such as MAFFT [12], MUSCLE [13], T-COFFEE [14], and CLUSTAL-W [15]. Progressive alignment fundamentally simplifies the task of MSA by breaking it down into a series of pairwise and profile alignments. Progressive alignment involves constructing a guide tree to determine the order of aligning sequences andperforming pairwise and profile alignment from the leaves of the guide tree to the root. The guide tree is usually constructed by using distance-based methods like UPGMA and neighbor joining (NJ) from a distance matrix obtained mainly from (1) k-tuple similarity or (2) PSA. Current MSA methods and tools perform well on aligning closely related sequences [16]. However, the performance of these methods decreases with sequence divergence [17; 18; 19]. Virtually everyone interested in deep phylogeny is looking for ways to improve MSA. Some have incorporated secondary structure to guide the sequence alignment [20; 21; 22; 23], while others explored post-alignment refinement [1; 17]. The improvement of MSA with these approaches remains limited. A guide tree is a crucial component in progressive alignment, and its accuracy affects the accuracy of output alignment [24]. A few studies have shown that an inaccurate guide tree could be a major source of error in progressive sequence alignment [25; 26]. Therefore, different strategies for improving guide trees have been proposed [24]. Two criteria have been used to evaluate the effect of guide trees on the accuracy of MSA generated by MAFFT and ClustalW, including (1) the sum-of-pair score (SPS), excluding shared gaps in pairwise comparisons, and (2) the accuracy of phylogenetic reconstruction [27; 28]. The result indicates that the final SPS is affected little by the initial guide tree, but better guide trees significantly improve the accuracy of the reconstructed phylogenies. However, constructing an accurate guide tree is difficult for highly diverged sequences. Aligning three sequences using dynamic programming is expected to improve the alignment and, in particular, the estimated distances used to build the initial guide tree [14; 15; 29; 30]. Three-dimensional dynamic programming (3D_DP), as formulated by [PERSON] [31], represents an extension of the Needleman-Wunsch algorithm originally proposed for pairwise sequence alignment. [PERSON] contributed to developing 3D-DP for an affine gap penalty. His approach to 3D-DP increases the time and space requirements to cubic complexity, which is not feasible for long sequences. The Carrillo-Lipman [32] algorithm was proposed to narrow down the search space within N-dimensional dynamic programming. The idea of this method is to combine the initial MSA with information from each pairwise alignment to define lower bounds for the two-dimensional projection of the optimal path. Consequently, this strategy enables us to focus solely on the cells within the N-dimensional lattice that satisfy these bounds.