Parallel Construction of Variable-Length Markov Chains
Title: Parallel Construction of Variable-Length Markov Chains
DNr: NAISS 2023/5-61
Project Type: NAISS Medium Compute
Principal Investigator: Alexander Schliep <>
Affiliation: Göteborgs universitet
Duration: 2023-02-24 – 2024-03-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 methods for the computation and comparisons 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. We are further exploring applications of the variable-length Markov chains in the domain of alignment-free sequence comparisons.