Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
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.

1.	The 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. 
2.	The 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? 
3.	Section 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.
4.	Additionally, 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. 
5.	No 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.
6.	This 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?
7.	“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?

I 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.

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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
main_review: Disclaimer: I am not very knowledgeable about biological sequences. 
I 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. 

Questions:
- with what architecture was the running time computed ? Not all proposed models have a linear complexity with respect to the sequence length
- why is there a decoder in Figure 1 that is not mentionned in the caption and does not seem to be used at all?

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
            

main_review: I enjoyed the paper as using hyperbolic space makes sense and improving the efficiency of biological tasks is important. 

However, 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). 

In 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.       
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
main_review: Strengths:

++ The paper presents an interesting idea of preserving the edit distance when encoding the genomic sequences in geometric vector spaces.

++ 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. 
 
++ 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. 
 
++ The paper is clear and well written


Weaknesses:

-- 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. 

-- It is important to focus on how much time does the model saves once it is trained. However,
it 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. 

-- 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? 

-- 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?

limitations_and_societal_impact: -The paper discusses limitations and potential negative impacts in the supplementary

-It would be useful for the paper to discuss NeuroSEEDs limitations (if any) when applied to new types of datasets (beyond microbiome analysis)
review_title: null

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)