Multiple sequence alignment as a sequence-to-sequence learning problem
Authors: Edo Dotan
Yonatan Belinkov
Oren Avram
Elya Wygoda
Noa Ecker
Michael Alburquerque
Omri Keren
Gil Loewenthal
Tal Pupko
Venue: ICLR 2023 poster (2023)
Keywords: sequence alignment
molecular evolution
natural language processing
bioinformatics

Abstract: The sequence alignment problem is one of the most fundamental problems in bioinformatics and a plethora of methods were devised to tackle it. Here we introduce BetaAlign, a methodology for aligning sequences using an NLP approach. BetaAlign accounts for the possible variability of the evolutionary process among different datasets by using an ensemble of transformers, each trained on millions of samples generated from a different evolutionary model. Our approach leads to alignment accuracy that is similar and often better than commonly used methods, such as MAFFT, DIALIGN, ClustalW, T-Coffee, PRANK, and MUSCLE.

Published as a conference paper at ICLR 2023
MULTIPLE SEQUENCE ALIGNMENT AS A SEQUENCE- TO-SEQUENCE LEARNING PROBLEM
Edo Dotan' Yonatan Belinkov Oren Avram', Elya Wygoda', Noa Ecker', Michael Alburquerque', Omri Keren', Gil Loewenthal' and Tal Pupko
Tel Aviv University
Technion - Israel Institute of Technology
3 University of California Los Angeles
eddodotan@mill tau ac.il
f Corresponding authors: bel.inko@ttechnin..eee i1, talp@tauex tau. ac, i1
ABSTRACT
The sequence alignment problem is one of the most fundamental problems in bioinformatics and a plethora of methods were devised to tackle it. Here we intro- duce BetaAlign, a methodology for aligning sequences using NLP approach. BetaAlign accounts for the possible variability of the evolutionary process among different datasets by using ensemble of transformers, each trained on millions samples generated from a different evolutionary model. Our approach leads to alignment accuracy that is similar and often better than commonly used methods, such as MAFFT, DIALIGN, ClustalW, T-Coffee, PRANK, and MUSCLE.
INTRODUCTION
A multiple sequence alignment (MSA) provides record of homology at the single position reso- lution within set of homologous sequences. order to infer the MSA from input sequences, one has to consider different evolutionary events, such as substitutions and indels (i.e., insertions and deletions). MSAS can be computed for DNA, RNA, or amino acid sequences. MSA inference is considered of the most common problems in biology (Van Noorden et al. 2014). Moreover, MSAs are required input for various widely-used bioinformatics methods such as domain analy- sis, phylogenetic reconstruction. motif finding, and ancestral sequence reconstruction (Kemena & Notredame [2099 [Avram et al. (219)). These methods assume the correctness of the MSA, and their performance might degrade when inaccurate MSAS are used as input (Ogden Rosenberg 2006 Privman et al. 2012).
MSA algorithms typically assume a fixed cost matrix as input, i.e., the penalty for aligning non- identical characters and the reward for aligning identical characters. They also assume a penalty for the introduction of gaps. These costs dictate the score each possible alignment, and the algorithm aims to output the alignment with the highest score. Previous studies demonstrated that fitting the cost matrix configuration to the data increases the MSA inference accuracy (Rubio-Largo et al.) 2018 Llinares-Lppez et al. (022). Thus, MSA algorithms often allow users tune parameters that control the MSA computation. However, in practice, these parameters are seldom altered, and only few default configurations are used.
Alignment algorithms are often benchmarked against empirical alignment regions, which are thought to be reliable. However, such regions within alignments do reflect the universe of align- ment problems (Thompson et al. 1994). Of note, these regions were often manually computed, so there is no guarantee that they represent a reliable "gold standard" (Morrison 2009). When test- ing aligmment programs with simulated complex alignments, the results differ from the benchmarks results (Chang et al. 2014).
SSupoorted by the Viterbi Fellowship in the Center for Computer Engineering at the Technion.

---

Published as a conference paper at ICLR 2023
In the last decade, deep-learinng algorithms have revolutionized various fields (LeCun al. including computer vision (Voulodimos et al., 2018). natural language processing (NLP) Young
2015),
et al. 2018), sequence correction (Baid al. 2021), and medical diagnosis (Rakocz et al. 2021
Hill et al. 202T). Neural-network solutions often resulted in a substantial increase in prediction accuracy compared to traditional algorithms. Deep learning has also changed molecular biology and evolutionary research, c.g., by allowing accurate predictions of three-dimensional protein structures using AlphaFold (Jumper al., 2021).
We propose BetaAlign, a deep-learning method that is trained on known alignments, and is able accurately align novel sets of sequences. The method is based on the "transformer" architec- ture (Vaswani et al. (017). recent deep-learning architecture designed for sequence-to-sequene tasks, which was originally developed for machine translation. BetaAlign was trained on millions of alignments drawn from different evolutionary models. Our analyses demonstrate that Beta has comparable, and in some cases superior, accuracy compared to the most popular MSA algorithms: T-Coffee (Notredame et al. 2000), ClustalW (Larkin et al. (007), DIALIGN (Morgenstern, 2004).
MUSCLE (Edgar 2004). MAFFT Katoh Standley 2013) and PRANK (Löytynoja Goldman 2008).
BetaAlign converts the alignment problem into a sequence-to-sequene learning problem, a well- studied problem within the NLP field (Hirschberg & Manning 2015). We first present the NLP- based approach for pairwise alignment. We represent both the unaligned sequences and the resulting alignment as sentences in two different "languages". The language of the input sequences (the source language) is termed Concat, because, in this representation, each pair of input sequences concatenated with the pipe character ("1"") representing the border between the sequences. this language, each character in the resulting string is considered a different token. For example, when we aligned the sequence "AAG" against the sequence "ACGG", in the Concat language, this will be represented by the sentence "A A G ACG G" (Fig. [ In this sentence, there are eight tokens. Of note, in the Concat language there are only five possible unique tokens. A dictionary of language is the entire set of tokens used in that language, and thus in the Concat language, the dictionary is the set {"A", "C", "T", ".).
b
d
AAG
AA-G ACGG
AAG/ACG
Transformer
AAAC-GGG
ACGG
Figure I: An illustration of aligning sequences with cequence-to-sequenee learning. (a) Consider two input sequences "AAG" and "ACGG". (b) The result of encoding the unaligned sequences into the source language (Concat representation).
(c) The sentence from the source language is translated to the target language via a transformer model. (d) The translated sentence in the target language (Spaces representation). (e) The resulting alignment, decoded from the translated sen- tence, in which "AA-G" is aligned to "ACGG". The transformer architecture illustration is adapted from Vaswani al. (2017).
The target language, i.e., the language of the output alignment, termed here Spaces. In this language, the dictionary is the set ["A", "C", "G", "T", "_"]. In this representation, the tokens of the different aligned sequences are interleaved. Thus, the first two tokens in the Spaces output sentence are the first character of the first sequence and the first character of the second sequence, respectively. The third and fourth tokens correspond to the second column of the pairwise alignment, etc. In the above example, assume that in the output alignment "AA-G" is aligned to "ACGG", then, in the Spaces ces language, this will be represented as the sentence "A C G G G" (Fig. T We have compared the performance of different source and target representations (see Section A.2.2
With these representations, the input sequences are a sentence in one language, the output align- ment is sentence in another language, and perfect alignment algorithm is requested to accurately transduce one language to the other. The details regarding the training and execution of the NLP transformers are provided in Section 2 and Section A Of note, the occasional generation of in- valid alignments was encountered while developing BetaAlign. This challenge was addressed by introducing ensemble of transformers (see Section A.2.3).
2

---

Published as a conference paper at ICLR 2023
1.1 RELATED WORK
The Needleman & Wunsch (9700) algorithm to infer pairwise alignment assumes an affine gap penalty to indels, which is equivalent to assuming that the indel length distribution is geometric. The cost of substitutions and the reward for exact matches are equivalent to assuming specific prob- abilitics for character substitutions. Assuming that this model captures the evolutionary dynamics of all datasets is unrealistic because: (1) These simple assumptions are known to be violated in em- pirical datasets, e.g., the probabilities of proteins substitutions depend on the context. For example, whether the residue is exposed the solvent or not; (2) It was previously shown that indel lengths are not geometrically distributed in protein datasets (Benner et al.. 1993; Chang & Benner 2004 Zhang et al., 2010). Different datasets differ in their evolutionary dynamics, and thus the same model should not be applied to all datasets. Indeed, it was shown that fitting the scoring schemes to the specific dataset can improve the performance of the dynamic programming algorithms for alignment inference, suggesting that variability among datasets is common (L.inares-LLópe et al.) 202T]. These observations motivate the development of aligners that are able to learn data- spea--pecifiic attributes.
One could generalize this dynamic programming to multiple sequences with the time complexity of O(L*) (where L is considered the sequence length and N is the number of sequences), and thus, MSA computation becomes quickly impractical. Today multiple-sequenece aligners are mostly based on the progressive method in which pairwise alignments are iteratively combined to infer the multiple sequence alignment (e.g. Löytynoja 2014 Katoh & Standley 2013 Edgar 2004).
MATERIALS AND METHODS
2.1 AN ANLP-BASED APPROACH
Our hypothesis is that cutting-edge NLP tools can learn from known examples, and a trained model can infer accurate alignments for unseen data. A plethora of neural network architectures is available in the NLP domain for transduction, including recurrent neural networks (Sutskever et al. (0144) and transformers Vaswaani et al., 2017). As these architectures are sequence-to- te-quuence, the input to these models is a sentence, and the output is a predicted transduction. Our approach relies on optimizing the model based on training data, i.e., the learning phase of the algorithm. In our case, a massive amount of training data, i.e., true alignments, is obtained using simulations. We simulate the training alignments using SpartaABC (Loewenthal et al., (02T). SpartaABC allows simulating datasets along phylogenetic tree, with various indel-length distributions, and with different indel- lo-substitution rate ratios. allows finding indel model parameters that best describe a specific empirical dataset. It also assumes that the evolutionary dynamics of insertions and deletions characterized by a different set of parameters, i.e., a rich-indel model (Loewenthal et al.) 2021).
Formally, let denote the input sequences and y denote the correct MSA. Each training data point is pair (z, During the training phase, the NLP algorithm learns a function So that maps x to y. i.e., transformer. This function should minimize the discrepancy between y and So (2r.. The function fa depends on set of tunable parameters, 0, which defines the architecture and the internal representation of the transformer. Given an unseen test sequence, which was not used for training, the predicted alignment is obtained by applying fo to this input.
Note that the values of the pairs (Ir y) depend on an evolutionary model s that includes the topology and branch lengths of the phylogenetic tree, as well as the substitution and indel model parameters. Changing 1 would alter the training data distribution, which in turn, should lead different fo. is possible to train the model on data from a specific vú, or train model in which y is sampled from a prior distribution over its model parameters.
If we apply the Concat encoding with the Pairs rs decoding, the source dictionary size is the set of five characters and the size of the target dictionary is the set of 24 characters (see Section [A.18)), In NLP transduction, each token in each dictionary has to be embedded in higher dimensional space. Thus, two different embeddings are needed (for the source and target dictionaries). In contrast, we can consider joint dictionary for applying the Concat or Crisscross (see Section A.1.8)) en- codings with the Spaces decoding. The joint dictionary of Concat and Spaces has six tokens: "A", "C", "G", "T".. "_", "I". We note that the token "_" is never found in the input, while the token
3

---

Published as a conference paper at ICLR 2023
"I" is never found in the output. Nevertheless, assume joint dictionary for both the input and the output. The joint dictionary of Crisscross and Spaces has five tokens: "A", "C", "G", "T","" "_". Thus, the same embedding function is used for both the source language, ie., the unaligned sequences, and the target language, i.e., the aligned sequences. One of the advantages of the joint dictionaries over the separate dictionaries of Concat with Pairs, is that the dictionaries have fixed size regardless of how many sequences are included in the alignment (in the Pairs represen- tation, should use triplets for alignments with three sequences, quadruplets for alignments with four sequences, etc.) Thus, we only use the Spaces language when we generalize from pairwise to multiple alignment.
2.2 SPLITTING THE UNALIGNED SEQUENCES TO SEGMENTS
The transformers we applied for aligning sequences are limited to sentences of up to 1,024 tokens, which usually suffices for natural languages. When aligning biological sequences, the sentence that represents the unaligned sequences is often much longer than this threshold, and the transformers fail to transduce due memory and run-time limitations (both these factors are proportional to the square of the sequence length). We exemplify our approach for aligning long sequences on an example comprising five sequences. each of which of length of at least 2,000 characters. In our "segmentation" methodology, we first define a parameter that we call segment size, which depends on the number of sequences. characters. Thus, when we start the alignment process, we first process 554 tokens (110 characters from each sequence and four "I" characters, when using the Concat representation).
our example of five sequences, we selected a segment size of 110
When aligning segments, we use dedicated transformers for this task that we call "segmented trans- formers". The segmented transformers share the same architecture with the standard transformers, but they are trained on different data. In addition, while standard transformers were designed to always align the entire input sentence, segmented transformers align only prefixes of the unaligned sequences. Specifically, the segmented transformers were designed that the last column in the resulting aligned sequences does not include gaps.
To generate the training data for the segmented transformers, simulated long alignments (see Section[A.1.2). This provided us with long unaligned sequences, which we call X, and "true" MSA, which call Y. The training data for the segmented transformer are pairs of (1r, y), in which represents a segment of the unaligned sequence taken from X, and y represents a subregion of Y that corresponds to r. Both r and y are short enough allow training a transformer.
To divide X and Y to multiple short (z, pairs, we repeated the following process. We first
(b)
(0)
extract the first 110 characters from each of the five sequences, which will be the unaligned seg- In the true
(N)
ment, i.e., the alignment, we find the column with the highest index that the number of non-gap characters of each sequence to the left of this column is smaller or equal to the segment size. Once this col- umn is found, we inspect if it has any indels. If so, we inspect the previous column. We repeat this process until we find col- umn without indels. The ob- tained (first) column without in- del characters marks the "true" alignment for this segment, i.e., the y. Hence, the source sen- tence the first 110 characters of each unaligned sequence (x:)
(d)
Figure 2: Creating training data for segmented transformers, ex- plained using a segment size of three characters. (a) The true alignment; (b) The unaligned sequences of the first segment, i.e., the first x as described in the Section 2.2 (c) The segment of the true MSA that corresponds to the x presented in i.e., the first
Note that the third column of the true MSA was not selected as it contains gaps, and the forth column was not selected, as includes four characters of some of the original sequences (i.e., it is longer than the segment size three); (d) The unaligned se- quences of the second segment; (e) The corresponding segment the true alignment.
4

---

Published as a conference paper at ICLR 2023
and the target is the "true" alignment (y) from the first column until the indel-free column that was found. From both X and Y. we remove all the characters that appear in y (the characters that were successfully aligned). This process is repeated with the new X and Y until they empty, i.c., they were divided to multiple (xr, y) pairs. Of note, when analyzing the last segments, it is possible that fewer than 554 tokens are translated, For explanatory purposes,
assume segment size of three and five input sequences (Fig. 2 Simply diving X and Y to pairs of arbitrary length introduces various problems as illustrated in Section 2.3
The above procedure describes the generation of training data, for which the true alignment is known. We now turn describe how to run trained model. Here, we first transduce the first segment. However, in order to decide which characters to remove and which to retain, we cannot rely on the identification of an indel-free column the true alignment as we did for the training data (since we do not know the true alignment). Thus, we analyze the resulting alignment, and mark which characters of the input segments were translated from each sequence. These characters are removed, and the process is repeated. This iteration stops when all characters from the unaligned sequences were processed. Of note, different trained transformers may divide the segments differ- ently. After aligning all of the segments, we reconstruct the resulting alignment by concatenating the resulting alignment of each segment.
2.3 PROBLEMS ARISE WHEN SIMPLY SPLITTING MSAS
The logic for searching for indel-free column is illustrated in Fig. 3 i.e., example show- ing the problems without indel- free last column. For explana- tory purposes, we assume a seg- ment size of three. The algo- rithm starts by translating the first three characters from each of the five sequences (Fig. 33).
(b)
(0)
(8)
(d)
(e)
The indel in the last column of the first segment (Fig. (b) in-
Figure 3: Importance of indel-free last column of segments. Con- sider (a) to be the true alignment, with a segment size of three characters. Panels (b) and (c) refer to the unaligned sequences and the aligned results, of the first segment respectively. Simi- larly, panels (d) and (e) refer the unaligned sequences and the aligned results of the second segment, respectively. Note the dif- ference between (a) and the concatenation of the results, as the fourth and fifth columns of the latter should be the fourth column in (a).
troduces new complexity, as this indel has a perfect match in the next segment (Fig. (p.. In our approach, this is solved by train- ing segmented transformers. If we choose to use indels in the last column, we move the com- plexity of the segment approach into the concatenation of the segments afterward. One will need to make sure the indels at the resulted alignment make sense. Of note, this approach makes each of the indels appear in only segment (but segment may harbor multiple indels).
RESULTS
3.1
COMPARING PERFORMANCE TO DIFFERENT ALIGNERS
We compared the performance of BetaAlign to the soute-of-the-an alignment algorithms: ClustalW [arrin et al. 2007). DIALIGN (Morgenstern) 2004). MAFFT (Katoh & Standley 2013), T-Coffee Notredame et al.] 2000), PRANK (Löytynoja & Goldman 2008), and MUSCLE (Edgar 2004)) For each number of sequences from two to ten, the performance was compared on a simulated
test dataset comprising 3,000 nucleotide MSAs (Fig. 44). BetaAlign had the lowest error rate for any number of aligned sequences (paired t-test; p < 10 10-200. For all alignment methods, the error increases the number of sequences increases. Notably, ClustalW and DIALIGN were much more affected by the increase in the number input sequences, compared to other methods. Of note, this analysis was conducted by applying the Concat source language with the Spaces target language.
5

---

Published as a conference paper at ICLR 2023
Nuclectide sequences
Protein sequences
(a)
(b)
0.23
DAAION PAFFT
HAETT
0.08
CS-error
CS-error
HERIEL BHEAKig
PUSELE
0.06
0.00
648
040
Number input sequences
Number of input sequences
Figure 4: Comparing the accuracy of BetaAlign to other aligners on the SND1 nucleotide dataset (a) and on the SPD1LG protein dataset (b). The lower the column score error (CS-error), the more accurate is the aligner (see Section A.1.3)
We repeated the same analysis for the protein dataset. The error of all methods was lower compared to the nucleotide sequences, most likely reflecting the increase in alphabet size, which helps identify homologous regions (Fig. App) PRANK and BetaAlign outperformed all other aligners. As seen from Fig. there is single optimal method to align all types of sequences.
3.2 GENERALIZING TO LARGE MSAS
Aligning long sequences with transformers introduces new challenges. The attention map calculated inside the transformer is Onn²m?), both term of memory and running time, where and m are the number of sequences and the sequences' length, respectively. Note, that mm reflects the total tokens that need be processed. Thus, increasing the alignment size causes memory and time problems. This known problem in the NLP domain, and different efficient transformers were created in order to tackle this issue (Lin et al., 2021). Those architec- tures cannot be directly applied to the alignment prob- lem (see Section 3.5). Hence, we developed new way to align longer sequences by splitting the input sequences into short segments and training the transformers to align each segment (the size of the segments varies along the run, but is approximately 100 alignment columns). We compared the performance of all aligners MSAs of five sequences, with true alignment lengths up to 2,500 bases and 2,508 amino acids, for nucleotide and protein sequences, respectively. Clearly, the performance of Be- taAlign is affected by the division of sequences into short segments, both when aligning nucleotide (Fig. (5h) and protein (Fig. 5D) sequences. Notably, even with this ap- proximation, BetaAlign is more accurate than the widely used aligners MAFFT and ClustalW for nucleotide se- quences and more than MAFFT, ClustalW, and MUSCLE for protein sequences.
(a)
Protein sequences
(b) Nucleatide se quences
Cistaw
Heart
HoreT
MUSCLE Beiald gn
MUSCLE
Botadaag:
Cheerrrr
CSerror
0.12
3.75
3.25
Figure 5: Performance on MSAs with five (a) protein and (b) nucleotide se- quences. The average MSA length was 760 bases and 765 amino acids, for nu- cleotide and protein sequences, respec- tively. These datasets were aligned after dividing the input into short segments, thus overcoming computational mem- ory and run time limitations introduced by large MSAs.
3.3 BETAALIGN CAN TRAINED TO CAPTURE SPECIFIC DATA ATTRIBUTES
In this section, describe two experiments that demonstrate the importance of fitting the scoring scheme to specific datasets. Evolutionary processes generating sequence data substantially vary across the tree of life and among different regions within genome. To this end, BetaAlign was trained on simulated data which were generated based on prior assumptions, which characterize the evolutionary dynamics of indels in Drosophila (oaiilaaaooeeee (Loewenthal al. 2021). Fig. 6h displays the results

---

Published as a conference paper at ICLR 2023
(a) Drosophila- le sequences
(b)
Protein sequences
[e]
Protein sequences (b) Nudeatide
Oustre
Horry
MUSOLE
028
MUSOLE
6:3
CS CS-error
CSerror
0.44
0.2-
dommmtrs
domains
Figure 6: Evaluating the different aligners on datasets that reflect different scenarios found in biological sequences. (a) Drosophila-lin datasets with high deletion rates. (b) Protein- like datasets comprised of either three or five domains, each domain with its own indel- evolutionary dynamics.
Figure 7: on the accuracy of protein (a) and nucleotide (b) datasets. Train and test alignments had 10 sequences. Spatial variation was only intro- duced to the test data, i.c., different regions of the alignment were simulated with different sets of indel model parameters.
The effect of model misxpecification
of the different aligners. BetaAlign and PRANK (Löytynoja & Goldman 2008) outperformed all of the other aligners (paired t-test; p < 10-3). We hypothesize that the high accuracy of PRANK stems from its ability to differentiate insertions and deletions and the fact that deletions occur at higher rates than insertions in this Drosophila-like dataset.
Next, we tested the performance of the different aligners on proteins containing different domains, e.g., with different electrochemical properties. Each of the domains has its own indel rates and distributions, reflecting the biological phenomenon of variation in the evolutionary dynamics among different regions within a single protein. We simulated proteins with either three or five domains and compared the accuracy of the various aligners (Fig. (6p) BetaAlign outperformed all other aligners, clearly demonstrating the ability of our approach to learn complicated indel patterns from training data (paired t-test; p < 10-5). Interestingly, increasing the number of domains led to significant loss in PRANK's 's inference accuracy, suggesting that it is more sensitive to spatial variation in indel processes within the analyzed sequences. We conducted another analysis characterizing the errors of the different aligners (see Section A.2.1.
3.4 MODEL MISSPECIRICATION
We next evaluated the sensitivity of BetaAlign to model misspecifications. Specifically, we trained BetaAlign on alignments without spatial variations, but tested its performance on alignments gen- erated with spatial variations. Test datasets were created by generating four "segments", each with a different indel dynamics (see Section [A. BetaAlign was substantially more accurate on the test protein dataset compared to other aligners (Fig. ( On the nucleotide dataset, BetaAlign CS-error (see Section A..13)) was lower than two aligners but higher than the other two (Fig. [ We note that without model misspecification, BetaAlign had the highest accuracy compared to all other aligners on nucleotide datasets and was not the hest for protein datasets. Model misspecifica- tion changed this order, BetaAlign is now the most accurate aligner for protein dataset and had intermediate accuracy on nucleotide dataset. In general, machine-learning models are sensitive to deviations between the training and testing distributions. We found it surprising as this case, the classic aligners on the protein datasets were more sensitive than BetaAlign.
Sec.ion[A.I.II],
3.5 ATTENTION MAP COMPARISON
BetaAlign harnesses NLP-based sequence-to-sequenee methods to analyze biological data. How- ever, it is clear that biological data are substantially different from natural languages data, e.g., they have a much smaller dictionary size (six for nucleotides using the Spaces representation, com- pared to order of a hundred thousand tokens in vocabularies of natural languages). Attention maps provide gateway for understanding the internal properties of various transformers. Put sim- ply, attention maps show on which parts of the sequences the transformer focuses while generating
7

---

Published as a conference paper at ICLR 2023
the next token. Fig. Bh displays the averaged attention map gathered from the attention layers of the decoder (in this case, when processing an amino-acid MSA of seven sequences). Fig. 8p shows an
attention map from NLP English-to-Free to-French translation task (Belinkov & Glass 2019 Bahdanau iet al. 2016).
Note that each attention map corresponds to translation of single sentence. In the case of Fig. Bp. the translation is of the sentence "The agreement of the European Economic Area was signed in August 1992.". The sentence translated in Fig. 88 is a concatenation of seven unaligned sequences of length approximately 40 amino-acids. Clearly, natural language sentences are much shorter, on average, than sentences processed by BetaAlign, and thus, the BetaAlign attention map is much larger (consisting of hundreds of tokens) than the natural language one (consisting of dozens of tokens). Moreover, the attention in the natural languages is focused on one diagonal while the attention in BetaAlign is focused on several diagonals, the number of which equals the number of inputs sequences. The difference stems from the fact that in the BetaAlign sequence-to-sent task, generating the next token requires assigning more weight to information that is distributed among all sequences. Of note, this analysis was conducted on the Concat and Spaces for the source and target languages, respectively.
Fig. Bp is an enlargement of the attention map around the rightmost diagonal of Fig. 8p. The x-axis refers to the characters of the input sentence and the y-axis refers to the translated characters of the output sentence. As can be seen, the diagonal is actually step of seven rows and one column. This is the logical explanation as each of the seven rows extracts information from this column, i.e., the characters of a column at the resulting MSA are all dependent on the same character in the unaligned sequences. The red arrows mark the corresponding output and input characters. As can be seen, the weight is higher in this area, i.e., the transformer learned the importance of the corresponding area.
Due to the dynamics of our attention maps (specificallly, the focus split), we cannot easily use NLP architectures for longer sentences, which have dedicated attention maps (Lin et al. 2021). In our segmentation strategy, instead of calculating the entire attention map, we focus the attention on specific places of the diagonals. Future research will focus on improving attention calculations.
4 DISCUSSION
We have designed and implemented new technology that aligns sequences with accuracy that competes with state-of-the-art methods. Our deep dearning-basee approach is fundamentally dif- ferent from current algorithms, which rely on conventional scoring schemes. Our method allows us to personalize the alignment process for inputs that differ in their evolutionary dynamics. The increased knowledge regarding the differences in mutation processes and selection regimes among different species allows us to easily train BetaAlign on clade-specific datasets, i.e., we are capable of creating different aligners per kingdom and even per species. Similarly, BetaAlign can be trained to capture the evolutionary dynamics of different regions within the genome, e.g., introns versus promotors versus other non-coding regions. Moreover, this method has the potential to capture variations among different types of protein-coding genes, e.g., transmembrane versus cytoplasmatic proteins.
One can argue that BetaAlign heavily depends the simulator. In other words, if the simulator does not reflect biological realism, the resulting aligner may produce inaccurate MSAs for empirical data. However, the design of BetaAlign allows switching between simulators easily. This allows re- search groups to focus on mimicking the sequence evolutionary process to create better simulators, which turn, will improve the alignment accuracy. Since tuning a simulator an easier task than creating new alignment method, we anticipate shift in the scientific community from developing better aligners to developing more realistic simulation schemes. BetaAlign can learn those specific alignment rules without the need to specifically provide them as input to the program. This feature abolishes the need to provide any assumptions regarding the evolutionary process at the development stage of the aligner. For example, if a research group assumes that translocation or recombination has happened between proteins of different species, they can create a simulator reflecting this pro- cess and train BetaAlign to align those sequences, instead of developing new methods to consider translocation or recombination (to the best of our knowledge, current aligners do not consider these types of events).
8

---

Published as a conference paper at ICLR 2023
(a)
(c)
Tokens in output sentence
Tokens in output sentence
agresment
digned
August
(b)
on
was
zone
économique européerne
ande
1992
Tokens input sentence
<end>
Tokens in input sentence
Figure 8: Comparing the attention maps of BetaAlign and other NLP tasks. The x-axis is the input tokens, and the y-axis is the output tokens. The attention splits between all the input tokens when generating the next token. (a) The attention map extracted from the last layer of the BetaAlign's 's decoder. (b) Attention map extracted from translating an English sentence. The attention map (b) focuses on one location of the input sentence while BetaAlign focuses on multiple locations, one for each of the unaligned sequences. To visualize this, colored each of the unaligned sequences in different color as well as the amino acid that refers to this unaligned sequence. When zooming into the map, there is step of the attention the four left diagonals, that we identified as an indel. In this indel, the first "I" has a meaningful part. (c) Zooming into the rightmost diagonal of (a). The red arrows represent the corresponding output and input characters "L".
In this paper, we have demonstrated the power of applying NLP- iis-iieeered deep learning methods to sequence alignment. We anticipate that deep learning methods originating in NLP will become more common for solving numerous computation-biolog tasks, e.g., to infer ancestral sequences or to detect post-translation modification sites in proteins. Future development will benefit from the es- tablishment of benchmark datasets, developing better pre-training models for biological sequences, and designing dedicated transformers for nucleotide and protein sequences.
4.1 LIMITATIONS
BetaAlign has some limitations that impact its effectiveness and utility. First, in its current form unable to align very long sequences from hundreds of species. Scaling up the algorithm requires further algorithmic improvements. Second, the application the methodology requires GPUs for optimal performance, which may not always be available to researchers. Third, BetaAlign heavily relies on specific probabilistic evolutionary models. Evolutionary aspects that are not accounted for in the model will not be captured by the trained algorithm. For example, the models applied assume that the indel dynamics is homogenous across the alignment. However, is known that indels are more common in the N and C termini of proteins compared the rest of the sequence. The transformer cannot learn this aspect as it relies on simulations in which homogeneity of the indel process was assumed.
ACKNOWLEDGEMENTS
Y.B. and T.P. have received funding from the Israel Science Foundation (Grants 448/20 and 2818/21, respectively). Y.B. was supported by Azrieli Foundation Early Career Faculty Fellowship. E.D., O.A., E.W. N.E.. M.A., and G.L. were supported in part by a fellowship from the Edmond Safra Center for Bioinformaties Tel Aviv University.

---

Published as a conference paper at ICLR 2023
REFERENCES
Federico Abascal, David Posada, and Rafael Zardoya. MtArt: A New Model of Amino Acid Re- placement for Arthropoda. Molecular Biology and Evolution, 24(1):1-5, Jamuary 2007. ISSN 0737-4038. doi: 10. 00.1033/mlbbv//msl13... URL h
ms ms1136
Oren Avram, Rapoport Dana, Shir Portugez, and Tal Pupko. MIcrOblallz3r user-friendly web server for the analysis of large-scale microbial genomics data. Nucleic Acids Research, 2019. doi: 10.1093/nar/gk7423. URL httts:t:: hwwp://///0.11//////g/g....
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural Machine Translation by Jointly Learning to Align and Translate. arXiv: 1409.443 [cs, stat], May 2016. UtLhttp:
brg/abs/ /409. 0473
arXiv: 1409.0473.
Gunjan Baid, Daniel E. Cook, Kishwar Shafin, Taedong Yun, Felipe Alinares-Lóper Quentin Berthet, Aaron M. Wenger, William J. Rowell, Maria Nattestad, Howard Yang, Alexey
Kolesnikov, Armin Töpfer, Waleed Ammar, Jean-Philippe Vert, Ashish Vaswani, Cory Y. McLean, Pi-Chuan Chang, and Andrew Carroll. DeepConsensus: Gap-Aware Sequence Trans- formers for Sequence Correction. preprint, Bioinformatics, August 2021. URL http:// 1111/102211111 08. 31. 458403
Yonatan Belinkov and James Glass. Analysis Methods in Neural Language Pro- cessing: A Survey. Transactions of the Association for Computational Linguis-
lics, 7:49-72, April 2019. ISSN 2307-387X, doi: a
URL
00254/
Steven A. Benner, Mark A. Cohen, and Gaston H. Gonnet. Empirical and Structural Models for In- sertions and Deletions in the Divergent Evolution of Proteins. Journal of Molecular Biology, 229 (4):1065-1082, February 1993. ISSN 0022-2836. doi: 10. 10.10066/mbii199933 1993. URL https:
7/www. www.sciencedirect. com/ ort.aacccc....cc..aaaaaaaaaaaaaa
Jia-Ming Chang. Paolo Di Tommaso, and Cedric Notredame. TCS: a new multiple sequence align- ment reliability measure to estimate alignment accuracy and improve phylogenetic tree recon- struction. Molecular Biology and Evolution, 31(1))m,,,111))11) 3166;:625-1167, June 2014. ISSN 1537-1719. doi: 10. 70.1093//mllbe//sull1...
Mike S. S. Chang and Steven A. Benner. Empirical analysis of protein insertions and deletions determining parameters for the correct placement of gaps in protein sequence alignments. Journal of Molecular Biology, 341(2):617-631, August 2004. ISSN 0022-2836. doi: 10.1016/j.imb.2000 05.045.
Robert C. Edgar. MUSCLE: multiple sequence alignment with high accuracy and high through- put. Nucleic Acids Research, 329-)11992 March 2004. ISSN 1362-4962. doi: 10. 1093/ nar/gkh340. URL 1093/nand htt////ar/kkh3/
c. oup. wwt.//oo///aaaee http://ttiiilllloooooooo////oooo www.lllooooooooo//
Steven Henikoff and Jorja G Henikoff. Amino acid substitution matrices from protein blocks. Pmo ceedings of the National Academy of Sciences of the United States of America, 89(22):10915 10919, November 1992. ISSN 0027-8424. URL https: htwp:://wwwww... ncbi. mwm. nih. nih.vv..ogoo/
pmc/ http//attceesssec553..333
Brian L. Hill, Nadav Rakocz, Ákos Rudas, Jeffrey N. Chiang, Sidong Wang, Ira Hofer, Maxime Can- nesson, and Eran Halperin. Imputation of the continuous arterial line blood pressure waveform from non-invasive measurements using deep learning. Scientific Reports, 11(1):15755, December 2021. ISSN 2045-2322 doi: 10. 1031038/ 598-021--9491-yy, com/
URL httpt:t/////o www. nature.
Julia Hirschberg and Christopher D Manning. Advances natural language processing. ARTIFI- CIAL INTEELJIGGENE pp. 7, 2015.
10

---

Published as a conference paper at ICLR 2023
Jaime Huerta- Huerta-Cepas, François Serra, and Peer Bork. ETE 3: Reconstruction, Analysis, and Visual-
ization of Phylogenomic Data. Molecular Biology and Evolution, 33(6):6635-1638, June 2016.
ISSN 0737-4038, 1537-1719. doi: 10. 00.1093/molbeww/ms0046. URL attps::// /ates///ccammmcc..
David T. Jones, William R. Taylor, and Janet M. Thornton. The rapid generation of mutation data matrices from protein sequences. Computer applications in the biosciences: CABIOS, 8(3):275- 282, June 1992. ISSN 0266-7061.
doi: 10. 0..003/boinnormmaic4..........
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zídek, Anna Potapenko, Alex Bridg- land, Clemens Meyer, Simon A. A. Kohl, Andrew J. Ballard, Andrew Cowie, Berardino Romera-Paredes, Stanislav Nikolov, Rishub Jain, Jonas Adler, Trevor Back, Stig Petersen, David Reiman, Ellen Clancy, Michal Ziclinski, Martin Steinegger, Michalina Pacholska, Tamas Berghammer, Sehastian Bodenstein, David Silver, Oriol Vinyals, Andrew W. Senior, Koray Kavukcuoglu, Pushmeet Kohli, and Demis Hassabis. Highly accurate protein structure pre- diction with AlphaFold. Nature, 596(7873):583-589, August 2021. ISSN 0028-0836, 1476- 4687. doi: 10. 1080000841118-002-0033888 641586-021-03811
URL https: /www nature cwm artoia/rreees/////
Kazutaka Katoh and Daron M. Standley. MAFFT Multiple Sequence Aligmment Software Version 7: Improvements in Performance and Usability. Molecular Biology and Evolution, 30(4):772- 780. April 2013. ISSN 0737-4038. doi: 10. 10.1093/molbev//ms0000.. URL https::tt//o/ org/ 10. 10.1093//mllbe//msttt
Carsten Kemena and Cedric Notredame. Upcoming challenges for multiple sequence alignment methods in the high-throughput era. Bioinformatics (Oxford, England), 25(19):2455-244 2465,, Oc- tober 2009. ISSN 1367-4811. doi: 00.0090hboonnfommaicc////555..
Diederik Kingma and Jimmy Ba. Adam: Method for Stochastic Optimization. December 2014. doi: 10.488500arXiv.44422..o
URL http://s//////.....r////a//// / 1412. 6980v9
M.A. Larkin, G. Blackshields, N.P. Brown, R. Chenna, P.A. McGettigan, H. McWilliam, F. Valentin, L.M. Wallace, A. Wilm, R. Lopez, J.D. Thompson, T.J. Gibson, and D.G. Higgins. Clustal and Clustal X version 2.0. Bioinformatics, (3(21))2947-2944
November 2007. ISSN 1367-4803,
1460-2059. doi: 10. 10..005thiinnfommaicshhnnoo- URL httpss: oup com/ bioinformat cs htt.//orrrtttisssaiiiiocooc 1ooklll-ooookpp/oooo
0t1./09////o// ctsp:///oooioooooaaiicocooo///o hott////ttttttttmmmmm/mmmmm./m 04
S. Quang Le and Olivier Gascuel. An Improved General Amino Acid Replaceement Matrix. Molecu- lar Biology and Evolution, 25(7):1377-1320 April 2008 ISSN 0737-4038, 1537-1719 doi:
1093/molbev/msn007. URL htttt:::/accadmmm crc.aamm...ccg..cccco////rrrrrar
6o1/10.10933/olbev///o
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):36-444,
May 2015. ISSN 0028-0836, 1476-4687. doi: 10. 10.1038/nature145399 URL http::/www.
nature com/ wtt.:////rrttteeee//ttteeeeeeeee
Tianyang Lin, Yuxin Wang. Xiangyang Liu, and Xipeng Qiu. A Survey of Transformers.
arXiv:2106.0455 04554 [cs], June 2021. URL http:://aaaai..or//aa/////// 2106.04554.
arXiv:
Felipe Llinares-López, Quentin Berthet, Mathieu Blondel, Olivier Teboul, and Jean-Phillppe Vert. Deep embedding and alignment of protein sequences. preprint, Bioinformatics, November 1.21. 1111111121111 11. 468653...33
URL
Gil Loewenthal, Dana Rapoport, Oren Avram, Asher Moshe, Elya Wygoda, Alon Itzkovitch, Omer Israeli, Dana Azouri, Reed A Cartwright, Itay Mayrose, and Tal Pupko. A Probabilistic Model for Indel Evolution: Differentiating Insertions from Deletions. Molecular Biology and Evolution, 38(12):5769-5781, December 2021. ISSN 1537-1719. doi: (0.1093/molbev/msab266 URL https:://oii http://////o......0..0...0.. httt////mmeeee////ee//////
Ari Löytynoja. Phylogeny aware aligmment with PRANK. Methods in Molecular Biology (Clifton, N.J.). 1059:155-111171 2014. ISSN 1940-6029, doi: 12110079978-162770--- 10.

---

Published as a conference paper at ICLR 2023
Ari Löytynoja and Nick Goldman. Phylogeny-Awar Gap Placement Prevents Errors in Sequence Alignment and Evolutionary Analysis. Science. 120 1632-165,, June 2008. ISSN 0036- 8075, 1095-9203. doi: 10.1 10.1126/science.115588
URL https:/ www. www.nce.eee........... org/
doi/10. /12//scieccce.eececcccccccc 158395
B. Morgenstern. DIALIGN: multiple DNA and protein sequence alignment at BiBiServ. Nucleic
Acids Research, 32(Web Server):W33 33333333,,3333 July 2004. ISSN 0305-1048, 1362-4962. doi: 10.
1093/nar/gkh:373, URL
http://cccecicccoppppo//o/rr/rra 1ookup//oo
10.1093/ nar///ar///// / gkh373
David A. Morrison. Why Would Phylogeneticists Ignore Computerized Sequence Aligmment? Sys- tematic Biology, 58(1):150-155) February 2009. ISSN 1076-836X, 1063-5157. doi: 10.1093/
sysbiolsyp009. URL httpa://.eeeeelll..........oooor
1675067
Saul B. Needleman and Christian D. Wunsch. A general method applicable to the search for similar- ities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3):443 453, March 1970. ISSN 0022-2836. doi: 10. 11016/002--2836700))9)
Cédric Notredame, Desmond Higgins, and Jaap Heringa. T-coffee: a novel method for fast and accurate multiple sequence alignment 1Edited by Thornton. Journal of Molecular Biology,
302(1):205-217, September 2000. ISSN 00222836. doi: 10. 10000//mi...000004004444 URL https:
//linkinghub. elseeieeeee... com httpa///.aa..aae/ee//aaa///////0
T Heath Ogden and Michael S Rosenberg, Multiple Sequence Alignment Accuracy and Phyloge- netic Inference. Systematic Biology 55(2)314-328, April 2006. ISSN 1063-5157. doi: 10.1080/
106351505005417333 URL /tt/
730
Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng. David Grangier, and Michael Auli. fairseq: Fast, Extensible Toolkit for Sequence Modeling, April 2019. URL 1rXiv:1904.0110 [cs].
http:://ara org/ alte//4/s/999/./../. 01033
Osnat Penn, Eyal Privman, Giddy Landan, Dan Graur, and Tal Pupko. An Alignment Con- fidence Score Capturing Robustness to Guide Tree Uncertainty. Molecular Biology and Evolution, 27(8):1759-177 1767, August 2010. ISSN 0737-4038, 1537-1719. doi: 10.1093/ molbev/msg066. URL https: /wwadaaaaaccccccc wttp./////beeaaaaeeeeeoooooo lookupp/oo 20.1093/molbbv///e
com hbw
Eyal Privman, Osnat Penn, and Tal Pupko. Improving the performance of positive selection in- ference by filtering unreliable alignment regions. Molecular Biology and Evolution, 29(1):155, January 2012. ISSN 1537-1719. doi: 10.:093/molbe//msr117
Tal Pupko and Itay Mayrose. A gentle Introduction to Probabilistic Evolutionary Models, pp. 22, 2020.
Nadav Rakoez, Jeffrey N. Chiang, Muneeswar G. Nittala, Giulia Corradetti, Liran Tiosano, Swetha Velaga, Michael Thompson, Brian L. Hill, Sriram Sankararaman, Jonathan L. Haines, Margaret A. Pericak-Vancee Halperin. Automated identification of clinical features from sparsely annotated 3-dimensional medical imaging. npj Digital Medicine, 4(1):44, December 2021. ISSN 2398-6352. doi: 10. 10.1058/4411466001-00111 s41746 021 00411-11111111
Dwight Stambolian, Srinivas R. Sadda, and Eran
URL httt:://www... http:///www.atttrt. com art cles/
Álvaro Rubio-Largo, Leonardo Vanneschi, Mauro Castelli, and Miguel A. Vega-Rodriguez. Swarm intelligence for optimizing the parameters of multiple sequence aligners. Swarm and Evolutionary Computation, 42:16-28, October 2018. ISSN 22106502. doi: 10.1016/
http://tiiiiinggb.beee.eeseee S.wevo.2018.04.003 URL ott.t///ooo./laaaaaaaaaaaaaaerae
$2210650216304661
Itamar Sela, Haim Ashkenazy, Kazutaka Katoh, and Tal Pupko. GUIDANCE2: accurate detec-
tion of unreliable alignment regions accounting for the uncertainty of multiple parameters. Nu-
cleic Acids Research, 43(W1):77w14, July 2015. ISSN 0305-1048. 1362-4962. doi: 10.
1093/nar/gkv318, URL httptt://ttcaeeeeeee www.ecc..pppcooooooo htt.a/////ttacccecooo/ooo/aaaa lookup/doi/ 10. 70.10993/ar//kv33 8
12

---

Published as a conference paper at ICLR 2023
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, 1lya Sutskever, and Ruslan Salakhutdinov. Dropout: A Simple Way to Prevent Neural Networks from Overfitting. Journal of Machine Learning Research, 15(56):1929-9999 19588, 2014. ISSN 1533-7928. URL http:/ http://jmlz... .rrg/ jm1r..
hapers//15/srivastee 4a htmml
Ilya Sutskever, Oriol Vinyals, and Quoe V. Le. Sequence to Sequence Learning with Neural Net- arXiv: arXiv: 1509.3215
works, December 2014. URL
[cs].
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jonathon Shlens, Zbigniew Wojna. Rethinking the Inception Architecture for Computer Vision, December 2015. URL http:
00567 arXiv:1512.00567 [cs].
Julie D. Thompson, Desmond G. Higgins, and Toby J. Gibson. CLUSTAL W: improving the sensi- tivity of progressive multiple sequence alignment through sequence weighting, position-specinge gap penalties and weight matrix choice. Nucleic Acids Research, 22(22)4473-4688) November 1994. ISSN 0305-1048. doi: 10. 10.10033mar/22..2.4673.
Richard Van Noorden, Brendan Maher, and Regina Nuzzo. The top 100 papers. Nature, 514(7524): 550-553, October 2014. ISSN 1476-4687. doi: 10.1038/514550a
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention Is All You Need, December 2017. URL
http://arxiv..ot www..oog///o....ooooo 03762 arXiv:1706.0376: [cs].
Athanasios Voulodimos, Nikolaos Doulamis, Anastasios Doulamis, and Eftychios Protopapadakis. Deep Learning for Computer Vision: A Brief Review. Computational Intelligence and Neuro- science, 2018:7068349, 2018. ISSN 1687-5273.
doi: 10.1155/2018700683499
Martin Wu, Sourav Chatterji, and Jonathan A. Eisen. Accounting For Alignment Uncertainty in Phylogenomics. PLoS ONE, 7(1)ee30288, January 2012. ISSN 1932-6203. doi: 10.1371/jouraa.
pone.0030288. URL wwtphhttss/// www.dxpppo.....o /ttpppp:///xxpppooooo////0...111
pone. 0030288
Tom Young, Devamanyu Hazarika, Soujanya Poria, and Erik Cambria. Recent Trends in Deep Learning Based Natural Language Processing. November 2018. URL attp:://axxi org/
abs/ bass/100..m 02709
arXiv: 1Xiv:1708.00 1708.02709 [es].
Jia Zhang, Li Xiao, Yufang Yin, Pierre, Hanlin Gao, and Kai Li. A law of mutation: power decay of small insertions and small deletions associated with human diseases. Applied biochemistry and biotechnology, 162(2). September 2010. ISSN 1559-0291. doi: 100100000--0099990 URL https: / wwwpedd. ncbi, nlm. nih. gov/19816659/ Biotechnol.
Publisher: Appl Biochem
13

---

Published as a conference paper at ICLR 2023
A
SUPPLEMENTARY INFORMATION
A.1 SUPPLEMENTARY METHODS
A.1.1 GENERATING TRUE MSAS USING SPARTAABC
We used SpartaABC (Loewenthal et al. 2021 to generate millions of true alignments. SpartaABC
requires the following input: (1) a rooted phylogenetic tree, which includes a topology and branch lengths; (2) a substitution model (amino acids or nucleotides); (3) root sequence length; (4) the indel model parameters, which include: insertion rate (Ry), deletion rate (RD). a parameter for the insertion Zipfian distribution (AA), and a parameter for the deletion Zipfian distribution (Ap). MSAs were simulated along random phylogenetic tree topologies generated using the program ETE version 3.0 (Huerta-Cepas et al. 2016) with default parameters.
We describe the data created for Fig. in Section 3.1 MSAs with ten sequences that were used as training and testing data, respectively. We generated the same number of DNA MSAs. For each random tree, branch lengths were drawn from uniform distribution in the range (0.5, 1.0). Next, the sequences were generated using SpartaABC with the following parameters: R,, RD E (0.0, 0.05), A,, AD E (1.01, 2.0). The alignment lengths as well as the sequence lengths of the tree leaves vary within and among datasets they depend indel dynamics and the root length. The root length was sampled uniformly in the range [32, 44]. Unless stated otherwise, all protein datasets were generated with the WAG+G model, and all DNA datasets were generated with the GTR+G model, with the following parameters: (1) frequencies for the different nucleotides (0.37, 0.166, 0.307, 0.158), in the order "T", "C", "A" and "G", (2) with the substitutions rate (0.444, 0.0843, 0. 16, 0.107, 0.00027), in the order "a", "b", "c", "d", and "e" for the substitution matrix (Fig.
We generated 395,000 and 3,000 protein
the
To
G
A
CiTG
T
axt
d
CTTy
C A
From
b
dæc
fag
C
f
Figure 9: Substitution matrix.
A.1.2 GENERATING LONG MSAS
For the dataset used in Fig. 5 we generated 395,000 and 3,000 protein MSAs with five sequences, which were used as training and testing data, respectively. We generated the same number of DNA MSAs. As we used segments in those datasets, we divided the alignments into smaller pieces (see Section 2.2) with fixed size of 110. Hence, for the protein dataset the number of sentences in the training data was 2,857,364. For the DNA dataset, the number of sentences the training data was 2,424,287. The number of testing segments varies among datasets as it depends on the transformer results of the previous segment. Of note, when using segments, the number of resulting sentences higher than the number of alignments (depending on the alignment length and the segment size). In contrast, when aligning shorter sequences, each alignment is a sentence, We used the same SpartaABC parameters as were used for generating the dataset for Fig. 4 (see Section A.I.II, except for a root length sampled uniformly from the interval [480, 1, 120] and a branch length drawn from a uniform distribution in the range (0.1, 0.15).
A.1.3 EVALUATING ACCURACY OF INFERRED ALIGNMENTS
Alignment accuracy is often quantified by the column score (CS), which counts the number of alignment columns in the inferred alignment that are identical to the "true" alignment (Penn et al.) 2010). We note that we request both the coordinates and the characters of each column to match. For example, consider the case that in a true pairwise alignment, position 17 of the first sequence is an "A", which is matched to an "A" in position 19 of the second sequence. If in the inferred alignment, position 17 of the first sequence matches position 21 in the second sequence, and they are both "A",
14

---

Published as a conference paper at ICLR 2023
this is not considered match as the coordinates are not the same. To normalize this score to the range of [0, 1], we divided the CS by the total number of columns in the true MSA. The CS CS-error is defined as 1.0 CS-score, and thus reflects the level of disagreement between the inferred and true MSAs.
A.1.4 COVERAGE
When the trained BetaAlign is applied to test data, the output a sequence of tokens. It possible for this sequence of tokens to not reflect a biologically meaningful alignment. For example, while an alignment algorithm, in general, should only introduce new gap characters, here, our algorithm sometimes wrongly mutates the characters of the input sequence or outputs an alignment in which the sequences are not of the same length (although, by alignment definition, they should be). We call such an output "invalid alignment". Such cases are illustrated in Fig. 10 A detailed explanation about this metric is at Section 1.1.1
AAG a ACGG
AAG
AAG ACGG
AAG d ACGG
ACGG
AAG/ACGG
AAG/ACGG
AAG/AGGG
AAACGG-G
Transformer
Transformer
Transformer
Transformer
AAGC-GGG
AATC-GGG
AAAC-GG
AAAC-GG
AG-G
AT-G
AA-G
AA-G
ACGG
ACGG
ACG
ACG
Figure 10: Invalid alignments. (a) Although the first input sequence is "AAG" the first row in the resulting pairwise alignment is "AG-G", which is invalid as the algorithm not only introduced gaps but also mutated a character. Here, sequences were encoded using the Concat representation and decoded with Spaces; (b) A similar problem may arise when decoding with Pairs: (c) An example of an invalid pairwise alignment when applying the Concat and Spaces representations, stemming from an unequal length of rows the resulting MSA. Note that this problem can never appear using Pairs; (d) A similar problem may arise in the Crisscross encoding. The different representation schemes are explained in Section A. The transformer architecture illustration is adapted from Vaswani et al. (2017).
It is possible to train several transformers on the same training dataset. These transformers can have different configurations, e.g., as a result of using different optional tunable parameters. One such tunable parameter is, for example. the learning rate. We train a set of transformers on the same training data. is often the case that one transformer outputs an invalid alignment, while others output valid alignment (as measured in Section A.2.3). We use only the valid alignments to determine the final output. The performance of BetaAlign is always computed on the output of the original transformer. We term the percentage of cases for which we can obtain valid alignments as "coverage". The more transformers we use, the higher the "coverage", and thus the higher our confidence in the final output. Of note, using alternative transformers also provides alternative alignments, which can be used, for example, to estimate alignment uncertainty (Wu et al. 2012) Sela et al. 2015).
15

---

In addition to Spaces, we consider alternative decoding for the output alignments, with the corresponding language called Pairs. We note that each column of the output alignment can be Published as a conference paper at ICLR 2023
A.1.5 PREPROCESSING THE INPUT FOR THE MACHINE TRANSLATION TASK
To train the NLP models, we first represent the input unaligned sequences in one of the two source languages, as explained Section A.1.8 (Concat or prisscross) The true MSAs were also represented in the target languages (Pa rs seac. The actual training of the NLPP transform- ers as well as the pre-processing step were done using the Fairseq library (Ott et al. 2019),, which is implemented in Python. Six text files used input for the processsnsnng step before actually running the transformer: unaligned sequences and true MSAs, for training, validation, and testing data.
A. 1.1.6 PREPROCESSING INPUTS AND OUTPUTS
In addition, for running the preprocessing steps, one has to declare names for the input and output languages. Moreover, one can explicitly state if the same dictionary is used for both the source and target languages, i.c., whether joint dictionary should be assumed. In our case, when we apply the combinations of Concat and Spaces or Crisscross and Spaces, the dictionary is joint, while for the combination Concat and Pairs, the dictionary is not joint and hence two different dictionaries are internally generated by the library (one for the source language and the other for the target language). The output of this preprocessing step binary files that are later used as input to the transformer. This preprocess step allows rumning different configurations of the transformers (or potentially, other muchine-learning models) on the same input files, without the need to perform the same computations the input files over and over again.
A.1.7 TRAINING THE TRANSFORMERS
We first assessed various transformer configurations, which differ in their training parameters: max tokens, learning rate and warmup updates. Based on their performance on the pairwise nucleotide and protein alignment datasets (Supplementary Table 2. we selected two optimal transformer con- figurations, which we call "original" and "alternative". The learning rate and warmup values for both transformers are 5E-5 and 3,000, respectively. The max token parameter values are 4,096 and 2,048 for the original and alternative transformers, respectively.
We used label-smoothed cross entropy (Szegedy et al.) 2015) to compute the loss of the model with a dropout (Srivastava et al. (2044) rate of 0.3. We used "Adam" (Kingma & Ba. 2014) as the optimizer of the model with 0.9 forgetting factors for gradients and 0.98 for the and second moments of gradients.
All model evaluations are exccuted on GPU machines, Tesla V100-SXM2-32GB. The Weights and Biases platform (https://wandb.ai) was used to follow the progress of the training steps and helped decide when to stop the learning processes.
A. COMPARING DIFFERENT REPRESENTATIONS
We examined several source and target languages for the sequence-to-sequencc learning task. In ad- dition to Concat (see Section I and we call the corresponding language Crisscross. In this language, the first token is the first character of the first sequence and the second token is the first character of the second sequence. From the perspective of transformer, it helps because it needs to learn closer rather than longer dependencies, compared to Concat. As the input sequences are not necessarily of the same length, gap character ("-") is placed if no more characters are available for one of the sequences. For example, for the example input sequences in Fig. [ ("AAG" and "ACGG"), the input sentence would be "A "AAAGGGG"" G". Thus, the number of tokens is always twice the length of the longest sequence.
we consider another possibility for encoding the input sequences,
one of the following: "AA", "AC", .... "A-". "CA". .... "T-", "-A". ..... "-T". In Pairs, each such possibility is a token. Thus, for nucleotide sequences, the dictionary size is 24. For protein sequences, the dictionary size is 440. Note that "_ (gap and another gap) is illegal token.
16

---

Published as a conference paper at ICLR 2023
We encoded the same datasets with different representations: (1) Concat and Pairs; (2) Concat and Spaces (see Section I (3) Crisscross and Spaces. Then, we trained two transformers on each of the datasets, e.g., two transformers the Concat and Pairs, and two different trans- formers on Concat and Spaces. The transformers were trained with the same tunable parameters. done on
We compared the transformers' performance the same test data. This comparison dataset PD2 (see Supplementary Table 2 Note, that we did not use the Pairs representations when shifting from pairwise multiple alignment because the dictionary of pairwise and multiple alignments are different, which disenables transfer learning.
A.1.9 TRANSFER LEARNING IMPLEMENTATION
In our work, transfer learning was repeatedly used for training the transformers. The first protein transformer was trained on a simple dataset of pairwise amino acid sequences (we denote this dataset "PDI", for protein dataset 1). Its weights were randomly sampled with default values of the Fairseq library. The resulting trained transformer termed "PT1", for protein transformer 1. PT1 was next trained on PD2. resulting in PT2, etc. A similar process was used to train the nucleotide-base transformers (NTI, NT2, etc.) on nucleotide (DNA) datasets (NDI, ND2, etc.) note, transfer learning used in this study only when the previous and the currently processed data are encoded using the same representations, i.e., they share the same dictionaries.
A.1.10 CALCULATING COVERAGE
Each alignment was passed through both the original and alternative transformers. A valid alignment defined by the following rules: (I) All alignment rows are of the same length; (2) When remov- ing all gaps from each row of the alignment, the result equals to the unaligned input sequences. For example, for the unaligned inputs: "AAG" and "ACGG", the inferred alignment, "A-AG" over "ACGG" is valid, whereas for the same input the alignment "A-AG" over "ACGC" is invalid (see Fig. [Op. The coverage defined as the fraction of valid alignments.
A.1.11 GENERATING MISSPECIFICATION ARSEECIFICATION DATASET
To create misspecification datasets, we simulated alignments that have four different regions, each evolving under a different indel model, i.e., each part of the alignment has different indel parameters. The Ry and RD are sampled from the ranges: [0.01, 0.02). [0.02, 0.03). [0.03, 0.04), (0.04, 0.05) for the first, second, third and fourth regions of the alignment, respectively. The Ar and Ad are sampled from the ranges: [1.01, 1.2). [1.2, 1.4), [1.4, 1.6). [1.6, 1.8) for the different regions, respectively. Those values were assumed both when simulating nucleotide and protein datasets. For protein sequences, each region was simulated assuming a different amino-acid replacement matrix: JTT Jones al. 1992). BLOSUM (Henikoff & Henikoff] 1992), mtRTT (Abascal et al., (2007), and LG (Le & Gascuel) 2008), for the first to the fourth domains, respectively. For nucleotide sequences, the GTRI. JC, GTR2, JC, were assumed for each region, respectively (Pupko Mayrose 2020). The GTRI and GTR2 frequencies are (0.37, 0.166, 0.307, 0. 0.158) and (0.265, 0.182, 0.171, 0,382) for the firquency of "T". "C", "A", and "G", respectively. The assume entries in the rate matrix were: (0.444, 0.0843, 0.116, 0.107. 0.00027) and (1.387, 1.79, 0.431, 0.321, 4.947), for "a", "b", "c", "d", and "e" as stated in matrix (see Section Section[..1.I A.I.I). for GTR1 and GTR2, respectively.
A.1.12 EXTRACTING THE ATTENTION MAPS
In the Fairseq library, which we used for training the transformers, there an option to extract the attention map. Since using this option resulted in bug, fixed it by changing the source code of the library. Once the issue was fixed, we could save the attention maps.
A.1.13 COMPARING AGAINST OTHER ALIGNMENT PROGRAMS
We compared BetaAlign against the following programs, used with default parameters: MUSCLE v3.8. 1551 (Edgar 2004). MAFFT v7.475 (Katoh & Standley 2013), PRANK 150003 (Löytynoja & Goldman 2008). T-Coffee Version.12 12.00.7fb084. (Notredame et al. 2000), ClustalW 2.1 (Lrrkin
al. 2007). and DIALIGN dialign2-2 (Morgenstern) 2004).
17

---

Published as a conference paper at ICLR 2023
A.2 SUPPLEMENTARY DISCUSSION
A.2.1 CHARACTERIZING THE ERROR OF DIFFERENT ALIGNERS
To better understand the limitations of the various multiple sequence aligners, analyzed the resulting aligmments with respect to 25 features, e.g., the resulting alignment length, the total number of gaps, and the average gap size. We then compared these features to the true alignment. Fig. []] shows the level the resulting alignment distorts these features as a heatmap. The closest the value to zero, the less biased the aligner is with regard to this feature. For example, a deviation of -0.09 in alignment length means that the aligner tends to produce alignments that are 9% shorter than the aligning). BetaAlign's deviations range from -6% 6% and are lower than other aligners. Other aligners are especially biased with respect to long indels. We hypothesize that this is due to their implicit assumptions regarding the distribution of the indels, which is different from the distributions used to simulate these data.
true alignment
Deterig1
40000
4:30
4.32
0.53
3:05
4.00
-085
4:22
4.31
4.05
-3.01
4:01
0.58
4000
(0:3
0.24
4.53
0.00
-3.00
4.00
0.02
RNAK
0.00
4:30
4.02
0.55
0.01
060
-2.0
3:1
4441
4:81
4003
4:33
5:00
4.03
0.33
6A2
4:33
4:00
3:1
5.26
0.1
040
+2.00
0.00
4.01
533
200
DAUOM
0:00
0.03
0.03
9.00
SOL
5.12
3922
0.22 KIRE
0:23
02
0.40
3.02
DOL
5:05
0:00
2:11
0.08
0.08
0.00
2.01
0.01
9.00
MUSCLE
033
0.58
0.34
0.50
8.04
3.03
8:00
0:27
9.04
0.62
0.22
0.03
2:28
0.22
0.00
5.00
0.05
.000
CARS DUE
NUN SANTEE PEE
SUNE GAN LON IKE
riol FRO yOU SOL 2N TH C045
HOOL poomoooooo WITU MMW.MO0000.0OO c44
TOT JONN LOODOR
CAPS
101 CUPP LPN
Ros 2000
Figure 11: Level of aligmment attributes distorted by different aligners, For each feature and for each alignment, shown the percent deviation comparing the resulting alignment to the true simulated alignment. The data used in this section are SPD12. For detailed description of the features used, see Loewenthal et al. 2021).
A.2.2 TESTING ALTERNATIVE REPRESENTATION SCHEMES
Supplementary Table displays the performance of transformers trained with various encodings for pairwise protein alignment. All six variants had similar accuracy, as measured by the CS-score. The Pairs target language resulted the highest coverage. For the task of multiple sequence align- ments, we decided not to work with the generalization of the Pairs target language because in this case the size of the dictionary increases exponentially with the number of input sequences (if we denote n as the number of input sequences, the output protein dictionary size is 22" 1). Further- more, because the dictionary size depends on n, the Pairs irr target language hinders using transfer learning. Note that the Spaces and Crisscross dictionaries do not change when increasing the number of input sequences, As the performance using the Concat source language was slightly better than that of the Cri sscrosss source language, the former was applied for all analyses.
A.2.3 COVERAGE RESULTS
When generating the results of Fig. in the main text, a small fraction of the resulting alignment was invalid (see Section A.1.4). Changing the tunable parameters of the transformers led to differ- ent deep-learning models. We harnessed this feature of the neural network models and generated an additional transformer for aligning nucleotide sequences as well as additional transformer for aligning protein sequences (we call each of these transformers "alternative".. When we aligned the invalid cases with the alternative transformers, large fraction yielded valid alignments. Thus, ery time the "original" transformer failed, the results of the alternative transformer were considered. This methodology substantially increased the coverage, i.e., the percentage of MSAs that were suc-
18

---

Published as a conference paper at ICLR 2023
Table 1: Transformers performance trained pairwise protein alignments with source and target languages (dataset PD2). Each combination of source and target language was tested with two values for the max-token parameter, resulting in two transformers: "original" and "alternative..
TRANSFORMER NAME
SOURCE LANGUAGE
TARGET LANGUAGE
TOKENS
CS-SCORE
COVERAGE
original
Concat
Paics
4096
0,997
0,939
alternative
Concat
Pairs
2048
0,997
0,952
original
Concat
Spaces
4096
0,997
0.835
alternative original alternative
Concat
Spaces
2048
Crisscross
Spaces
4096
0,991
0.503
Crisscross
Spaces
cessfully aligned. Specifically, the fraction of datasets that could not be aligned was less than 2%
both for nucleotide and protein sequences (Fig. 12
(a)
Nucleotide sequences
original alternative overall
Fraction of invalid alignments [%)
0.06
0.04
0.00
7
Number of input sequences
(b)
Protein sequences
original
0.08
alternative
Fraction of Invalid alignments [%]
0.07
overall
0.06
0.05
0.04
0.03
0.02
0.01
0.00
7
Number of input sequences
The fraction of invalid alignments for nucleotides (a) and protein (b) sequences function of the number of inputs sequences. For each dataset, two different transformers were trained. The fraction of invalid alignments of the "original" and "alternative" transformers in blue and orange, respectively. In green is the fraction of invalid MSAs shared by both transformers.
Figure 12:
19

---

Published as a conference paper at ICLR 2023
Table 2: The generation datasets used in this work. The R and the AI&Ap refer to the indel parameters of the SpartaABC. The root length was sample uniformly from in the range (min- imum sequence length times 0.8, maximum sequence length times 1.1). Datasets names reflect to the order in which the transformers were trained. For example, the first protein transformer was trained on dataset PDI, then the optimized weights were starting point of PD2, etc. Similarly, the nucleotides transformer was first trained on NDI. Tables (a), (b) refer to nucleotide and protein datascts, respectively. Table (c) refers to special datasets (hence the "S" at the start of the dataset name). In this table, datasets SNDI and SPDILG the datasets used create Fig. Of note, dataset SPD1LG was generated with the LG amino-acid replacement matrix. The other datasets, SND2 to SND5 and SPD2 to SPD9 refer nucleotide and protein sequences used for the "seg- mented transformers", respectively. SND6 and SPDI0 refers to the misclassification datasets, and thus, the indel parameters were sampled separately for each "region" (see Section A.I.1I).
DATASET
BRANCH LENGTH
ROOT LENGTH
Ry&Ry
Ay&Ap
INPUT SEQUENCES NUMBER
NDI
0.03
50- 60
0.0-0.55
1.01
ND2
0.03 0.3
100 300
0.0
101-2.0
2
ND3
0.6
1.01-200
ND4
0.3
50- 60
0.04
1.1
3
ND5
0.15
55
0.5
1.0
ND6
0.15
ND)7
0.15
55
0,5
1.5
ND8
0.05
1.01 -2
ND9
0.05
0.03 0.05
1.01
ND10
0.07
45
0.0
1.01 -2
5
NDI1
0.08
37-42
0.03
1.01-2
ND12
0.09
40
0.04
1.3
ND13
0.05
0.02-0.03
1.0
ND14
0.02
1.35 1.45
ND15
0.07-0.1
35 45
0.05
1.01 -2
7
0.07
70
-
DATASET
BRANCH LENGTH
ROOT LENGTH
Ry
Ay&AAp
INPUT SEQUENCES NUMBER
PDI
0.05
40-40
0.0-0.05
1.0
2
PD2
0,05 0.1
70
0.04
-.01-2.0
2
PD3
0.1
200-250
0.04
1.1-2.0
PD4
0.0
30 40
0.0-
1.01 2,0
3
0.2
50
0.04
1.01-20
3
PD6
0.15
50
0.05
1.01
3
PD7
0.15
50
0.05
1.5
3
30
1.01
PD9
0,075
35
0.03
1.07
PDI0
0.04-0.08
40
0.0-0.05
101
5
PDI1
0.04
40-40
0.0-0.05
1.0-2
PD12
0.1
30
0.0-0.05
1.01
6
PD13
30 40
0.03 0.05
1.01
6
PD14
0.0
25 35
0.0-
1.01-2
7
PD15
0.08
0.09
27 32
0.03 0.05
1.01-2
7
PD16
0.09
30
0.04
1.3
7
PD17
0.05 0.1
40
0.0 0.05
1.01
10
PD18
0.07 0.1
25 35
0.04
1.01
7
R,
ArdAA
SIQUEEEEE
SNDI
0.05 -1.
01--115
10
SNI2
0.1-0.1
600- MP0
110-1.05
101 -2
SNDS
0.15
600- 500
0.0-0.05
101
SNDM
100-
08-011
100
SND6
10
SPTI
0.08
0.000.5
1.01 2.0
10
SPOILG
0,55 0.1
40
0.D 0.05
1.01 2.0
10
SPD2
0.08 0.15
2201 200
0.0 0.05
1.01
0.15
130
0.15
SP14
010
1001
SPD6
6.6- 0.2
600 500
0.0 0.05
101
7
SPOT
0.06 11.
600 145
11.0
100
5
SPD6
0.15
600 500
0.0 0.05
LB1
SPD11
0.12
0.0259
0.0155 0035
185
1.799
SPD12
8.7- 0.12
40
Denunic
Dynanic
SPO15
0.07-111 2.12
30
Dyromic
Dynums:
A.2.4 ADDITIONAL DATASETS
The parameters that used to generate the different datasets are listed in Supplementary Table
20

---

Published as a conference paper at ICLR 2023
A.2.5 DATA FOR SPECIFIC FIGURES
To create Fig. and Fig. 12 used the same datasets, SNDI and SNDILG for the nucleotide and protein dataset, respectively. The datasets for Fig. 5 are SNDS and SPD9 for the nucleotide and protein dataset, respectively. We have used SPDI1, SPD12 and SPD13 to create Fig. 6 In Fig. 7 the transformers that we used were trained on datasets SNDI and SPDI. The test datasets that include spatial variation are SND6 and SPD10 for nucleotide and protein datasets, respectively. Shown in Fig. D and Fig. [C are attention maps of different resolutions extracted from one of the protein alignments composed of seven sequences (dataset PD14). Dataset SPD12 was used to create Fig.
21


Reviews:
[{"review_id": "esZ2gDn3g7", "reviewer": "Reviewer_JNkr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work uses sequence-to-seqeunce transformers to align multiple sequences which is an important problem in computational biology.  The approach mainly proposes a scheme to convert multiple seqeunces into one long input sequence and the desired output aligned sequence as the output sequence in the seq2seq setup. The training data for this setup is generated via simulation. To account for long sequences, a heuristic scheme for splitting inputs/outputs into multiple shorter seqeunces is described. An ensemble of transformers is trained where each transformer is trained on the data from a different simulation and this ensemble is used for prediction. Finally, the proposed approach is compared against other commonly used multiple sequence aligners on datasets of neucleotide and protein sequences.", "summary_of_the_review": "The proposed approach is reasonable and the empirical comparison shows its superiority over other baselines. However, more analysis needs to be done and the baselines and experiments should be more thoroughly explained.", "strength_and_weaknesses": "I am not well-versed in computational biology, so I am unable to judge the quality of empirical analysis because I am not sure how effectively the chosen datasets reflect progress in this area, and I am also unaware of the technical details of the baselines and models that are used in comparison. Hence, I will mostly reserve my detailed comments on the proposed technique and the results that are described in the paper.\n\nStrengths:\n\n-- The approach is fairly straightforward to implement, and seems reasonable to try.\n\n-- The results show that the proposed approach is in general better than the baselines when considering the performance across various numbers of sequences to be aligned. Although MUSCLE, and PRANK consistently perform similarly to the proposed approach.\n\n-- The \"model misspecification\" experiment is interesting because it aims to characterize robustness to distributional variaitons in training/test data. The proposed approach does seem robust to the tested misspecification.\n\nWeaknesses:\n\n-- The approach involves several heuristics and is a fairly common instantiation of generic transformer-based sequence to sequence paradigm. Hence, it is low on technical novelty. However, the application domain of computational biology is unusual and I haven't seen the use of this paradigm in the proposed domain.\n\n-- The main contribution of the paper is to develop schemes for flattening multiple sequences into one input sequence and use the aligned sequence as the output sequence. Although, two such schemes are compared, the choice of the scheme seems arbitrary and inadequate analysis/ theoretical justification is provided for the choice.\n\n-- I might be mistaken but it seems like the test data is also synthetically generated. While this would still be fine for comparing approaches, performance on naturally occurring data would strengthen the paper. Also, why not generate test data under all the proposed schemes in Table 2 and measure performance on different kinds of datasets? \n\n-- The paper would benefit from a detailed description of the baselines in the main text so that it is clear how the proposed approach differs from existing approaches.\n\n-- Similar to the point above, more analysis to show how the proposed approach is doing better compared to the baselines would help. Concretely, characterizing the errors various approaches differ in would significantly strengthen the paper. Do the baselines have hyperparameters that could be tuned? Were they tuned for different number of sequences etc.\n\n-- MUSCLE and PRANK seem fairly close to the proposed approach. Interestingly, while the results show them to be competitive/better for neucleotides and worse for protein, the misspecification experiment flips this order. This is interesting and should be studied in detail.\n\n-- Minor point: Instead of using \"words\", please use \"token\" while talking about sequences.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NOawdeKciAy", "reviewer": "Reviewer_AUpf", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to treat multiple sequence alignment task as a machine translation task by processing 'concats' into 'spaces'. It is an interesting idea, and the authors resolve the main obstacle of transformer sequence length limitation with segments.", "summary_of_the_review": "The idea is kind of interesting. However, the motivation is not very clear. Also, the comparison between the proposed method and the traditional MSA methods is not fair. HMM-based methods are missing. The advancement of the method compared to the previous methods is unclear to me. ", "strength_and_weaknesses": "## Major concern\n\n1. Due to the nature of the transformer, there is no guarantee that all input(e.g. ATCG) will be mapped to the output. The MSA will be meaningless if BetaAlign cannot guarantee that input tokens are not corrupted in the resulting alignment.\n2. The experiments are conducted on simulated datasets with few sequences in each MSA. It seems that BetaAlign is more time-consuming than traditional methods since each segment needs to pass the transformer once. The alignment comparison between BetaAlign and traditional ones shows that it is comparable, but it remains a question that why we need deep learning here to achieve similar results but consume more time.\n3. The authors should mention HMM-based methods[1] as well as other ones incorporating profiles.\n4. Datasets based on structural alignment should be used as the benchmark dataset, like BAliBASE. Using simulated data similar to the training set is not fair for traditional ones.\n\n## Minor comments\n\n1. The construction of the training & testing set is ambiguous. Also, the parameters of traditional methods for benchmarking should be stated.\n2. The evaluating metric **SC-error** is confusing. Why not use the original CS (column score) or SPS (Sum-of-pairs score)[2]? I think CS is already normalized.\n3. Latest downstream tasks of MSA like AlphaFold2 for 3D structure prediction use MSA with around one hundred sequences for promising performance. Figure 4 should show the comparison of a more diverse number of input sequences.\n\n[1]  S. R. Eddy, Accelerated profile HMM searches. *PLoS Comp. Biol.*, 7:e1002195, 2011.\n\n[2] Julie D. Thompson, Frédéric Plewniak, Olivier Poch, A comprehensive comparison of multiple sequence alignment programs, *Nucleic Acids Research*, Volume 27, Issue 13, 1 July 1999", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8O5Dbb7s_f", "reviewer": "Reviewer_8ZqM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes using sequence-to-sequence translation from NLP as the core of a Multiple Sequence Alignment. They train their model on phylogenetic simulators and compare against standard alignment methods. ", "summary_of_the_review": "The paper provides an interesting combination of ideas and applies them to the MSA problem. On technical and empirical merit, this is interesting and a good paper. The key weaknesses for the methods usability are somewhat uncovered primarily (1) extension to real data (2)  addressing of compute challenges and (3) how to infer the correct simulator parameters. Furthermore, the exposition is a bit grandiose that sets the reader up for high expectations that detracts from the overall work. More humility in word choice, providing reader context of related work, and defining clearly the set of MSA tasks the method excels in and struggles at would greatly improve the paper.", "strength_and_weaknesses": "Strengths:\n- The paper likely improves the SOTA for some applications of multiple sequence alignments.\n- The paper develops an interesting splitting strategy to apply this method for longer sequences.\n- The leveraging of simulators allows the method to more closely tailor the alignment to the phylogenetic process.\n\nWeaknesses:\n- While model misspecification is addressed in simulator parameter space, it isn't addressed in the mismatch between simulators and real data. An experiment that applies to the \"gold standard\" real alignment data while the model is trained on simulator data would be a vital experiment to convince the reader that the effects won't decay in the sim2real setting as often occurs in genomics, robotics, and vision.\n- Compute can be prohibitive(only applied to a moderate number of sequences) even with the splitting strategy as the number of sequences increases or the number of alignments that need to be performed. Further analysis of compute time(including training) is likely one of the crucial pragmatic aspects of a bioinformatic piece of software that is noticeably missing.\n- The splitting strategy likely will not work multiple sequence local alignments given how to split the sequences will likely be unclear.\n- More discussion around inferring the correct simulator from data would greatly improve the method's viability.\n\nMinor Comment:\n- Providing a more substantial Related Work section in the Main Text would improve its readability and context for this paper.\n- Connection to the likelihood-free inference literature for related works (Beaumont et al 2002[1] where ABC was presented and Chan et al 2018 [2] which combines simulators + deep NNs + sets of sequences). \n\n[1] Beaumont et al (2002). Approximate Bayesian Computation in Population Genetics.\n[2] Chan et al (2018). A Likelihood-Free Inference Framework for Population Genetic Data using Exchangeable Neural Networks.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster