A framework for space-efficient variable-order Markov models.

Area of Science:

• Bioinformatics
• Computational Biology
• Data Structures

Background:

• Variable-order Markov models (VOMMs) are crucial for analyzing biological sequences with similar properties.
• Existing VOMM implementations struggle with large, genome-scale datasets due to memory limitations and inflexibility.

Purpose of the Study:

• To develop practical and versatile representations for VOMMs and interpolated Markov models.
• To significantly reduce memory footprint compared to existing methods, enabling analysis of larger datasets and longer contexts.

Main Methods:

• Developed novel, space-efficient data structures for variable-order and interpolated Markov models.
• Implemented support for diverse context-selection criteria, scoring functions, probability smoothing, and interpolation methods.
• Introduced compression techniques leveraging data redundancy and context constraints.

Main Results:

• Achieved space reductions of up to 4x compared to suffix array implementations and 10x+ compared to trie-based methods.
• Further compression reduced index size by up to 90% on repetitive datasets (60x smaller than suffix array methods).
• Contextual constraints enabled further size reductions, achieving data structures 100x smaller than previous suffix array implementations.

Conclusions:

• The new VOMM representations are highly memory-efficient and versatile.
• These advancements facilitate the application of VOMMs to larger biological datasets and longer sequence contexts.
• The improved scalability may unlock new possibilities in bioinformatics sequence analysis.