RAM-MSA: an anytime memory-bounded method for exact multiple sequence alignment using path finding Authors: Jue Wang, Fumihiko Ino, Alia Benkahla Published: 2026 ABSTRACT AbstractMotivationMultiple sequence alignment (MSA) is a crucial process in bioinformatics, essential for understanding functional or structural relationships among DNA or protein sequences. As the number of sequences increases, existing exact MSA methods, which produce algorithmically optimal alignments, suffer from exponentially increasing memory consumption. Existing heuristic MSA methods, on the other hand, rapidly compute alignments on large sequence sets by sacrificing their accuracy. Current approaches remain insufficient, underscoring the necessity of a novel approach that bridges the gap between heuristic and exact MSA methods. Specifically, there is an urgent need for an exact MSA approach that enables users to obtain the best possible alignment within their available computation time.ResultsWe propose Recursive Anytime Memory-bounded MSA (RAM-MSA), a novel exact MSA method that manages exponential memory demands within a limited memory space. The proposed method promptly generates an initial MSA result and continuously outputs alignments with higher accuracy, ultimately providing an exact alignment. Experimental evaluations demonstrate that RAM-MSA reduced memory usage to 62.51% compared to a state-of-the-art exact MSA method. In terms of anytime performance, the proposed method generates an initial alignment with an objective score of 0.96 in a comparable time to the heuristic methods, and continues to improve the alignment until the exact result is obtained. Unlike existing path-finding-based methods, which support only linear gap penalties, RAM-MSA also handles affine gap penalties. This study provides a systematic quantification of the discrepancy between algorithmically optimal alignments and structurally-derived reference alignments.Availability and implementationSource code is available at https://github.com/luxwj/RAM-MSA. 1 Introduction Multiple sequence alignment (MSA) plays a crucial role in various sequence analysis applications. Similar symbols in input sequences are aligned to reveal the evolutionary or structural relationships among the sequences. In protein structure prediction, MSA results are necessary to improve the accuracy of the output structure (Jumper et al. 2021). For epidemic research, tracing viral evolution heavily relies on MSA methods (Katoh and Standley 2021). MSA algorithms represent biological sequences as strings and generate alignments by inserting gaps. These alignments are scored using a substitution matrix that assigns a score to each pair of symbols. An exact MSA method, such as a generalized Needleman-Wunsch algorithm extended to high-dimensional spaces (Needleman and Wunsch 1970), produces an algorithmically optimal alignment. Such an optimal alignment achieves the highest possible score under the given substitution matrix. However, algorithmic optimality may diverge from biological correctness. To evaluate the biological significance of the generated alignments, the results should be compared against the reference alignments in the benchmarks. Notably, all MSA approaches mentioned in this paper are global MSA methods, which align the sequences across their entire length. Most of the existing MSA approaches are heuristic methods and generate approximate alignments because MSA problems are known to be NP-complete (Wang and Jiang 1994). However, existing heuristic methods often fail to produce sufficiently accurate alignments on real-world sequence sets (Chowdhury and Garai 2017). In contrast, exact MSA approaches are preferred in accuracy-critical applications. Current exact MSA methods are unable to handle large-scale sequence sets due to the exponentially growing memory consumption (Bani Baker et al. 2024, Hosseininasab and Van Hoeve 2021, Lin et al. 2007, Sundfeld et al. 2018). Dynamic programming (DP) based methods and path-finding methods require O(ln) and O(2nl) memory, respectively, where n is the number of sequences and l is the maximal length of sequences. Once the available memory is exhausted, these methods simply terminate without alignment results. Furthermore, the scoring scheme of existing path-finding methods is limited to linear gap penalties, whereas popular heuristic methods support the more biology-realistic affine gap penalties. For large-scale problems where exact solutions may be unattainable, an anytime method allows users to obtain the best possible solution within their available time. Several anytime A* methods have been proposed, including MAWA* (Vadlamudi et al. 2010), ARA* (Likhachev et al. 2003), and APS (Vadlamudi et al. 2016). A problem setting closely related to MSA is the longest common subsequence (LCS), where anytime column search (ACS) has been used to develop anytime approaches (Djukanovic et al. 2020). However, extending such approaches to MSA is nontrivial because MSA is a non-uniform cost search problem with complex substitution matrices and gap penalties, whereas LCS is a uniform cost search problem. To address the limitations of existing heuristic and exact MSA approaches and bridge the gap between them, we propose a novel exact MSA method called Recursive Anytime Memory-bounded MSA (RAM-MSA). Our method is designed based on the A* algorithm (Hart et al. 1968), which builds a search tree to convert MSA problems into path-finding problems. To promptly generate an initial MSA result, our method adopts a greedy path-finding strategy. Furthermore, it continuously updates the MSA result by integrating the ACS paradigm into A* search, which eventually outputs an exact alignment. To cope with exponential memory growth, RAM-MSA employs a memory-bound strategy that removes some unexpanded tree nodes when the pre-defined memory threshold is reached during the search process. The pruned nodes are later restored when sufficient memory space becomes available, ensuring the exact solutions. Our contributions are as follows: We propose a recursive MSA approach that refines score estimation in A* search. The proposed approach leverages (n−1)-D MSA results to guide n-D tasks, i.e. tasks with n input sequences, producing more accurate score estimates than the conventional Carrillo and Lipman (CL) lower bound (Carrillo and Lipman 1988) in most cases. This enhancement adds no extra computational cost beyond the existing exponentially scaling workload O(2nl). We propose a recursive MSA approach that refines score estimation in A* search. The proposed approach leverages (n−1)-D MSA results to guide n-D tasks, i.e. tasks with n input sequences, producing more accurate score estimates than the conventional Carrillo and Lipman (CL) lower bound (Carrillo and Lipman 1988) in most cases. This enhancement adds no extra computational cost beyond the existing exponentially scaling workload O(2nl). Our approach incorporates the ACS paradigm to realize an anytime property, enabling continuous generation of intermediate MSA results with increasing accuracy, and eventually outputs the exact MSA. We extended the ACS method to accommodate the feature of non-uniform cost search in MSA tasks. The initial alignment reaches up to 98% accuracy with a runtime comparable to heuristic MSA methods like MAFFT (Katoh and Standley 2013). Our approach incorporates the ACS paradigm to realize an anytime property, enabling continuous generation of intermediate MSA results with increasing accuracy, and eventually outputs the exact MSA. We extended the ACS method to accommodate the feature of non-uniform cost search in MSA tasks. The initial alignment reaches up to 98% accuracy with a runtime comparable to heuristic MSA methods like MAFFT (Katoh and Standley 2013). A memory-bound strategy is developed to compute large-scale exact MSA problems under limited memory capacity. By temporarily removing selected unexpanded nodes from the search list, the method reduces memory consumption to near-linear levels, whereas conventional path-finding approaches incur exponential growth in list size. A memory-bound strategy is developed to compute large-scale exact MSA problems under limited memory capacity. By temporarily removing selected unexpanded nodes from the search list, the method reduces memory consumption to near-linear levels, whereas conventional path-finding approaches incur exponential growth in list size. To the best of our knowledge, our method is the first path-finding-based MSA approach supporting affine gap penalties. Compared to the linear gap penalty model, the affine gap penalty model is more essential for producing biologically realistic alignments. Specifically, protein sequence alignments prefer a long gap to multiple distributed gaps. However, existing path-finding-based exact MSA methods are unable to handle affine gap penalties because doing so would substantially increase workload and memory consumption compared to linear gap penalties. To the best of our knowledge, our method is the first path-finding-based MSA approach supporting affine gap penalties. Compared to the linear gap penalty model, the affine gap penalty model is more essential for producing biologically realistic alignments. Specifically, protein sequence alignments prefer a long gap to multiple distributed gaps. However, existing path-finding-based exact MSA methods are unable to handle affine gap penalties because doing so would substantially increase workload and memory consumption compared to linear gap penalties. We comprehensively evaluated RAM-MSA from both algorithmic and biological perspectives. Specifically, we compared the reference alignments against the exact alignments generated based on the optimal score under a given substitution matrix. This study experimentally demonstrates the discrepancy between algorithmically optimal alignments and structurally-derived reference alignments. We comprehensively evaluated RAM-MSA from both algorithmic and biological perspectives. Specifically, we compared the reference alignments against the exact alignments generated based on the optimal score under a given substitution matrix. This study experimentally demonstrates the discrepancy between algorithmically optimal alignments and structurally-derived reference alignments. 2 Background 2.1 Multiple sequence alignment algorithms To process biological sequences with MSA methods, the sequences are often transformed into strings. For protein sequences, each symbol in a string corresponds to one of the twenty standard amino acids. Figure 1 shows an example of MSA, which takes n≥3 sequences as inputs and generates the output alignment by inserting gaps into each sequence. The input sequences may have different lengths, but the output alignment consists of n sequences with the same length l. Example of MSA (n=4). The symbol “-” represents a gap. The sum-of-pairs (SP) score serves as the objective function in exact MSA methods. The final output of an exact MSA method is the alignment with the highest SP score. Assuming an alignment A contains n sequences of equal length l, the SP score of A is calculated as follows: Where A[i][k] denotes the k-th symbol in the i-th sequence of the alignment, and s(x,y) is a function calculating the score of two symbols, x and y, based on a substitution matrix and gap penalties. Common substitution matrices used in protein sequence alignment tasks include BLOSUM (Henikoff and Henikoff 1992), PAM (Dayhoff 1972), and Gonnet (Gonnet et al. 1992), which define scores for all 210 possible substitution pairs of the twenty standard amino acids (and their corresponding symbols). Each element in A is either a symbol from the alphabet, e.g. one of the twenty amino acids in protein sequences, or a gap, denoted by “-”. An alignment must satisfy the following constraints: (1) For any two symbols, the k-th and m-th with ktm do 2: k= index of the first non-empty bin 3: p= node with the highest f-score in Lopen[k] 4: // reexp_fscore is used when re-expanding the node 5: if p.fscore10611.74. The results suggested that the scalability limit under affine gap penalties was more sensitive to the path length, i.e. the alignment length. RAM-MSA successfully computed more exact alignments in the linear cases than in the affine ones. As explained in Section 3.4, computing alignments under linear gap penalties is less complex and has a lower workload. 4.3 Anytime performance We demonstrate the anytime performance of the RAM-MSA method by illustrating how much time it has taken to generate the intermediate MSA results. Figure 6 shows the results on the BAliBASE RV11 BBS11024 sequence set under linear gap penalties. The first anytime result was produced by the greedy search in 0.006 seconds with an objective score close to 0.97. The second result was generated by the anytime feature using the extension of ACS in 46 seconds, with an objective score exceeding 0.995. PA-star2 generated the exact alignment in 162 seconds, whereas RAM-MSA generated the exact alignment in 319 seconds. The anytime feature performed well under linear gap penalties because it generated highly accurate results considerably faster than PA-star2. Anytime performance on the BAliBASE RV11 BBS11024 (n=4,l=385) under linear gap penalties. Higher objective scores indicate better alignment qualities. PA-star2 was parallelized with 12 threads, whereas RAM-MSA was a sequential method using one thread. Figure 7 demonstrates the results on the SABRE Twilight Zone twi_102 sequence set under affine gap penalties. The greedy search generated an alignment with an extremely low objective score, indicating that it performed worse under affine gap penalties. The second output achieved an objective score close to 0.8, which was better than the approximate results rapidly generated by the heuristic methods. Anytime performance on the SABRE Twilight Zone twi_102 (n=3,l=197) under affine gap penalties. Higher objective scores indicate better alignment qualities from an algorithmic perspective. Note that PA-star2 did not support affine gap penalties. Note that RAM-MSA required extra time to expand all the promising nodes to guarantee the result’s optimality after finding the last MSA. It took 1841.75 seconds and 195.52 seconds to complete the search on BAliBASE RV11 BBS11024 and on SABRE Twilight Zone twi_102, respectively. 4.4 Ablation study We conducted an ablation study on the four variants of the RAM-MSA method. The first variant was the standard A* method, against which we showed the speedups of the other variants. The remaining variants corresponded to our first three contributions. The second variant used the recursive MSA approach to enhance the h-score estimator by exploiting lower-dimensional MSA results. The third variant incorporated the ACS paradigm to continuously generate intermediate MSA results and dynamically update the score upper bound for node pruning. The fourth variant, the RAM-MSA method, integrated the memory-bound strategy to compute large-scale sequence sets with a limited memory space. Figure 8 shows the results of the ablation study of RAM-MSA on customized 1dlc, 2cba, and BAliBASE RV11 BBS11017 sequence sets under linear gap penalties. In Fig. 8a, the recursive MSA method showed an insignificant impact on speedup and even slowed down the computation for some sequence sets. This phenomenon was possibly related to the usage of recursive MSA results. When the method found the recursive MSA result for a node p, it computed a better estimate for the path score, which helped prune more candidate nodes. However, most of the nodes without a corresponding recursive MSA result could have a worse estimate than node n, which gave n a low priority in the open list. When only a subset of the nodes achieved a better estimate, the speedup was restricted. Ablation study of the RAM-MSA method regarding (a) speedup of computation time and (b) memory usage for customized 1dlc (n=4,l=590), customized 2cba (n=5,l=259), and BAliBASE RV11 BBS11017 (n=4,l=273) under linear gap penalties. The third and fourth variants adopted the ACS paradigm to dynamically update the score upper bound. They achieved higher speedups than the second variant by pruning more nodes from the open list. The fourth variant periodically checked its memory usage, which had little effect on computation time. The memory usage of the four variants is shown in Fig. 8b. In general, a variant with lower computation time also required less memory because fewer nodes were inserted into the open list and expanded. RAM-MSA used about half the memory required by the standard A* method on customized 2cba. The results of the ablation study under affine gap penalties are demonstrated in Fig. 9, including performance on BAliBASE RV11 BBS11009, BBS11022, and SABRE Twilight Zone twi_022. The recursive MSA method accelerated computation by a factor of 1.31 on twi_022. The anytime feature derived from the ACS paradigm achieved a speedup of 2.25× on BBS11009. However, computation slowed down on BBS11022 when the anytime feature was used. A potential reason is that very few nodes were pruned because no intermediate alignment other than the greedy result was generated during the search process. When comparing the third variant with standard A*, memory usage was reduced by approximately 75% and 66% on BBS11009 and twi_022, respectively. Ablation study of the RAM-MSA method regarding (a) speedup of computation time and (b) memory usage for BAliBASE RV11 BBS11009 (n=4,l=105), BAliBASE RV11 BBS11022 (n=4,l=69), and SABRE Twilight Zone twi_022 (n=4,l=100) under affine gap penalties. 4.5 Biological significance The biological significance of the alignments generated by RAM-MSA and the baseline methods was evaluated using the reference alignments. We excluded the customized benchmark because no reference alignments are available. The average SP and TC accuracies of the exact results generated by RAM-MSA under affine and linear gap penalties are shown in Tables 5 and 6, respectively. Table 5Biological significance of RAM-MSA under affine gap penalties.BenchmarkMethodTime (s)SPTCBAliBASE RV11RAM-MSA (affine)3367.210.730.56 (Group 1)PA-star2N/AN/AN/AMAFFT0.640.600.36MSAProbs0.170.780.59MUSCLE0.180.780.59SABRE TwiRAM-MSA (affine)9934.740.310.18 (Group 1)PA-star2N/AN/AN/AMAFFT2.370.160.06MSAProbs0.290.320.19MUSCLE0.380.310.19The three heuristic methods used their default settings. Higher SP and TC values indicate better accuracies. Note that PA-star2 did not support affine gap penalties. Biological significance of RAM-MSA under affine gap penalties. The three heuristic methods used their default settings. Higher SP and TC values indicate better accuracies. Note that PA-star2 did not support affine gap penalties. Table 6Biological significance of RAM-MSA under linear gap penalties.BenchmarkMethodTime (s)SPTCBAliBASE RV11RAM-MSA (linear)71 888.400.460.24 (Group 1 & 2 & 3)PA-star2N/AN/AN/AMAFFT1.970.400.22MSAProbs1.030.710.50MUSCLE1.070.720.52The three heuristic methods used their default settings for affine gap penalties. Higher SP and TC values indicate better accuracies. The results of PA-star2 are invalid because it failed on BAliBASE RV11 Group 3. Biological significance of RAM-MSA under linear gap penalties. The three heuristic methods used their default settings for affine gap penalties. Higher SP and TC values indicate better accuracies. The results of PA-star2 are invalid because it failed on BAliBASE RV11 Group 3. In Table 5, RAM-MSA achieved higher SP and TC accuracies than MAFFT on both benchmarks. However, MSAProbs and MUSCLE performed better on BAliBASE RV11. On SABRE Twilight Zone, RAM-MSA achieved SP and TC accuracies of 0.31 and 0.18, respectively, which are comparable to the best results among the heuristic methods. The drawbacks of RAM-MSA are its non-negligible computation time and scalability limitations, arising from its focus on algorithmic optimality. Of note, the heuristic methods used their default gap penalty settings, whereas RAM-MSA set the gap open and extension penalties to 9.5 and 2.0. We attempted to apply the gap penalties used by MAFFT and MSAProbs to RAM-MSA, but this resulted in worse accuracy than achieved with the current settings. This observation suggests that the optimal gap penalty settings likely differ between the exact and heuristic MSA methods. This is because the heuristic methods actually compute MSAs with several rounds of pairwise alignments. Furthermore, other parameters are involved in the computation, such as an offset value in MAFFT, meaning that accuracy does not depend solely on the gap open and extension penalties. Although the exact methods computed algorithmically optimal alignments, the SP and TC accuracies were often lower than those of the state-of-the-art heuristic MSA methods. A potential reason is that the heuristic methods analyzed the input from a phylogenetic perspective to improve accuracy, such as computing a guide tree for the sequences. Table 6 shows the biological significance of RAM-MSA under linear gap penalties. Of note, the three heuristic methods computed the alignments with their default settings for affine gap penalties. On BAliBASE RV11, RAM-MSA successfully computed more sequence sets in the linear cases than in the affine cases, but the SP and TC accuracies decreased gradually. The TC accuracy of RAM-MSA was 0.24, whereas MUSCLE achieved the highest TC accuracy of 0.52 among the baselines. Comparing the results of RAM-MSA in Tables 5 and 6, the affine gap penalties were more feasible than the linear ones for computing biologically significant MSA. Table 7 shows the anytime performance of RAM-MSA on BAliBASE RV11 Group 2 to 4 and SABRE Twilight Zone Group 2 under affine gap penalties. RAM-MSA failed to compute the optimal MSA and instead generated only the anytime results for these groups. It was difficult to evaluate the algorithmic optimality of the anytime results because no exact optimal alignments exist. The SP and TC accuracies of RAM-MSA were relatively lower than those of the heuristic methods. The major reason is that the anytime performance declines when n>5. Specifically, RAM-MSA produced no intermediate output other than the greedy search result when n>5. Furthermore, the greedy search produced results of low accuracy. Table 7Anytime performance of RAM-MSA.BenchmarkMethodTime (s)SPTCBAliBASE RV11RAM-MSA (affine)5775.140.250.10 (Group 2 & 3 & 4)PA-star2N/AN/AN/AMAFFT2.670.310.12MSAProbs2.880.660.38MUSCLE2.900.670.40SABRE TwiRAM-MSA (affine)5534.330.080.08 (Group 2)PA-star2N/AN/AN/AMAFFT4.820.050.03MSAProbs2.000.230.11MUSCLE3.170.230.10The results show biological significance achieved under affine gap penalties. The three heuristic methods used their default settings. Higher SP and TC values indicate better accuracies. Note that PA-star2 did not support affine gap penalties. Anytime performance of RAM-MSA. The results show biological significance achieved under affine gap penalties. The three heuristic methods used their default settings. Higher SP and TC values indicate better accuracies. Note that PA-star2 did not support affine gap penalties. The anytime performance on the SABRE Twilight Zone twi_102 is shown in Fig. 10. Although the objective score increased to 1.00 as shown in Fig. 7, the SP accuracy showed no significant improvement. The second anytime output achieved an SP accuracy of 0.44, which was higher than the algorithmically optimal alignment outputted last with an SP accuracy of 0.41. The fluctuating results in Fig. 10 indicate that the algorithmic optimality diverges from biological correctness. Anytime performance on the SABRE Twilight Zone twi_102 (n=3,l=197) under affine gap penalties. Higher SP accuracies indicate better alignment qualities from a biological perspective. Note that PA-star2 did not support affine gap penalties. 5 Discussion We introduced RAM-MSA, an anytime memory-bounded method for exact MSA tasks. We proposed a recursive MSA approach to improve h-score calculation, combined A* search and a variant of ACS to enable the anytime feature, and developed a memory-bound strategy to compute large-scale MSA problems within a limited memory capacity. RAM-MSA supports affine gap penalties, whereas existing path-finding-based exact methods only support linear gap penalties. By comparing the exact alignments with structurally-derived reference alignments, this study provides insights into the limitations of exact MSA methods and highlights the need for improved objective functions that better capture biological relevance. 5.1 Key outcomes of RAM-MSA Regarding algorithmic optimality, RAM-MSA generated optimal MSAs achieving an objective score of 1.00, whereas the highest objective score among the heuristic MSA methods was 0.82 on BAliBASE RV11 Group 1. RAM-MSA leverages (n−1)-D MSA results to guide n-D tasks and incorporates the ACS paradigm to realize the anytime property while accelerating computation. RAM-MSA achieved a speedup of up to 2.25× and reduced memory usage to 25% with these two features on BAliBASE RV11 BBS11009. In addition to the memory usage reduction induced by the anytime feature, the memory-bound strategy further enabled RAM-MSA to complete an exact MSA within a limited memory space. Specifically, RAM-MSA computed the exact MSA on BAliBASE RV11 BBS11006 with (n,l)=(8,541), on which the existing exact MSA method failed. The anytime feature also enabled RAM-MSA to rapidly generate an initial output with relatively high accuracy under linear gap penalties. On BAliBASE RV11 BBS11024, RAM-MSA achieved an objective score of over 0.96 within 1 second, whereas the optimal MSA required over 300 seconds to generate. 5.2 Limitations of RAM-MSA RAM-MSA addresses exact MSA problems primarily from an algorithmic perspective. As a result, the output alignments may differ substantially from the reference alignments because optimizing the objective function does not necessarily guarantee biological correctness. For instance, RAM-MSA achieved an SP accuracy of 0.73 on BAliBASE RV11 Group 1, while MSAProbs achieved an SP accuracy of 0.78 with its heuristic output. To enhance the accuracy of exact methods, an objective function that more faithfully captures the biological relationships among sequences is required. The scalability of RAM-MSA remains limited despite its memory-bounded extension because memory consumption grows exponentially with both n and l. The program ran out of memory on a machine with 32 GB of RAM when processing a task with lnl>10611.74 under affine gap penalties, and when 2nl>10204.70≈2680.00 under linear gap penalties. The scalability limit is higher under affine gap penalties than under linear gap penalties because the pruning strategy omits a large portion of nodes in the affine case. In practice, actual memory usage also depends on the pruning strategy, beyond what the theoretical workload predicts. 5.3 Future work In future work, we aim to leverage multi-core CPUs by parallelizing the proposed method to improve computational efficiency. To accelerate node expansion when handling a large number of sequences, we further plan to explore GPU platforms (Okada et al. 2015, Sundfeld et al. 2025). Regarding the anytime parameters, we will perform systematic parameter tuning rather than directly adopting the settings from previous studies. Additionally, the greedy search under affine gap penalties requires improvement. Contributor Information Jue Wang, Graduate School of Information Science and Technology, The University of Osaka, Suita, Osaka 565-0871, Japan. Fumihiko Ino, Graduate School of Information Science and Technology, The University of Osaka, Suita, Osaka 565-0871, Japan. Conflicts of interest None declared. Funding This work was supported in part by JSPS KAKENHI Grant Number JP23K28061 and JST BOOST, Japan Grant Number JPMJBS2402. Data availability The data and code underlying this article are available in RAM-MSA, at https://github.com/luxwj/RAM-MSA. References Associated Data Data Availability Statement The data and code underlying this article are available in RAM-MSA, at https://github.com/luxwj/RAM-MSA.