# Deep Squared Euclidean Approximation to the Levenshtein Distance for DNA Storage

arXiv: https://arxiv.org/abs/2207.04684 · HTML: https://mlsanity.com/paper/2207.04684/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 42 references that are in the map.
- First posted on arXiv 11 Jul 2022.

## Builds on (most cited first, 8 of 8)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [Hashing for Similarity Search: A Survey](https://mlsanity.com/paper/1408.2927/) (2014)
- [Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)](https://mlsanity.com/paper/1412.0348/) (2014)
- [Neural Distance Embeddings for Biological Sequences](https://mlsanity.com/paper/2109.09740/) (2021)
- [EmbedJoin: Efficient Edit Similarity Joins via Embeddings](https://mlsanity.com/paper/1702.00093/) (2017)
- [On Practical Accuracy of Edit Distance Approximation Algorithms](https://mlsanity.com/paper/1701.06134/) (2017)

## Built on by (most cited first, 2 of 2)

- [Levenshtein Distance Embedding with Poisson Regression for DNA Storage](https://mlsanity.com/paper/2312.07931/) (2023)
- [DoDo-Code: an Efficient Levenshtein Distance Embedding-based Code for 4-ary IDS Channel](https://mlsanity.com/paper/2312.12717/) (2023)

## Abstract (arXiv)

Storing information in DNA molecules is of great interest because of its advantages in longevity, high storage density, and low maintenance cost. A key step in the DNA storage pipeline is to efficiently cluster the retrieved DNA sequences according to their similarities. Levenshtein distance is the most suitable metric on the similarity between two DNA sequences, but it is inferior in terms of computational complexity and less compatible with mature clustering algorithms. In this work, we propose a novel deep squared Euclidean embedding for DNA sequences using Siamese neural network, squared Euclidean embedding, and chi-squared regression. The Levenshtein distance is approximated by the squared Euclidean distance between the embedding vectors, which is fast calculated and clustering algorithm friendly. The proposed approach is analyzed theoretically and experimentally. The results show that the proposed embedding is efficient and robust.