# A New Burrows Wheeler Transform Markov Distance

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Dec 2019.

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

- [Recasting Self-Attention with Holographic Reduced Representations](https://mlsanity.com/paper/2305.19534/) (2023)
- [Efficient Malware Analysis Using Metric Embeddings](https://mlsanity.com/paper/2212.02663/) (2022)
- [Holographic Global Convolutional Networks for Long-Range Prediction Tasks in Malware Detection](https://mlsanity.com/paper/2403.17978/) (2024)
- [AVScan2Vec: Feature Learning on Antivirus Scan Data for Production-Scale Malware Corpora](https://mlsanity.com/paper/2306.06228/) (2023)
- [Neural Normalized Compression Distance and the Disconnect Between Compression and Classification](https://mlsanity.com/paper/2410.15280/) (2024)
- [An Introduction to Compression-Based Machine Learning](https://mlsanity.com/paper/2609.21309/) (2026)

## Abstract (arXiv)

Prior work inspired by compression algorithms has described how the Burrows Wheeler Transform can be used to create a distance measure for bioinformatics problems. We describe issues with this approach that were not widely known, and introduce our new Burrows Wheeler Markov Distance (BWMD) as an alternative. The BWMD avoids the shortcomings of earlier efforts, and allows us to tackle problems in variable length DNA sequence clustering. BWMD is also more adaptable to other domains, which we demonstrate on malware classification tasks. Unlike other compression-based distance metrics known to us, BWMD works by embedding sequences into a fixed-length feature vector. This allows us to provide significantly improved clustering performance on larger malware corpora, a weakness of prior methods.