Neural Distance Embeddings for Biological Sequences
Authors: Gabriele Corso
Zhitao Ying
Michal Pándy
Petar Veličković
Jure Leskovec
Pietro Liò
Venue: NeurIPS 2021 Poster (2021)
Keywords: bioinformatics
sequence similarity
hyperbolic embeddings
low-distortion embeddings
metric learning
manifold learning

Abstract: The development of data-dependent heuristics and representations for biological sequences that reflect their evolutionary distance is critical for large-scale biological research. However, popular machine learning approaches, based on continuous Euclidean spaces, have struggled with the discrete combinatorial formulation of the edit distance that models evolution and the hierarchical relationship that characterises real-world datasets. We present Neural Distance Embeddings (NeuroSEED), a general framework to embed sequences in geometric vector spaces, and illustrate the effectiveness of the hyperbolic space that captures the hierarchical structure and provides an average 38% reduction in embedding RMSE against the best competing geometry. The capacity of the framework and the significance of these improvements are then demonstrated devising supervised and unsupervised NeuroSEED approaches to multiple core tasks in bioinformatics. Benchmarked with common baselines, the proposed approaches display significant accuracy and/or runtime improvements on real-world datasets. As an example for hierarchical clustering, the proposed pretrained and from-scratch methods match the quality of competing baselines with 30x and 15x runtime reduction, respectively.

Neural Distance Embeddings for Biological Sequences
Gabriele Corso" MIT
Rex Ying
Michal Pándy University Cambridge
Stanford University
Petar Veličković DeepMind
Jure Leskovec Stanford University
Pietro Liò University of Cambridge
Abstract
The development of data-dependent heuristics and representations for biological sequences that reflect their evolutionary distance is critical for large-scale biological research. However, popular machine learning approaches, based continuous Fuclidean spaces, have struggled with the discrete combinatorial formulation the edit distance that models evolution and the hierarchical relationship that charac- terises real-world datasets. We present Neural Distance Embeddings (NeuroSEED), general framework embed sequences in geometric vector spaces, and illustrate the effectiveness of the hyperbolic space that captures the hierarchical structure and provides an average 22% reduction embedding RMSE against the best competing geometry. The capacity of the framework and the significance of these improve- ments are then demonstrated devising supervised and unsupervised NeuroSEED approaches to multiple core tasks in bioinformatics. Benchmarked with common baselines, the proposed approaches display significant accuracy and/or runtime improvements on real-world datasets. As example for hierarchical clustering, the proposed pretrained and from-scratch methods match the quality of competing baselines with 30x and 15x runtime reduction, respectively.
Introduction
Over the course of evolution, biological sequences constantly mutate and a large part of biological research is based on the analysis of these mutations. Biologists have developed accurate statistical models to estimate the evolutionary distance between pairs of sequences based on their edit distance D(s1. s2): the minimum number of (weighted) insertions. deletions or substitutions required to transform string into another string 82.
However, the computation of this edit distance kernel D with traditional methods is bound quadratic complexity and hardly parallelizable, making its computation a bottleneck in large scale analyses, such microbiome studies 3 Furthermore, the accurate computation of similarities among multiple sequences, at the foundation of critical tasks such as hierarchical clustering and multiple sequence alignment, is computationally intractable even for relatively small numbers of sequences. Problems that in other spaces are relatively simple become combinatorially hard in the space of sequences defined by the edit distance. For example, finding the Steiner string, a classical problem in bioinformatics that can be thought of as computing the geometric median in the space of sequences, is NP-complete.
widely used bioinformatics for these tasks are inteiindeeennnnt and, therefore, cannot exploit the low-dimensional manifold assumption that characterises real-world data 8 10 Leveraging the available data to produce efficient and data-
Classical algorithms and heuristics 4 5
"Correspondence to gcorsoêmit.edu
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

