A framework for space-efficient variable-order Markov models
Loading...
Date
2019-11-15
Authors
Cunial, Fabio
Alanko, Jarno
Belazzougui, Djamal
Journal Title
Journal ISSN
Volume Title
Publisher
Oxford University Press
Abstract
Motivation: Markov models with contexts of variable length are widely used in bioinformatics for
representing sets of sequences with similar biological properties. When models contain many long
contexts, existing implementations are either unable to handle genome-scale training datasets within
typical memory budgets, or they are optimized for specific model variants and are thus inflexible.
Results: We provide practical, versatile representations of variable-order Markov models and of
interpolated Markov models, that support a large number of context-selection criteria, scoring functions,
probability smoothing methods, and interpolations, and that take up to four times less space than previous
implementations based on the suffix array, regardless of the number and length of contexts, and up
to ten times less space than previous trie-based representations, or more, while matching the size of
related, state-of-the-art data structures from Natural Language Processing. We describe how to further
compress our indexes to a quantity related to the redundancy of the training data, saving up to 90% of
their space on very repetitive datasets, and making them become up to sixty times smaller than previous
implementations based on the suffix array. Finally, we show how to exploit constraints on the length and
frequency of contexts to further shrink our compressed indexes to half of their size or more, achieving data
structures that are a hundred times smaller than previous implementations based on the suffix array, or
more. This allows variable-order Markov models to be used with bigger datasets and with longer contexts
on the same hardware, thus possibly enabling new applications.
Availability and implementation: https://github.com/jnalanko/VOMM
Description
Keywords
Variable-order Markov models , Truncated suffix tries , Succinct data structures , Burrows-Wheeler transform , Biological sequence analysis , Protein families , Metagenomics