  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.
