# Levenshtein Distance Embedding with Poisson Regression for DNA Storage

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 32 references that are in the map.
- First posted on arXiv 13 Dec 2023.

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

- [Momentum Contrast for Unsupervised Visual Representation Learning](https://mlsanity.com/paper/1911.05722/) (2019)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering](https://mlsanity.com/paper/2010.00402/) (2020)
- [Neural Distance Embeddings for Biological Sequences](https://mlsanity.com/paper/2109.09740/) (2021)
- [Deep Squared Euclidean Approximation to the Levenshtein Distance for DNA Storage](https://mlsanity.com/paper/2207.04684/) (2022)

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

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

## Abstract (arXiv)

Efficient computation or approximation of Levenshtein distance, a widely-used metric for evaluating sequence similarity, has attracted significant attention with the emergence of DNA storage and other biological applications. Sequence embedding, which maps Levenshtein distance to a conventional distance between embedding vectors, has emerged as a promising solution. In this paper, a novel neural network-based sequence embedding technique using Poisson regression is proposed. We first provide a theoretical analysis of the impact of embedding dimension on model performance and present a criterion for selecting an appropriate embedding dimension. Under this embedding dimension, the Poisson regression is introduced by assuming the Levenshtein distance between sequences of fixed length following a Poisson distribution, which naturally aligns with the definition of Levenshtein distance. Moreover, from the perspective of the distribution of embedding distances, Poisson regression approximates the negative log likelihood of the chi-squared distribution and offers advancements in removing the skewness. Through comprehensive experiments on real DNA storage data, we demonstrate the superior performance of the proposed method compared to state-of-the-art approaches.