AGTTCATCACT
Decoder ge
Sheep
Platyfish
Hlunder
Whale Pig
Dog
Freq
Human Monkey
Rabbbit
Catfish
Guinea-pia
Barbel
Trout
Encoder fo
Rat
Mouse
Hamsster
ACATCATCAGT
CGATCATGCAT
distance
Figure On the left, the key idea of NeuroSEED: learn an encoder function fo that preserves distances between the sequence and vector space (D and d). The vector space then be used to study the relationship between sequences and, potentially, decode new ones (see Section 7.2p. On the right, example of the hierarchical clustering produced the Poincaré disk. The data was downloaded from UniProt 14 and consists of the P53 tumour protein from 20 different organisms.
dependent heuristics and representations would greatly accelerate large-scale analyses that are critical
biological research.
While the number of available biological sequences has grown exponentially over the past decades, machine learning approaches to problems related to string matching [2] 12 have not been adopted widely bioinformatics due to their limitation in accuracy and speed. In contrast to most tasks in computer vision and NLP, string matching problems are typically formalised as combinatorial optimisation problems. These discrete formulations do not fit well with the current deep learning approaches. Moreover, representation learning methods based Euclidean spaces struggle to capture the hierarchical structure that characterises real-world biological datasets due to evolution. Finally, common self-supers supervvpe learning approaches, very successful in NLP, are less effective in the biological context where relations tend to be between sequences rather than between bases [3].
In this work, we present Neural Distance Embeddings (NeuroSEED), a general framework to produce representations for biological sequences where the distance in the embedding space correlated with the evolutionary distance D between sequences. NeuroSEED provides fast approximations of the distance kernel D, now-dimensional representations for biological sequences, tractable analysis of the relationship between multiple sequences in the embedding geometry and way to decode novel sequences.
Firstly, we reformulate several existing approaches into NeuroSEED highlighting their contributions and limitations. Then, we examine the task of embedding sequences to preserve the edit distance that is the basis of the framework. This analysis reveals the importance of data-dependent approaches and of using geometry that matches the underlying data distribution well. The hyperbolic space is able to capture the implicit hierarchical structure given by biological evolution and provides an average 22% reduction in embedding RMSE against the best competing geometry.
We show the potential of the framework and its wide applicability by analysing two fundamental tasks in bioinformatics involving the relations between multiple sequences: hierarchical clustering and multiple sequence alignment. For both tasks, unsupervised approaches using NeuroSEED encoders are able to match the accuracy of common heuristics while being orders of magnitude faster. For hierarchical clustering, we also explore a method based on the continuous relaxation of Dasgupta's 's cost the hyperbolic space which provides 15x runtime reduction at similar quality levels. Finally, for multiple sequence alignment, we devise original approach based on variational autoencoders that matches performance of competitive baselines while significantly reducing the runtime complexity.

---

As a summary our contributions are: (i) We introduce NeuroSEED, general framework to map sequences in geometric vector spaces, and reformulate existing approaches into it. (ii) We show how the hyperbolic space can bring significant improvements to the data-dependent analysis of biological sequences. (iii) We propose several heuristic approaches classical bioinformatics problems that can be constructed on top of NeuroSEER embeddings and provide significant running time reduction against classical baselines.
2 Bioinformatics tasks
The field of bioinformatics has developed a wide range of algorithms to tackle the classical problems that we explore. Here we present the tasks and briefly mention their motivation and some of the baselines we test. More details are provided in Appendix B
Edit distance approximation In this work, we always deal with the classical edit distance where the same weight given to every string operation, but all the approaches developed can be applied to any distance function of choice (which is given as an oracle). For example, when using amino acid sequences,
of the different metric variants of the classical substitution matrices such as mPAM250 [13] would be a good choice. As baseline approximation heuristics, we take k-mer [5], which is the most commonly used alignment-free method and represents sequences by the frequency vector of subsequences of certain length, and FFP [16), another alignment-free method which looks the SaasnnnShannon divergence between distributions of k-mers.
Hierarchical clustering (HC) Discovering the intrinsic hierarchical structure given by evolutionary
history is a critical step of many biological analyses. Hierarchical clustering (HC) consists of, given a pairwise distance function, defining tree with internal points corresponding clusters and leaves to datapoints. Dasgupta's cost 17 measures how well the tree generated respects the similarities between datapoints. As baselines we consider classical agglomerative clustering algorithms (Single
18]. Complete 19 and Average Linkage [6]) and the recent technique (20) that uses a continuous relaxation of Dasgupta's 's cost in the hyperbolic space.
Multiple sequence alignment (MSA) Aligning three or sequences is used for the identifica- tion active and binding sites as well as conserved protein structures, but finding its optimal solution NP-complete. A related task MSA is the approximation of the Steiner string which minimises the sum of the distances (consensus error) to the sequences in a set.
Datasets To evaluate the heuristies we chose three datasets containing different portions of the 16S rRNA gene, crucial in microbiome analysis (21) one of the most promising applications of our approach. The first, Qiia [21], contains more than 6M sequences of up to 152 bp that cover the V4 variable region. The second, RT988 (II), has only 6.7k publicly available sequences of length up to 465 bp covering the V3-V4 regions. Both datasets were generated by Illumina MiSeq [22] and contain sequences of approximately the same length. Qiita was collected from skin, saliva and faeces samples, while RT988 was from oral plaques. The third dataset the Greengenes full-length 16S rRNA database 23), which contains more than 1M sequences of length between 1,111 to 2,368. Moreover, we used dataset of synthetically generated sequences to test the importance of data-dependent approaches. A full description of the data splits for each of the tasks is provided in Appendix B.4
Neural Distance Embeddings
The underlying idea behind the NeuroSEED framework, represented in Figure [ is to map sequences in a continuous space so that the distance between embedded points is correlated the one be- tween sequences. Given distribution of sequences and distance function D between them, any NeuroSEED approach is formed by four main components: an embedding geometry, an encoder model. a decoder model, and a loss function.
Embedding geometry The distance function d between the embedded points defines the geometry of the embedding space. While this factor has been mostly ignored by previous work [T] 24 25
26 27 we show that it is critical for this geometry to reflect the relations between the sequences in the domain. our experiments, we provide comparison between Fuclidean, Manhattan, cosine, squared Euclidean (referred to Square) and hyperbolic distances (details in Appendix D)
3

---

Encoder model The encoder model fo maps sequences to points in the embedding space. In this work we test variety of models as encoder functions: linear layer, MLP, CNN. GRU 2 and transformer [29] with local and global attention. The details on how the models are adapted to the sequences are provided Appendix [ Chen et al. (24] proposed CSM, an encoder architecture based on the convolution of subsequences. However, as also noted by Koide ef al. [12,, this model does not perform well when various layers are stacked and, due to the interdependence cells in the dynamic programming routine, it cannot be efficiently parallelised on GPU.
For some tasks it is also useful to decode sequences from the embedding space. This idea, employed in Section 7.2 and novel among the works related to NeuroSEED, enables to apply the framework to a wider set of problems.
Decoder model
Loss function
The simplest way train NeuroSEED encoder is directly minimise the MSE between the sequences' distance and its approximation as the distance between the embeddings:
L( Σ (D(s1, - a d(fe(s)). fo(
(1)
$1.82ES
where a is a constant or learnable scalar. Depending on the application that the learned embeddings used for, the MSE loss may be combined substituted with other loss functions such as the triplet loss for closest string retrieval (Appendix[F) the relaxation of Dasgupta's 's cost for hierarchical clustering (Section 7.1 or the sequence reconstruction loss for multiple sequence alignment (Section 7.2).
There are least five previous works 24 25
that have used approaches that can be described using the NeuroSEED framework. These methods, summarised in Table [ show the potential of approaches based the idea of NeuroSEED, but share two significant limitations. The first is the lack of analysis of the geometry of the embedding space, which we show to be critical. The second is that the range of tasks is limited to edit distance approximation (EDA) and closest string retrieval (CSR). We highlight how this framework has the flexibility to be adapted to significantly more complex tasks involving relations between multiple sequences such as hierarchical clustering and multiple sequence alignment.
26
Table I: Summary of the previous and the proposed NeuroSEED approaches. EDA stands for edit distance approximation and CSR for closest string retrievals. For experiments, in the columns geometry and encoder we report those that performed best among the ones tested.
Method
Geometry
Encoder
Decoder
Loss
Tasks
Zheng et al.
I1
Jaccard
CNN
X
MSE
EDA
Chen al.
Cosine
CSM
X
MSE MAE triplet
EDA
Zhang et al.
25
Euclidean
GRU
X
EDA & CSR
Dai et al.
26
Euclidean
CNN
X
MAE triplet
EDA & CSR
Gomez et al.
(27
Square
CNN
X
MSE
EDA & CSR
Section
Hyperbolic
CNN & transformer
X
MSE MSE
EDA
Section
Hyperbolic
CNN & transformer
X
HC & MSA
Section
Hyperbolic
Lincar
X
Relaxed Dasgupta
HC
Section
Cosine
Linear
V
MSE + reconstr.
MSA
Appendix
Hyperbolic
CNN & transformer
X
MSE & triplet
CSR
4
Related work
Hyperbolic embeddings Hyperbolic geometry is a non-Euclideas geometry with constant negative sectional curvature and is often referred to continuous version of tree for its ability embed trees with arbitrarily low distortion. The advantages of mapping objects with implicit or explicit
hierarchical structure in the hyperbolic space have also been shown other domains (3 31 32 10
In comparison, this work deals with very different space defined by the edit distance in biological sequences and, unlike most of the previous works, we do not only derive embeddings for a particular set of datapoints, but train an encoder to map arbitrary sequences from the domain in the space.

---

Sequence Distance Embeddings The clear advantage of working in more computationally tractable spaces has motivated sigmificant research Sequence Distance Embeddings
[33
(also known
as low-distortion embeddings) approaches to variants of the edit distance 34
35
36
38
39
40)
However, they are data-independent and have shown weak performance on 'ncoonstrinned
edit distance.
Hashing and metric learning NeuroSEED also fits well into the wider research on learning to hash [1], where the goal typically to map a high dimensional vector space into smaller one preserving distances. Another field related to NeuroSEED is metric learning 42) 43 where models
are trained to learn embeddings from examples of similar and dissimilar pairs.
Locality-sensitive hashing Finally, the work presented is complementary to the line of research in pecality-sensitive hashing methods. Researchers have developed series of heuristics especially for the tasks of sequence clustering 44 455 and local alignment [46]. These use as subroutines embeddings/feature based on alignment-based the limitations we highlight in the paper. Future work could analyse how to improve these heuristics with NeuroSEED embeddings.
alignment- -fre methods, and therefore, fall into
5 Edit distance approximation
In this section we tes the performance of different encoder models and distance functions to preserve an approximation of the edit distance in the NeuroSEED framework trained with the MSE loss. To make the results more interpretable and comparable across datasets, report results using % RMSE:
100 VL(0,))
100
% RMSE(0,
Σ (ED(s), - (((o(s)) $1.9
n
where n the maximum sequence length. This can be interpreted as an approximate average error in the distance prediction as percentage of the size of the sequences.
RT988
Qlita
Greengenes
Model
Baseline
Hyperbolic
Baseline
Hyperbolic
Baseline
Hyperbolic Training/Inference Innference
NW alignment
17.5h
6.01
5.93
7s/
5-mer
1.41
5.03
3.60
29s 29s
6-mer
1.47
5.72
3.15
118s / 118s
FFP
12.03
20.42
10.26
360s/ 360s
FFP
11.86
17.53
8.63
679s/ / 679s
16.16
14.13
1274s
Linear
21. 86
0.51:0.01
4.39:0.09
2.50sc.01
1155, 74418.34
2. 2.70s0.01
1.1h 3s
MLP
1.10c0.05
0.59:0.20
4.36:0.19
1.85e0.02
4.38
2.53+o.01
0.9h / 3s
0.58x0.0s
0.59-0.01
2.68:0.06
1.56:0.01
1.37.0.04
1.00:0.01
2.1h 6s
GRU
1.10:0.11
2.56:3.33
3.30.0.06
2. 2.60,0.16
1.61+0.00
1.18+0.16
7.4h 65s
Global T.
2.09
1.91,0.07
2.2h / 3s
Local
0.57.0.00
0.45:0.01
2.42.0.02
1. 1.8610.02
1.85x0.04
1. 1.89.0.05
2.0h 3s
Figure 2: % RMSE test set results (4 runs). All neural models have an embedding space dimension of 128. The baseline geometries were chosen by best average performance and correspond to cosine distance for k-mers, Jensen-Shaaee Shannon divergence for FFP and Euclidean distance for the neural models. The baselines CNN and GRU correspond, therefore, with [26] and 25 The training and inference time comparisons provided in the Greengenes dataset are shown for set of 5k sequences and were all run on CPU (Intel Core i7) with the exception of the neural models' training that was run GPU (GeForce GTX TITAN Xp). The distance function used does not significantly impact the runtime of any of the models. all the tables: T. stands for transformer, indicates that not applicable or the model did not converge. bold the best results and the green-to-white colour scale the range of results bost-to-worst. Full results for every geometry can found Figure T0 in Appendix
"Code, datasets and tuned hyperparameters be found wbbnss//gttubb.co//goo///unansss
5

---

5-mer Cosine
CNN Euclidean
CNN Hyperbolic
0.7
0.6
Real distance
0.0
0.2
0.4
0.5
0.6
Predicted distance
Predicted distance
Predicted distance
Figure 3: Qualitative comparison in the Qiita dataset between the best performing bascline (5-mer with cosine distance) and the CNN in the Euclidean and hyperbolic space. For every test set sequence pair, predicted real distances plotted, the darkness represents the density of points. The CNN model follows much more tightly the red line of the oracle across the whole range of distances the hyperbolic space.
Data-dependent vs data-independent methods Figures 2 and 3 show that, across the datasets and the distance functions, the data-dependent models learn significantly better representations than iata-independent baselines. The main reason for this is their ability to focus on and dedicate the embedding space to manifold of much lower dimensionality than the complete string space. This observation is further supported by the results in Appendix D where the same models are trained on synthetic random sequences and the data-independent baselines are able to better generalise.
Our analysis also confirms the results from Zheng el al. [1]] and Dai et al. [26] which showed that convolutional models outperform feedforward and recurrent models. We also show that transformers. even when with local attention, produce. in many cases, better representations. Attention could provide significant advantages when considering more complex definitions of distance that include, for example, inversions 47 duplications and transpositions 48
Hyperbolic space The most interesting and novel results come from the analysis of the geometry of the embedding space. In these biological datasets, there an implicit hierarchical structure that is well reflected by the hyperbolic space. Thanks to this close correspondence even relatively simple models perform very well with the hyperbolic distance. In convolutional models, the hyperbolic space provides 22% average RMSE reduction against the best competing geometry for each model.
The benefit of using the hy- perbolic space clear when analysing the dimension required (Fgguee(). The hyperbolic space provides significantly more ef- ficient embeddings, with the model reaching the 'elbow' at dimension 32 and matching the performance of the other spaces with dimension 128 with only 4 16. Given that the space to store the embeddings and the time to compute distances be- tween them scale linearly with dimension, this provides significant improvement in downstream tasks over other NeuroSEED approaches.
5.5
4.5
Cosine
Euclidean
Square
Manhattan
2.5
Hyperbolic
1.5
0
40
80
100
120
Embedding dimension
Figure 4: Edit distance approximation RMSE on Qiita dataset for global transformer with different distance functions.

---

Running time The computational complexity of approximating the pairwise distance matrix for N sequences of length M is reduced from O(N2 M log M) ) to ON + NV) assuming constant embedding size and a model linear with respect to the sequence length. This translates into a very significant runtime improvement even when comparing only 5000 sequences, as can be seen from the last column in Figure 2 Moreover, while the training takes longer than the baselines due to the more complex optimisation, in applications such as microbiome analysis, biologists typically analyse data coming from the same distribution (e.g. the 16S rRNA gene) for multiple individuals, therefore the initial cost would be significantly amortised.
6 Unsupervised heuristics
In this section, we show how competitive heuristics for hierarchical clustering and multiple sequence alignment can be built on the low-distortion embeddings produced by the models trained in the previous section.
Hierarchical clustering Agglomerative clustering, the most commonly used class of HC algo- rithms, can be accelerated when run directly on NeuroSEED embeddings produced by the pretrained model. This reduces the complexity to generate the pairwise distance matrix from ( M2 log M) to ON (M + N)) and allows to accelerate the clustering itself using geometric optimisations like Decalit--sensiivve hashing.
We test models with no further tuning from Section 5on a dataset of 10k unseen sequences from the Qiita dataset. The results (Figure show that there is no statistical difference in the quality of the hierarchical clustering produced with ground truth distances compared to that with convolutional or attention hyperbolic NeuroSEED embeddings. Instead, the difference in Dasgupta's cost between different architectures and geometries is statistically significant and results gap when these trees used for tasks such MSA shown below. The total CPU time taken to construct the tree is reduced from more than 30 minutes to less than one in this dataset and the difference gets significantly larger when scaling to datasets of more and longer sequences.
large performance
Model
Cosine
Euclidean
Square
Manhattan
Hyperbolic
4-mer
0.261
0.260
0,242
0.191
0.299
Baselines
Linear
0.062:0.007
0.172x0.086
0.15340.037
0.177:0.026
0.028=0.005
Single
0.628
MLP
0.16910.054
0.095s0.021
0.28910.094
0.178:0.029
0.03520.004
Complete L.
0.479
CNN
0.028c0.00
0.030=0.004
0.067:0.022
0.081:0.047
0.004:0.015
Average L.
0.000
GRU
0.042+0.005
0.068+a.010
0.059+0.015
0.066:0.043
Global T.
0.032+0.014
0.003 .os
0.038+2.005
0.002:0.003
0.000s0.006
Local T.
0.03510.003
0.02240.008
0.03410.00s
0.02210.003
0.000z0.007
Figure 5: Average Linkage % increase in Dasgupta's cost of NeuroSEED models compared to the performance clustering on the ground truth distances, ubiquitously used in bioinformatics. Average Linkage was the best performing clustering heuristic across all models.
Multiple sequence alignment Clustal, the most popular MSA heuristic, is formed by a phyloge- netic tree estimation phase that produces a guide tree then used by progressive alignment phase to compute the complete alignment. However, the first of the two phases, based hierarchical clustering, is typically the bottleneck of the algorithm. On 1 1200 RT988 sequences (used below), the construction of the guide tree takes 35 minutes compared to 24s for the progressive alignment. Therefore, it can be significantly accelerated using NeuroSEED heuristics to generate matrix and guide tree. In these experiments, we construct the running the Neighbour Joining algorithm (NJ) [49 on the NeuroSEED embeddings and then pass it on the Clustal command-line routine that performs the alignment and returns an aligmment score.
Again, the results reported in Figure 6 show that the alignment scores obtained when using the NeuroSEED heuristics with attention models are not statistically different from those obtained with
3 'Computing the pairwise distance matrix of set of sequences is critical step of many algorithms including the analysed in the next section.
7

---

the ground truth distances. Most of the models also show relatively large variance in performance across different runs. This has positive and negative consequences: the alignment obtained using single run may not be very accurate, but, by training ensemble of models and applying each of them, we are likely to obtain significantly better alignment than the baseline while still only taking a fraction of the time.
Model
Cosine
Euclidean
Hyperbolic
Linear
60.6:35.1
111.3+3.6
57.5+22.0
MLP
72.3+11.8
53.6+3.1
.11.7=18.9
CNN
31.0#16.2
4.7s9.7
-16.3x16.1
Global T.
39.4+74.3
1.9:3.8
31.1+21.8
31.9:30.5
8.6+14.1
-20.147.3
Figure 6: Percentage improvement (average of runs) in the alignment cost (the lower the better) returned by Clustal when using the heuristics to generate the tree as opposed to its default setting using NJ on real distances.
7
Supervised heuristics
In this section propose and evaluate two methods to adapt NeuroSEED the tasks of hierarchical clustering and multiple sequence alignment with tailored loss functions.
7.1 Relaxed approach to hierarchical clustering
An alternative approach to hierarchical clustering uses the continuous relaxation 20 of Dasgupta's cost [17 as loss function to embed sequences the hyperbolic space (for more details see Appendix B.2 and (20). In comparison to Chami el al. (20), we show that it is possible to significantly decrease number pairwise distances required by directly mapping the sequences into the space. This allows to considerably accelerate the construction, especially when dealing with large number of sequences without requiring any pretrained model. Figure [ shows an example the relaxed approach when applied to small dataset of proteins.
RT988 dataset
Qiita dataset
0.35%
2.5%
incresse Dasgupts's cost
0.30%
0.20%
1.5%
0.15%
1.0%
0.10%
0.00%
0.0%
VN
N
VN
N*2
VN
N VN
N*2
Pairwise distances
Pairwise distances
Embeddings
Embeddings
10
Linear
Linear 10
Single Linkage
Complete Linkage
Average Linkage
Figure 7: Average Dasgupta's 's cost of the various approaches with respect to the number of pairwise distances used the RT988 and Qiit datasets. The performances are reported as the percentage increase in cost compared the one of the Average Linkage (best performing). Embedding refers to the baseline (20 while Linear to the relaxed NeuroSEED approach. The attached number represents the dimension of the hyperbolic space used.
The results, plotted in Figure 7 show that a simple linear layer mapping sequences to the hyperbolic space is capable of obtaining with only N pairwise distances very similar results to those from

---

agglomerative clustering (N² distances) and hyperbolic embedding baselines (NVN distances). In the RT988 dataset this corresponds to, respectively, 6700x and 82x fewer labels and leads reduction of the total running time from several hours (>2.5h on CPU for agglomerative clustering. 1-4h on GPU for hyperbolic embeddings) to less than 10 minutes on CPU for relaxed NeuroSEED approach (including label generation, training and tree inference) with no pretraining required. Finally, using more complex encoding architectures such as MLPs or CNNs does not provide significant improvements.
7.2 Steiner string approach to multiple sequence alignment
An alternative approach to multiple sequence alignment uses a decoder from the vector space to in continuous optimisation task.
convert the Steiner string approximation problem (Appendix B.3
This method, summarised in Figure and detailed Appendix G consists of training an autoencoder to map sequences to and from continuous space preserving distances using only pairs of sequence at a time (where caleulating the distance is feasible). This is achieved by combining the loss function component for the latent space edit distance approximation and one for the reconstruction accuracy of the decoder. The first is expressed as the MSE between the edit distance and the vector distance in the latent space. The second consists of the mean element-wise cross-entropy loss of the decoder's outputs with the real sequences. At test time the encoder embeds all the sequences in the set, the geometric median point (minimising the sum of distances in the embedding space) is found with relatively simple optimisation procedure and then the decoder used to find an approximation the Steiner string. During training. Gaussian noise is added to the embedded point in the latent space forcing the decoder to be robust to points not directly produced by the encoder.
ACATCATCAGT
CGATCATGCAT
Training
ACTCATCTATCA
Testing
Decoder
Decoder
Sequence
reconstruction
loss
Edit distance approximation loss
Encoder
Encoder
ACATCATCAGT
CGATCATGCAT
CGATCATGEAT
CGATCATGCAT
ACATCATCAGT
ACTGATCATG
Figure 8: Diagram for the Steiner string approach multiple sequence alignment. On the left, the training procedure using pairs of sequences and a loss combining edit distance approximation and sequence reconstruction. On the right the extrapolation for the generation of the Steiner string by decoding the geometric median in the embedding space.
As baselines, report the average consensus error (average distance to the strings in the set) obtained using: a random sequence in the set (random), the centre string of the set (centre) and two competitive greedy heuristics (greedy-1 and greedy-2) proposed respectively by (50 and [1].
Baselines
Model
Cosine
Euclidean
Square
Hyperbolic
Random 75.98
Linear
59.41s0.11
59.96+0.27
60.53+0.49
60.89+0.82
Centre
62.52
MLP
60.80+0.35
60.00+0.18
59.81+0.22
59.86+0.12
Greedy-1
59.43
CNN
60.96=0.45
60.20=0.26
60.76:1.09
60.48:0.52
Greedy-2
59.41
Figure 9: Average consensus error for the baselines (left) and NeuroSEED models (right).

---

The results show that the models consistently outperform the centre string baseline and are close to the performance of the greedy heuristics suggesting that they are effectively decoding useful information from the embedding space. The computational complexity for N strings of size M is reduced from O(2 / log M) for the centre string and O(N2M) for the greedy baselines to O(NM) for the proposed method. Future work could employ models that directly operate in the hyperbolic space [2 to further improve the performance.
Conclusion
In this work, proposed and explored Neural Distance Embedddings, framework that exploits the recent advances in representation learning to embed biological sequences in geometric vector spaces. By studying the capacity to approximate the evolutionary edit distance between sequences, we showed the strong advantage provided by the hyperbolic space which reflects the biological hierarchical structure.
We then demonstrated the effectiveness and wide upplicability of NeuroSEED on the problems of hierarchical clustering and multiple sequence alignment. For each task, we experimented with two different approaches: one unsupervised tying NeuroSEED embeddings into existing heuristics and second based on direct exploitation of the geometry of the embedding space via tailored loss function. In all cases, the proposed approach performed on par with or better than existing baselines while being significantly faster.
Finally, NeuroSEED provides representations that are well suited for human interaction as the em- beddings produced can be visualised and easily interpreted. Towards this goal, the very compact representation of hyperbolic spaces of critical importance [TO]. This work also opens many oppor- tunities for future research direction with different types of sequences, labels, architectures and tasks. We present and motivate these directions in Appendix A
Acknowledgements
The authors thank Saro Passaro for his insightful comments and suggestions and Frank Stajano, Andrei Margeloiu, Hannes Stärk and Cristian Bodnar for their review of the manuscript.
Disclosure of Funding
G.C. is funded by the Robert Shillman (1974) Fellowship at MIT. P.V. is a Research Scientist at DeepMind. J.I. is a Chan Zuckerberg Biohub investigator. We also gratefully acknowledge the support of DARPA under Nos. HR001 12190039 (TAMI), N66001 1924033 (MCS); ARO under Nos. W911NF-16-D 1--442 (MURI), W91 1991NFF16-11 16-1-017 (DURIP); NSF under Nos. OAC-18355 (CINES), 19345193578 (HDR), CCF- 1918940 (Expeditions), IIS 2030477 (RAPID), NIH under No. R56LM013365. Stanford Data Science Initiative, Wu Tsai Neurosciences Institute, Chan Zuckerberg Biohub, Amazon, JPMorgan Chase, Docomo, Hitachi, Intel, JD. com, KDDI, NVIDIA, Dell, Toshiba, Visa, and UnitedHeallth Group.
References
[1] Hila Sberro, Brayon J Fremin, Soumaya Zlitni, Fredrik Edfors, Nicholas Greenfield, Michael P Snyder, Georgios A Pavlopoulos, Nikos C Kyrpides, and Ami S Bhatt. Large-scale analyses of human microbiomes reveal thousands of small, novel genes. Cell, 2019.
[2] Edoardo Pasolli, Francesca De Filippis, Italia E. Mauriello, Fabio Cumbo, Aaron M Walsh, John Leech, Paul D Cotter, Nicola Segata, and Danilo Frcolini. Large-scale gide analysis links lactic acid bacteria from food with the gut microbiome. Nature communications, 2020.
[3] Alexander Kurilshikov, Carolina Medina-Gomed Rodrigo Bacigalupe. Djawad Radjabzadeh, Jun Wang. Ayse Demirkan, Caroline Le Roy, Juan Antonio Raygoza Garay, Casey T Finnicum, Xingrong Liu, et al. Large-scale association analyses identify host factors influencing human gut microbiome composition. Nature Genetics, 2021.
[4] Saul B Needleman and Christian D Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of molecudar biology. 1970.
10

---

[5] Samuel Kariin and Chris Burge. Dinucleotide relative abundance extremes: a genomic signature. Trends in geneticx, 1995.
[6] Robert R Sokal. A statistical method for evaluating systematic relationships. Univ. Kansas, Sci. Bull., 1958.
[7] Ramu Chenna, Hideaki Sugawara, Tadashi Koike, Rodrigo Lopez, Toby J Gibson, Desmond G Higgins, and Julie D Thompson. Multiple sequence alignment with the Clustal series of programs. Nucleic acids research, 2003.
[8] Archit Verma and Barbara E Engelhardt. A robust nonlinear low-dimensional manifold for single cell ma-seq data. BMC bioinformaties, 2020.
[9] Richard C Tillquist. Low-dimensional representation of biological sequence data. In Proceedings of the 10th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics, 2019.
[10] Anna Klimovskaia, David Lopez- Paz, Léon Bottou, and Maximilian Nickel. Poincaré maps for analyzing complex hierarchies in single-cell data. Nature communications, 2020.
[11] Wei Zheng, Le Yang, Robert J Genco, Jean Wactawski- Wendd, Michael Buck, and Yijun Sun. SENSE: Siamese neural network for sequence embedding and alignment-fres comparison. Bioinformatics, 2019.
[12] Satoshi Koide, Keisuke Kawano, and Takuro Kutsuna. Neural edit operations for biological sequences. In NeurIPS, 2018.
[13] Matthew McDermott, Brendan Yap, Peter Szolovits, and Marinka Zitnik. Rethinking relational encoding in language model: Pre-training for general sequences. arXiv preprint arXiv:2103. 10334, 2021.
[14] UniProt Consortium. Uniprot: hub for protein information. Nucleic acids research, 2015.
[15] Weijia Xu and Daniel Miranker. metric model of amino acid substitution. Bioinformatics. 2004.
[16] Gregory E Sims, Se- Ra-Ran Jun, Guohong A Wu, and Sung- Hou Kim. Alignment-fiee genome comparison with feature frequency profiles (FFP) and optimal resolutions. Proceedings of the National Academy of Sciences, 2009.
[17] Sanjoy Dasgupta. A cost function for similarity- hierarchical clustering. In Proc. Annual ACM SIGACT Symposium Theory of Computing, 2016.
[18] Kazimierz Florek. Jan Lukaszewicz. Julian Perkal, Hugo Steinhaus, and Stefan Zubrzycki. Sur la liaison et la division des points d' d'un ensemble fini. In Colloquium mathematicum, 1951.
[19] Thorvald Julius Sørensen, A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application analyses of the vegetation Danish commons. 1948.
[20] Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré. From trees to continuous embeddings and back: Hyperbolic hierarchical clustering. In NeurlPS, 2020.
[21] Jose Clemente, Erica C Pehrsson, Martin Blaser, Kuldip Sandhu, Zhan Gao, Bin Wang. Magda Magris, Glida Hidalgo, Monica Contreras, Óscar Noya-Alarcón, et al. The microbiome of uncontacted amerindians. Science advances, 2015.
[22] Rupesh Kanchi Ravi, Kendra Walton, and Mahdich Khosroheidari. Miseq: next generation sequencing platform for genomic analysis. Disease gene identification, 2018.
[23] Daniel McDonald, Morgan N Price, Julia Goadrich, Eric P Nawrocki, Todd Z DeSantis, Alexander Probst, Gary L Andersen. Rob Knight, and Philip Hugenholtz. An improved greengenes taxonomy with explicit ranks for ecological and evolutionary analyses bacteria and archaea. The ISME journal, 2012.
[24] Jian Chen, Le Yang. Lu Li, and Yijun Sun. Predicting alignment distanees via continuous sequence matching. bioRxiv, 2020.
[25] Xiyuan Zhang, Yang Yuan, and Piotr Indyk. Neural embeddings for nearest neighbor search under edit distance. 2019.
[26] Xinyan Dai, Xiao Yan, Kaiwen Zhou, Yuxuan Wang. Han Yang, and James Cheng. Convolutional embedding for edit distance. In Proc. of SIGIR, 2020.
[27] Lluis Gómez, Marçal Rusinol, and Dimosthenis Karatzas, Lsde: Levenshtein space deep embedding for query-by-string word spotting. In ICDAR, 2017.
[28] Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proc. of EMNLP, 2014.
[29] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NewrIPS, 2017.
11

---

[30] Maximilian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. arXiv preprint arXi::1705.08039 2017.
[31] Benjamin Paul Chamberlain, James Clough, and Marc Peter Deisenroth. Neural embeddings of graphs in hyperbolic space. arXiv preprin! arXiv: 705. 10359, 2017.
[32] Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré, Low-dimensional hyperbolic knowledge graph embeddingg. In Proc. of ACL. 2020.
[33] Graham Cormode. Sequence distance embeddings. PhD thesis, Department of Computer Science,
University of Warwick, 2003.
[34] S Muthukrishnan and Süleyman Cenk Sahinalp. Approximate nearest neighbors and sequence comparison with block operations. In Proc. annual ACM symposium on Theory of computing, 2000.
[35] Graham Cormode, Shan Muthukrishnan, and Süleyman Cenk Sahinalp. Permutation editing and matching via embeddings. In International Colloquium on Automata, Languages, and Progrumming, 2001.
[36] Rafail Ostrovsky and Yuval Rabani. Low distortion embeddings for edit distance. Journal of the ACM (JACM), 2007.
[37] Tugkan Batu, Funda Ergun, and Cenk Sahinalp. Oblivious string embeddings and edit distance approxima- tions. SODA, 2006.
[38] Hossein Jowhari. Efficient communication protocols for deciding edit distance. In European Symposium Algorithms, 2012.
[39] Alexandr Andoni and Krzysztof Onak. Approximating edit distance in near-linear time. SIAM Journal on Computing, 2012.
[40] Diptarka Chakrahorty, Elazar Goldenberg, and Michal Koucký. Streaming algorithms for embedding and computing edit distance in the low distance regime. In Proc. of STOC, 2016.
[41] Jingdong Wang. Ting Zhang, Nicu Sche, Heng Tao Shen, al. A survey on learning to hash. IEEE transactions on pattern analysis and machine intelligence, 2017.
[42] Brian Kulis et al. Metric learning: A survey. Foundations and trends in machine learning, 2012.
[43] Aurélien Bellet, Amaury Habrard, and Mare Sebhan. survey on metric learning for feature vectors and structured data. arXiv preprint arXiv: 1306.6709, 2013.
[44] Weizhong and Adam Godzik. Cd-hit: a fast program for clustering and comparing large sets of protein or nucleotide sequences. Bioinformatics, 2006.
[45] Martin Steinegger and Johannes Söding. Clustering huge protein sequence sets in lincar time. Nature communications, 2018.
[46] Stephen F Altschul, Warren Gish, Webb Miller, Fugene W Myers, and David J Lipman. Basic local alignment search tool. Journal of molecular biology, 1990.
[47] Th Dobzhansky and Alfred H Sturtevant. Inversions in the chromosomes of Drosophila pscudoobscura. Genetics, 1938.
[48] Pavel Pevzner. Computational molecular biology: an algorithmic approach. 2000.
[49] Naruya Saitou and Masatoshi Nci. The neighhor-joining method: a new method for reconstructing phylogenetic trees. Molecular biology and evolution, 1987.
[50] Ferene Kruzslicz. Improved greedy algorithm for computing approximate median strings, Acta Cybernetica, 1999.
[51] Francisco Casacuberta and De Antonio. greedy algorithm for computing approximate median strings. In Proc. of National Symposium on Pattern Recognition and Image Analysis, 1997.
[52] Wei Peng, Tuomas Varanka, Abdelrahman Mostafa, Henglin Shi, and Guoying Zhao. Hyperbolic deep neural networks: A survey. arXiv preprint arXiv:2101.044 00562,056220 2021.
[53] Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature representations in product spaces. In Proc. of ICLR, 2019.
[54] Ondrej Skopek. Octavian Eugen Ganea, and Gary Bécigneul. Mixed-curvature variational autoencoders. In Proc. of ICLR, 2020.
[55] Octavian-Fugen Ganea, Gary Béeigneul, and Thomas Hofmann. Hyperbolic neural networks. In NeurlPS, 2018.
[56] Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovee. Hyperbolic graph convolutional neural networks. NeurlPS, 2019.
[57] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond Euclidean data. IEEE Signal Processing Magazine, 2017.
12

---

[58]
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids. groups, graphs, geodesics, and gauges, 2021.
[59]
Dan Gusfield. Algorithms on stings, trees, and sequences: Computer science and computational biology. Acm Sigact News, 1997.
[60]
Phillip Compeau and PA Pevzner. Bioinformatics algorithus: an active learning approach. 2018.
[61] William Masek and Michael S Paterson. A faster algorithm computing string edit distances. Journal of Computer and System sciences, 1980.
[62]
Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proc. of STOC, 2015.
[63] Igor Ulitsky, David Burstein, Tamir Tuller, and Benny Chor. The average common substring approach to phylogenomic reconstruction, Journal of Computational Biology, 2006.
[64] Chris-Andre Leimeister and Burkhard Morgenstern. Kmacs: the k-mismatch average common substring approach alignment- free sequence comparison. Bioinformatics, 2014.
[65] Lusheng Wang and Tao Jiang. On the complexity of multiple sequence alignment. Journal of computational biology, 1994.
[66] Robert Edgar. MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic
acids research, 2004.
[67]
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. The journal of machine learning research, 2014.
[68] Sergey Toffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proc. ICML, 2015.
[69] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv: 0645000550 2016.
[70] Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Proc. of ICLR, 2015.
[71] Elad Hoffer and Nir Ailon. Deep metric learning using triplet network. In International workshop on similarity-bused pattern recognition, 2015.
[72] Vassileios Balntas, Edgar Riba, Daniel Ponsa, and Krystian Mikolajezyk. Learning local feature descriptors with triplets and shallow convolutional neural networks. In Proc. of BMVC, 2016.
[73] Florian Schroff. Dmitry Kalenichenko, and James Philbin. Facenet: unified embedding for face
recognition and clustering. In CVPR, 2015.
[74] Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In Proc. of ICLR, 2014.
[75] Emile Mathicu, Charline Le Lan, Chris J Maddison, Ryota Tomioka, and Yee Whye Tch. Continuous hierarchical representations with Poincaré variational auto auto-encoders. In NeurIPS, 2019.
[76] Michael Powell. A direct search optimization method models the objective and constraint functions by linear interpolation. Advances optimization and numerical amalysis. 1994.
[77] Charles George Broyden. The convergence of class of double-rank minimization algorithms 1. general considerations. IMA Journal of Applied Mathematics, 1970.
[78] Roger Fletcher. A new approach to variable metric algorithms. The computer journal, 1970.
[79] Donald Goldfarb. A family of variable-metric methods derived by variational means. Mathematics of computation, 1970.
[80] David F Shanno. Conditioning of quasi-newton methods for function minimization. Mathematics of computation, 1970.
[81] Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: fundamental algorithms for scientific computing Python. Nature methods, 2020.
13


Reviews:
[{"review_id": "eobsnB6SDeC", "reviewer": "Reviewer_QePG", "summary": "The paper tackles the problem of approximating edit distances between biological sequences. For this purpose, the authors propose an encoder that maps sequences to a vector space, and is trained in a way such that the distance between encoded representations matches the edit distance between underlying sequences. The authors show multiple experiments with different architectures (Linear, Transformer, CNN, GRU, etc.) and different geometries (cosine, euclidean, hyperbolic, etc.). Overall, the approach is able to approximate well the edit distance while being much faster to compute. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Disclaimer: I am not very knowledgeable about biological sequences. \nI found the paper interesting, well-written and easy to follow. The idea of using neural networks to capture the statistics of the distribution in an embedding space seems to work well and to avoid doing M^2 operations to compute pairwise distances. I think it is an interesting new use case for neural networks, where it seems to work well. The extension to hierarchical clustering and multiple sequence alignment are interesting and seem to perform well. \n\nQuestions:\n- with what architecture was the running time computed ? Not all proposed models have a linear complexity with respect to the sequence length\n- why is there a decoder in Figure 1 that is not mentionned in the caption and does not seem to be used at all?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "SQMxC3LQMdc", "reviewer": "Reviewer_yqKf", "summary": "This paper presents an encoder-based framework  (called NeuroSEED) to learn the embeddings of DNA sequences in geometric vector spaces that preserve edit distance between them. Learning an efficient representation that captures the underlying hierarchical relationships allows faster applications of downstream applications like Edit distance Approximation (EDA), Closest String Retrieval (CSR), Multiple Sequence Alignment (MSA), and Hierarchical clustering (HA). The paper explores a variety of neural network models for encoding the sequences as well as different geometric vector spaces. The tasks are formulated as unsupervised (with general MSE loss) and supervised (with tailored loss functions).  It reports hyperbolic space to give the state-of-the-art performance for all the downstream tasks and claims a faster compute time (in terms of time complexity) when using these embeddings. The results are reported on two relevant microbiome analysis datasets - Qiita and RT988. ", "questions": "", "limitations": "", "rating": 7, "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": "Strengths:\n\n++ The paper presents an interesting idea of preserving the edit distance when encoding the genomic sequences in geometric vector spaces.\n\n++ The problem to accurately capture the underlying biological information in terms of hierarchy and edit distance is an important one and potentially useful for the field. \n \n++ The results are presented for 2 datasets and different settings and frameworks. The extensions to Dasgupta’s cost for HC and Steiner string approximation problem for MSA demonstrate the flexibility of NeuroSEED to task-specific formulations. \n \n++ The paper is clear and well written\n\n\nWeaknesses:\n\n-- For a paper that claims fast approximations for downstream applications, it does not have a runtime result table in the main paper or supplementary recording the runtimes of all the baselines and the proposed framework. While some approximations of the runtime and time complexity reported do suggest faster times, it would be very useful for the reader to see and compare the run times (including training/test) when running existing methods and NeuroSEED. \n\n-- It is important to focus on how much time does the model saves once it is trained. However,\nit would also be useful for the paper to comment on how the hyperparameter tuning times would affect the overall runtime of NeuroSEED on a new task compared to running existing methods. \n\n-- While the hyperbolic space emerges as the best performing geometric space for the embeddings, that is not the case for the encoder architecture. Can the paper recommend a default framework that would give overall good performance across datasets/tasks and still be fast? \n\n-- Alignment-free methods like kmacs seem to allow for mismatches. Does the k-mer baseline, formulated in the paper, incorporate mismatches when approximating edit distance using k-mers? If not, could that potentially result in a lower performance than expected by using existing methods like kmacs?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-The paper discusses limitations and potential negative impacts in the supplementary\n\n-It would be useful for the paper to discuss NeuroSEEDs limitations (if any) when applied to new types of datasets (beyond microbiome analysis) \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "HbIhp3Ghxg", "reviewer": "Reviewer_Pdgk", "summary": "This paper offers two contributions - the first is a formalization of a general encoder-decoder framework for learning representations of biological sequences, where the distance in the representation space corresponds to the edit distance between the sequences (NeuroSEED). The second is the use of hyperbolic geometry to embed the sequences. The authors then demonstrate the efficacy and runtime improvements of their method on a variety of tasks, including approximating edit distance, MSA and hierarchical clustering.", "questions": "", "limitations": "", "rating": 4, "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": "Overall, the manuscript is well written and the work is solid, but the exact training method and models compared are not clear from the main text. The significance and practicality of the method seem low, given that a model needs to be trained for each dataset rather than being pre-trained. Furthermore, the novelty is weak and discussion and comparison with other frameworks is missing. The elephant in the room here being locality sensitive hashing-based methods. Specific comments follow below.\n\n1.\tThe idea to use an encoder-decoder framework to embed sequences in a latent space is not new, the application of such a framework for biological sequences is not new  (see e.g., https://www.nature.com/articles/s41598-018-34533-1, https://link.springer.com/article/10.1186/s12859-017-1700-2, http://proceedings.mlr.press/v70/mueller17a.html), and the use of hyperbolic geometry as the embedding geometry is not new. However, the specific combination of these methods in application to biological sequences is, to my knowledge, novel. \n2.\tThe framework is only evaluated on two 16S rRNA datasets rather than whole genome sequencing or other more diverse sequencing datasets. Furthermore, the models are trained on each dataset specifically. This seems like a major practical limitation. How does this pre-training time factor into a sequence analysis project? The reported training time is long enough that it seems to remove any time benefits downstream. It seems somewhat misleading to focus on downstream clustering or pairwise distance calculation times when the model needs to be trained first and typically analysis is only performed once for a given dataset leading to limited amortization. On top of which, training time should increase with larger datasets. Is it possible to pre-train these models and have them generalize well? Do these models work on more diverse sequence datasets? What about sequences with larger disparities in length? \n3.\tSection 7.1 is unclear in explaining the approach - in particular line 241 - it is unclear how the linear layer maps sequences of different lengths to a hyperbolic space, or how the model is trained. Furthermore, this is referred to as an encoder-decoder framework, but a decoder is only used in one experiment and the details of its structure are fuzzy.\n4.\tAdditionally, the tables often include methods first established in other papers - it is unclear whether the entries in these tables are 1) original methods and original experiments by the authors, 2) methods taken from other papers but new experiments done by the authors, or 3) methods and experiments taken from other papers. \n5.\tNo comparison with locality sensitive hashing-based methods or even discussion of these methods in biological sequence analysis and other heuristic methods for sequence clustering that are widely used (e.g., https://www.nature.com/articles/s41467-018-04964-5, https://academic.oup.com/bioinformatics/article/22/13/1658/194225, https://www.nature.com/articles/nbt.3988). Even BLAST uses heuristics to find similar sequences before alignment (https://pubmed.ncbi.nlm.nih.gov/2231712/) which is not mentioned.\n6.\tThis work considers edit distance, but in practice biological sequence comparison is not performed based on edit distance but rather substitution scores between amino acids. These are not distance functions. How does this fit into the proposed framework?\n7.\t“Again, the results reported in Figure 6 show that the alignment scores obtained when using the NeuroSEED heuristics with attention models are not statistically different from those obtained with the ground truth distances.” – line 224. Reporting these results as percentage differences from CLUSTAL using the ground truth edit distances as the guide tree is confusing. It would be nice to report the scores directly. How does this compare to the results obtained by running CLUSTAL with default settings?\n\nI think the significance of this work is limited. It’s hard to call the formalization of the framework a useful contribution, because the idea of encoder-decoder-loss-geometry is already a standardized concept in the field. Furthermore, the offered performance and speedup benefits are limited by the need to train the model on each dataset and the generalizability to larger and more diverse sequence datasets is unknown.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no discussion of limitations and societal impact in the main text, but some discussion of limitations is provided in the appendix. I personally do not find the lack of societal impacts for this work to be an issue.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "69fQjlixf8y", "reviewer": "Reviewer_HK7w", "summary": "This paper proposes NeuroSEED to embed strings into vectors for edit distance approximation. The key insight is that hyperbolic space is more suitable for embedding the hierarchical of biological sequences. Extensive experiments are conducted to show that NeuroSEED significantly improves the efficiency of hierarchical clustering and multiple sequence alignment. \n            \n", "questions": "", "limitations": "", "rating": 7, "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": "I enjoyed the paper as using hyperbolic space makes sense and improving the efficiency of biological tasks is important. \n\nHowever, the authors may need to tune down the contribution of NeuroSEED to properly acknowledge the contribution of existing works. In the introduction, please state explicitly that there already exist works that embed strings into vectors for edit distance approximation. I think NeuroSEED conducts a nice survey and experimental study of existing edit distance embedding methods. However, it is a bit overclaimed to say that NeuroSEED is the first to propose a general framework for edit distance embedding because the workflow of (i) using a model to map string to vector and (ii) choosing a vector space and defining a loss function for training is already utilized in existing works such as [22, 23] (maybe obvious for a machine learning pipeline). \n\nIn addition to biological tasks, the generality of hyperbolic space may need to be examined for other use cases of edit distance. [22, 23] consider string similarity search and deal with datasets containing strings with a high variation in length (while datasets in this paper contain string with similar length). In addition, for string similarity search, it is important to enlarge the distance gap between similar string pairs and dissimilar string pairs (maybe more important than accurately approximate edit distance). I am curious whether using hyperbolic space leads to better performance for string similarity search. If not, I think a more appropriate title of this paper maybe “Neural Distance Embedding for Biological Sequence”, such that the limitation of the proposed method is explicitly stated.       ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies methods for embedding sequences into geometric spaces that approximately preserve the edit distance. The key finding is that embedding into hyperbolic spaces yields (significantly) lower distortion than embedding into other geometric spaces. The finding is supported by experiments on multiple data sets, in the context of several downstream applications: similarity search, clustering and multiple alignment.

Despite a few rounds of discussion, the reviewers did not reach a consensus. Most of the reviews are positive, with some reviewers being very positive. At the same time though, the negative review raises valid points, including (1) the basic edit distance (where all operations have unit cost) does not occur often in applications, so the practical impact of the proposed method is unclear (2) in the context of similarity search, there is no comparison to indexing methods that are faster than linear scan (e.g., LSH); given that fast algorithms for hyperbolic spaces are not well developed, it could be that the more accurate embeddings into hyperbolic spaces might actually yield less efficient algorithms than the less accurate embeddings into (say) the Euclidean space. 

That said, the paper does introduce an interesting idea, and it is likely that its findings will stimulate further research on embeddings into (and algorithms for) hyperbolic spaces. So, I recommend accepting the paper,  even though at present its practical impact is not guaranteed.

Decision: Accept (Poster)