Research map / Learning theory and algorithms / Clustering
A New Burrows Wheeler Transform Markov Distance
Edward Raff, Charles Nicholas, Mark McLean
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Represent each sequence with BWT-derived Markov transition features and cluster in Euclidean space | malware family clustering · Kaggle Bytes, Kaggle ASM, Drebin APK, Drebin TAR, and VS20F | V-Measure: Kaggle Bytes k=10·C: 0.414 -> 0.546; Kaggle ASM k=10·C: 0.531 -> 0.562; Drebin APK k=10·C: 0.326 -> 0.412; Drebin TAR k= | Improved |
| Use BWMD instead of LZJD for nearest-neighbor malware classification | 1-NN malware classification · Kaggle Bytes and Kaggle ASM | balanced accuracy: Kaggle Bytes: 97.9 (1.4) -> 96.4 (2.2); Kaggle ASM: 97.1 (1.7) -> 97.0 (1.8) | Hurt |
| Use BWMD instead of LZJD for nearest-neighbor malware classification | 1-NN malware classification · Drebin APK and Drebin TAR | balanced accuracy: Drebin APK: 81.0 (4.0) -> 55.3 (4.4); Drebin TAR: 87.9 (2.1) -> 76.3 (3.6) | Hurt |
| Use BWMD instead of LZJD for large-corpus nearest-neighbor search | EMBER retrieval · EMBER | AUC: 99.7% -> 98.3% | Hurt |
| Index BWMD Euclidean embeddings with DCI rather than brute-force search | BWMD · EMBER test set | query time: 834× faster than BWMD with a brute force search | Improved |
| Use BWMD rather than EBWT for clustering variable-length genomic scaffold sequences | single-link DNA clustering · Genomic scaffold DNA | clustering quality: 28 minutes -> 47 seconds | Improved |
| Use BWMD rather than LZJD for malware clustering | malware family clustering · VS20F training set | clustering time: 7.76 hours -> 27 minutes | Improved |
| Ignore sequence length in the distance by comparing normalized BWT transition distributions | BWMD · u=a^n1 and v=a^n2, n2>n1 | distance: bwmd(u,v)=0 | Improved |
| Use BWMD transition distributions to compare sequences with disjoint alphabets | BWMD · Sequences with no shared characters | distance: bwmd(u,v)=1 | Improved |
Closest papers by meaning
- Levenshtein Distance Embedding with Poisson Regression for DNA Storage (AAAI 2024 · similarity 0.83)
- Context-Aware Regularization with Markovian Integration for Attention-Based Nucleotide Analysis (NeurIPS 2025 · similarity 0.83)
- GeneZip: Region-Aware Compression for Long Context DNA Modeling (NeurIPS 2026 · similarity 0.82)
- Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchy (ICLR 2025 · similarity 0.82)
- VQDNA: Unleashing the Power of Vector Quantization for Multi-Species Genomic Sequence Modeling (ICML 2024 · similarity 0.82)
- DNABERT-2: Efficient Foundation Model and Benchmark For Multi-Species Genomes (ICLR 2024 · similarity 0.82)
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.
