A New Burrows Wheeler Transform Markov Distance
No Thumbnail Available
Links to Files
Permanent Link
Author/Creator
Author/Creator ORCID
Date
2019-12-30
Type of Work
Department
Program
Citation of Original Publication
Raff, Edward; Nicholas, Charles; McLean, Mark; A New Burrows Wheeler Transform Markov Distance; Cryptography and Security (2019); https://arxiv.org/abs/1912.13046
Rights
This item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.
Abstract
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.