Parallel Construction of Variable-Length Markov Chains
Title: Parallel Construction of Variable-Length Markov Chains
SNIC Project: SNIC 2021/5-49
Project Type: SNIC Medium Compute
Principal Investigator: Alexander Schliep <>
Affiliation: Göteborgs universitet
Duration: 2021-02-01 – 2022-02-01
Classification: 10203


The variable-length Markov chain is an extension of the Markov chain where the memory of the model can vary. The chains have applications in, e.g. bioinformatics where they are used to model genome sequences. However, existing methods are either slow or highly memory-intensive. Moreover, a faster implementation has since its development in 2005 been lost. We are developing a new method for the computation of the variable-length Markov chain based on the lost version, but with a focus on parallelisation. This method's goal is to be faster than the current methods and not require much more memory.