RAM-MSA: an anytime memory-bounded method for exact multiple sequence alignment using path finding.

Motivation: Multiple 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. Results: We 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 implementation: Source code is available at https://github.com/luxwj/RAM-MSA.