{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:34:54Z","timestamp":1772138094572,"version":"3.50.1"},"reference-count":68,"publisher":"Oxford University Press (OUP)","issue":"22","license":[{"start":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T00:00:00Z","timestamp":1555718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,11,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>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.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>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 60 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.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>https:\/\/github.com\/jnalanko\/VOMM<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btz268","type":"journal-article","created":{"date-parts":[[2019,4,10]],"date-time":"2019-04-10T07:14:22Z","timestamp":1554880462000},"page":"4607-4616","source":"Crossref","is-referenced-by-count":8,"title":["A framework for space-efficient variable-order Markov models"],"prefix":"10.1093","volume":"35","author":[{"given":"Fabio","family":"Cunial","sequence":"first","affiliation":[{"name":"Max Planck Institute for Molecular Cell Biology and Genetics (MPI-CBG), and Center for Systems Biology Dresden (CSBD) , Dresden 01307, Germany"}]},{"given":"Jarno","family":"Alanko","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki , Helsinki 00014, Finland"}]},{"given":"Djamal","family":"Belazzougui","sequence":"additional","affiliation":[{"name":"CAPA, DTISI, Centre de Recherche sur l'Information Scientifique et Technique , Algiers, Algeria"}]}],"member":"286","published-online":{"date-parts":[[2019,4,20]]},"reference":[{"key":"2023013108325540800_btz268-B1","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1089\/106652700750050844","article-title":"Optimal amnesic probabilistic automata or how to learn and classify proteins in linear time and space","volume":"7","author":"Apostolico","year":"2000","journal-title":"J. Comput. Biol"},{"key":"2023013108325540800_btz268-B2","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1109\/TIT.2004.826664","article-title":"An O(n) semipredictive universal encoder via the BWT","volume":"50","author":"Baron","year":"2004","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2023013108325540800_btz268-B3","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1613\/jair.1491","article-title":"On prediction using variable order Markov models","volume":"22","author":"Begleiter","year":"2004","journal-title":"J. Artif. Intell. Res"},{"key":"2023013108325540800_btz268-B4","author":"Bejerano","year":"2003"},{"key":"2023013108325540800_btz268-B5","doi-asserted-by":"crossref","first-page":"788","DOI":"10.1093\/bioinformatics\/btg489","article-title":"Algorithms for variable length Markov chain modeling","volume":"20","author":"Bejerano","year":"2004","journal-title":"Bioinformatics"},{"key":"2023013108325540800_btz268-B6","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/299432.299445","volume-title":"Proceedings of the Third Annual International Conference on Computational Molecular Biology","author":"Bejerano","year":"1999"},{"key":"2023013108325540800_btz268-B7","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1093\/bioinformatics\/17.1.23","article-title":"Variations on probabilistic suffix trees: statistical modeling and prediction of protein families","volume":"17","author":"Bejerano","year":"2001","journal-title":"Bioinformatics"},{"key":"2023013108325540800_btz268-B8","doi-asserted-by":"crossref","first-page":"927","DOI":"10.1093\/bioinformatics\/17.10.927","article-title":"Markovian domain fingerprinting: statistical segmentation of protein sequences","volume":"17","author":"Bejerano","year":"2001","journal-title":"Bioinformatics"},{"key":"2023013108325540800_btz268-B9","first-page":"179","volume-title":"International Symposium on String Processing and Information Retrieval","author":"Belazzougui","year":"2014"},{"key":"2023013108325540800_btz268-B10","first-page":"1","article-title":"A framework for space-efficient string kernels","author":"Belazzougui","year":"2017","journal-title":"Algorithmica"},{"key":"2023013108325540800_btz268-B11","doi-asserted-by":"crossref","first-page":"23.","DOI":"10.1145\/2635816","article-title":"Alphabet-independent compressed text indexing","volume":"10","author":"Belazzougui","year":"2014","journal-title":"ACM Trans. Algorithms"},{"key":"2023013108325540800_btz268-B12","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/978-3-319-19929-0_3","volume-title":"Annual Symposium on Combinatorial Pattern Matching","author":"Belazzougui","year":"2015"},{"key":"2023013108325540800_btz268-B13","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1038\/nmeth.1358","article-title":"Phymm and PhymmBL: metagenomic phylogenetic classification with interpolated Markov models","volume":"6","author":"Brady","year":"2009","journal-title":"Nat. Methods"},{"key":"2023013108325540800_btz268-B14","author":"Brants","year":"2007"},{"key":"2023013108325540800_btz268-B15","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1023\/A:1004165822461","article-title":"Model selection for variable length Markov chains and tuning the context algorithm","volume":"52","author":"B\u00fchlmann","year":"2000","journal-title":"Ann. Inst. Stat. Math"},{"key":"2023013108325540800_btz268-B16","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1214\/aos\/1018031204","article-title":"Variable length Markov chains","volume":"27","author":"B\u00fchlmann","year":"1999","journal-title":"Ann. Stat"},{"key":"2023013108325540800_btz268-B17","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1093\/comjnl\/40.2_and_3.76","article-title":"Semantically motivated improvements for PPM variants","volume":"40","author":"Bunton","year":"1997","journal-title":"Comput. J"},{"key":"2023013108325540800_btz268-B18","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1006\/csla.1999.0128","article-title":"An empirical study of smoothing techniques for language modeling","volume":"13","author":"Chen","year":"1999","journal-title":"Comput. Speech Lang"},{"key":"2023013108325540800_btz268-B19","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1109\/TCOM.1984.1096090","article-title":"Data compression using adaptive coding and partial string matching","volume":"32","author":"Cleary","year":"1984","journal-title":"IEEE Trans. Commun"},{"key":"2023013108325540800_btz268-B20","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1093\/comjnl\/40.2_and_3.67","article-title":"Unbounded length contexts for PPM","volume":"40","author":"Cleary","year":"1997","journal-title":"Comput. J"},{"key":"2023013108325540800_btz268-B21","doi-asserted-by":"crossref","first-page":"130.","DOI":"10.1186\/s12859-016-0980-2","article-title":"On the comparison of regulatory sequences with multiple resolution entropic profiles","volume":"17","author":"Comin","year":"2016","journal-title":"BMC Bioinformatics"},{"key":"2023013108325540800_btz268-B22","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1093\/bioinformatics\/btk029","article-title":"Bayesian classifiers for detecting HGT using fixed and variable order Markov models of genomic signatures","volume":"22","author":"Dalevi","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013108325540800_btz268-B23","first-page":"345","article-title":"The power of selective memory: self-bounded learning of prediction suffix trees","author":"Dekel","year":"2005","journal-title":"Advances in Neural Information Processing Systems"},{"key":"2023013108325540800_btz268-B24","doi-asserted-by":"crossref","first-page":"5251","DOI":"10.1109\/TIT.2009.2030460","article-title":"Individual sequence prediction using memory-efficient context trees","volume":"55","author":"Dekel","year":"2009","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2023013108325540800_btz268-B25","doi-asserted-by":"crossref","first-page":"4636","DOI":"10.1093\/nar\/27.23.4636","article-title":"Improved microbial gene identification with GLIMMER","volume":"27","author":"Delcher","year":"1999","journal-title":"Nucleic Acids Res"},{"key":"2023013108325540800_btz268-B26","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1093\/bioinformatics\/btm009","article-title":"Identifying bacterial genes and endosymbiont DNA with GLIMMER","volume":"23","author":"Delcher","year":"2007","journal-title":"Bioinformatics"},{"key":"2023013108325540800_btz268-B27","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1089\/106652703321825964","article-title":"Protein family classification using sparse Markov transducers","volume":"10","author":"Eskin","year":"2003","journal-title":"J. Comput. Biol"},{"key":"2023013108325540800_btz268-B28","first-page":"1459","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018","author":"Gagie","year":"2018"},{"key":"2023013108325540800_btz268-B29","first-page":"326","article-title":"From theory to practice: plug and play with succinct data structures","author":"Gog","year":"2014","journal-title":"13th International Symposium on Experimental Algorithms (SEA 2014)"},{"key":"2023013108325540800_btz268-B30","first-page":"269","volume-title":"Proceedings of the 15th International Conference on Machine Learning, vol. 98","author":"Kearns","year":"1998"},{"key":"2023013108325540800_btz268-B31","doi-asserted-by":"crossref","first-page":"544.","DOI":"10.1186\/1471-2105-11-544","article-title":"Clustering metagenomic sequences with interpolated Markov models","volume":"11","author":"Kelley","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023013108325540800_btz268-B32","first-page":"185","volume-title":"European Conference on Machine Learning","author":"Kermorvant","year":"2002"},{"key":"2023013108325540800_btz268-B33","author":"Kermorvant","year":"2002"},{"key":"2023013108325540800_btz268-B34","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1093\/bioinformatics\/btl088","article-title":"A generalization of the PST algorithm: modeling the sparse nature of protein sequences","volume":"22","author":"Leonardi","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013108325540800_btz268-B35","doi-asserted-by":"crossref","first-page":"37243","DOI":"10.1038\/srep37243","article-title":"Alignment-free transcriptomic and metatranscriptomic comparison using sequencing signatures with variable length Markov chains","volume":"6","author":"Liao","year":"2016","journal-title":"Sci. Rep"},{"key":"2023013108325540800_btz268-B36","doi-asserted-by":"crossref","first-page":"1314","DOI":"10.1093\/bioinformatics\/bts121","article-title":"Probabilistic suffix array: efficient modeling and prediction of protein families","volume":"28","author":"Lin","year":"2012","journal-title":"Bioinformatics"},{"key":"2023013108325540800_btz268-B37","author":"Magarick","year":"2016"},{"key":"2023013108325540800_btz268-B38","doi-asserted-by":"crossref","first-page":"1442","DOI":"10.1109\/TIT.2004.830763","article-title":"Linear time universal coding and time reversal of tree sources via FSM closure","volume":"50","author":"Martin","year":"2004","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2023013108325540800_btz268-B39","doi-asserted-by":"crossref","first-page":"215.","DOI":"10.1038\/nature11209","article-title":"A framework for human microbiome research","volume":"486","author":"Meth\u00e9","year":"2012","journal-title":"Nature"},{"key":"2023013108325540800_btz268-B40","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1016\/j.compbiolchem.2006.05.001","article-title":"SVM-based detection of distant protein structural relationships using pairwise probabilistic suffix trees","volume":"30","author":"O\u011ful","year":"2006","journal-title":"Comput. Biol. Chem"},{"key":"2023013108325540800_btz268-B41","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/978-3-642-16321-0_36","volume-title":"Proceedings of the 17th International Symposium on String Processing and Information Retrieval","author":"Ohlebusch","year":"2010"},{"key":"2023013108325540800_btz268-B42","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1093\/bioinformatics\/15.5.362","article-title":"Interpolated Markov chains for eukaryotic promoter recognition","volume":"15","author":"Ohler","year":"1999","journal-title":"Bioinformatics"},{"key":"2023013108325540800_btz268-B43","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1023\/A:1007670818503","article-title":"An efficient extension to mixture techniques for prediction and decision trees","volume":"36","author":"Pereira","year":"1999","journal-title":"Mach. Learn"},{"key":"2023013108325540800_btz268-B44","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1109\/TCBB.2016.2620143","article-title":"Efficient algorithms for sequence analysis with entropic profiles","volume":"15","author":"Pizzi","year":"2018","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023013108325540800_btz268-B45","doi-asserted-by":"crossref","first-page":"D501","DOI":"10.1093\/nar\/gki025","article-title":"NCBI reference sequence (RefSeq): a curated non-redundant sequence database of genomes, transcripts and proteins","volume":"33","author":"Pruitt","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2023013108325540800_btz268-B46","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1109\/TIT.1983.1056741","article-title":"A universal data compression system","volume":"29","author":"Rissanen","year":"1983","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2023013108325540800_btz268-B47","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1109\/TIT.1981.1056282","article-title":"Universal modeling and coding","volume":"27","author":"Rissanen","year":"1981","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2023013108325540800_btz268-B48","first-page":"791","volume-title":"Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP '97), vol. 2","author":"Ristad","year":"1997"},{"key":"2023013108325540800_btz268-B49","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1023\/A:1026490906255","article-title":"The power of amnesia: learning probabilistic automata with variable memory length","volume":"25","author":"Ron","year":"1996","journal-title":"Mach. Learn"},{"key":"2023013108325540800_btz268-B50","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1093\/nar\/26.2.544","article-title":"Microbial gene identification using interpolated Markov models","volume":"26","author":"Salzberg","year":"1998","journal-title":"Nucleic Acids Res"},{"key":"2023013108325540800_btz268-B51","author":"Schulz","year":"2007"},{"key":"2023013108325540800_btz268-B52","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1007\/978-3-540-87361-7_26","volume-title":"International Workshop on Algorithms in Bioinformatics","author":"Schulz","year":"2008"},{"key":"2023013108325540800_btz268-B53","first-page":"513","article-title":"Unsupervised sequence segmentation by a mixture of switching variable memory Markov sources","author":"Seldin","year":"2001","journal-title":"Proceedings of the 18th International Conference of Machine Learning (ICML)"},{"key":"2023013108325540800_btz268-B54","first-page":"2409","author":"Shareghi","year":"2015"},{"key":"2023013108325540800_btz268-B55","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1162\/tacl_a_00112","article-title":"Fast, small and exact: infinite-order language modelling with compressed suffix trees","volume":"4","author":"Shareghi","year":"2016","journal-title":"Trans. Assoc. Comput. Linguist"},{"key":"2023013108325540800_btz268-B56","first-page":"944","author":"Shareghi","year":"2016"},{"key":"2023013108325540800_btz268-B57","first-page":"381","author":"Singer","year":"1996"},{"key":"2023013108325540800_btz268-B58","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/978-3-540-89097-3_17","volume-title":"International Symposium on String Processing and Information Retrieval","author":"Sir\u00e9n","year":"2008"},{"key":"2023013108325540800_btz268-B59","first-page":"648","author":"Smyth","year":"1997"},{"key":"2023013108325540800_btz268-B60","article-title":"Engineering small space dictionary matching","author":"Sokol","year":"2013"},{"key":"2023013108325540800_btz268-B61","doi-asserted-by":"crossref","first-page":"410","DOI":"10.3389\/fmicb.2012.00410","article-title":"The binning of metagenomic contigs for microbial physiology of mixed cultures","volume":"3","author":"Strous","year":"2012","journal-title":"Front. Microbiol"},{"key":"2023013108325540800_btz268-B62","article-title":"Probability estimation for PPM","author":"Teahan","year":"1995"},{"key":"2023013108325540800_btz268-B63","doi-asserted-by":"crossref","first-page":"2196","DOI":"10.1093\/bioinformatics\/btl369","article-title":"Interpolated variable order motifs for identification of horizontally acquired DNA: revisiting the Salmonella pathogenicity islands","volume":"22","author":"Vernikos","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013108325540800_btz268-B64","doi-asserted-by":"crossref","first-page":"1002","DOI":"10.1109\/18.135641","article-title":"A sequential algorithm for the universal coding of finite memory sources","volume":"38","author":"Weinberger","year":"1992","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2023013108325540800_btz268-B65","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/18.382011","article-title":"A universal finite memory source","volume":"41","author":"Weinberger","year":"1995","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2023013108325540800_btz268-B66","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1109\/18.382012","article-title":"The context-tree weighting method: basic properties","volume":"41","author":"Willems","year":"1995","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2023013108325540800_btz268-B67","doi-asserted-by":"crossref","first-page":"1085","DOI":"10.1109\/18.87000","article-title":"The zero-frequency problem: estimating the probabilities of novel events in adaptive text compression","volume":"37","author":"Witten","year":"1991","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2023013108325540800_btz268-B68","doi-asserted-by":"crossref","first-page":"894","DOI":"10.1089\/cmb.2005.12.894","article-title":"Finding short DNA motifs using permuted Markov models","volume":"12","author":"Zhao","year":"2005","journal-title":"J. Comput. Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btz268\/28705237\/btz268.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/22\/4607\/48978898\/bioinformatics_35_22_4607.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/22\/4607\/48978898\/bioinformatics_35_22_4607.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T12:42:10Z","timestamp":1675168930000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/35\/22\/4607\/5475595"}},"subtitle":[],"editor":[{"given":"Inanc","family":"Birol","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2019,4,20]]},"references-count":68,"journal-issue":{"issue":"22","published-print":{"date-parts":[[2019,11,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btz268","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/443101","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2019,11,15]]},"published":{"date-parts":[[2019,4,20]]}}}