Research map / Learning theory and algorithms / Prediction and decision losses
Levenshtein Distance Embedding with Poisson Regression for DNA Storage
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Poisson regression loss and a early-stopping-dimension criterion for neural Levenshtein distance embedding, evaluated on DNA storage data.
Problem
Fast approximation of Levenshtein distance between DNA sequences via neural sequence embeddings, where the choice of embedding dimension and training loss affect approximation accuracy.
Approach
Interprets Levenshtein distance as a Poisson-distributed count of edit events, so trains embeddings with Poisson negative log-likelihood (PNLL), which approximates the chi-squared NLL of prior chi-square regression as embedding dimension grows; also selects embedding dimension via an early-stopping dimension found from eigenvalues of the covariance of embedding differences.
Key results
- PNLL loss gives the lowest homologous approximation error AE_h across all embedding networks, e.g., CNN-10-w (140) reaches AE_h 0.47 ± 0.00 versus 0.62 for MSE with CNN-5 (80)... (see table: CNN-10-w(140) PNLL AE_h 0.47 vs MSE 0.62)
- Increasing embedding dimension from 80 to the early-stopping dimension (120 for CNN-5/CNN-10, 140 for wide CNNs) improves AE_g substantially, e.g., CNN-10-w AE_g from 3.76 to 3.00 with PNLL.
- Estimated early-stopping dimension is 120 for CNN-5 and CNN-10 and 140 for CNN-5-w, CNN-10-w and GRU.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PNLL instead of MAE | CNN-10-w, dimension 140 · DNA storage test | AE_h: 0.54±0.00 -> 0.47±0.00 | Helped |
| Use PNLL instead of MSE | CNN-10-w, dimension 140 · DNA storage test | AE_g: 2.90±0.01 -> 3.00±0.02 | Hurt |
| Increase embedding dimension from 80 to the ESD dimension 140 (ablation) | CNN-10-w with PNLL · DNA storage test | AE_h: 0.48±0.01 -> 0.47±0.00 | Helped |
| Increase embedding dimension from 80 to the ESD dimension 140 (ablation) | CNN-10-w with PNLL · DNA storage test | AE_g: 3.76±0.01 -> 3.00±0.02 | Helped |
| Increase embedding dimension from 80 to 140 (ablation) | GRU with PNLL · DNA storage test | AE_g: 4.34±0.02 -> 4.54±0.04 | Hurt |
| Increase embedding dimension from 80 to 140 (ablation) | GRU with PNLL · DNA storage test | AE_h: 0.61±0.00 -> 0.64±0.00 | Hurt |
| Use CNN-10-w instead of CNN-10 (ablation) | PNLL embedding model at the ESD dimension · DNA storage test | AE_h: 0.55±0.01 -> 0.47±0.00 | Helped |
| Use CNN-10-w instead of CNN-10 (ablation) | PNLL embedding model at the ESD dimension · DNA storage test | AE_g: 3.35±0.05 -> 3.00±0.02 | Helped |
| Increase convolutional depth from 5 to 10 layers (ablation) | CNN embedding with PNLL, dimension 120 · DNA storage test | AE_h: 0.58±0.02 -> 0.55±0.01 | Helped |
| Increase convolutional depth from 5 to 10 layers (ablation) | CNN embedding with PNLL, dimension 120 · DNA storage test | AE_g: 3.57±0.04 -> 3.35±0.05 | Helped |
| Increase embedding dimension above the ESD (ablation) | CNN-5 · DNA storage test | Approximation error | No clear effect |
| Use a wider convolutional network instead of a plain-width network (ablation) | Levenshtein distance embedding · DNA storage test | Approximation error | Helped |
Surprising findings
- GRU performance worsens when embedding dimension increases from 80 to 140, and its eigenvalues decay gradually, suggesting the dimension assumption fails for GRU.
- Width (channels) matters more than depth (layers) for the early-stopping dimension and approximation accuracy.
Limitations
- Assumptions A1-A4 (independence, normality, dimension upper bound) are approximate and can fail, e.g., for GRU.
- Poisson approximation is justified mainly when distance is small relative to sequence length.
- Failed approximations occur for sequences with homopolymer runs at insertion/deletion sites, which the method does not address.
Experimental setup
Datasets: DNA storage data from DNA-Fountain (ENA PRJEB19305)
Benchmarks: DNA storage data (DNA-Fountain)
Metrics: global approximation error (AE_g) homologous approximation error (AE_h)
Baselines: MSE loss MAE loss RE-chi-squared (chi-square regression) CNN-5 CNN-10 GRU
Builds on: chi-square regression Siamese neural network DNA-Fountain
Closest papers by meaning
- Neural Embeddings for kNN Search in Biological Sequence (AAAI 2024 · similarity 0.85)
- Hyperbolic Genome Embeddings (ICLR 2025 · similarity 0.83)
- DoDo-Code: an Efficient Levenshtein Distance Embedding-based Code for 4-ary IDS Channel (NeurIPS 2025 · similarity 0.83)
- VQDNA: Unleashing the Power of Vector Quantization for Multi-Species Genomic Sequence Modeling (ICML 2024 · similarity 0.81)
- Absorb & Escape: Overcoming Single Model Limitations in Generating Heterogeneous Genomic Sequences (NeurIPS 2024 · similarity 0.81)
- What DNA Foundation Models Learn Beyond Sequence Composition (NeurIPS 2026 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.