Fast and Adaptive Variable Order Markov Chain Construction

Abstract

Variable order Markov chains (VOMCs) are a flexible class of models that extend the well-known Markov chains. They have been applied to a variety of problems in computational biology, e.g. protein family classification. A linear time and space construction algorithm has been published in 2000 by Apostolico and Bejerano. However, neither a report of the actual running time nor an implementation of it have ever been published since. Using their theoretical results, we implement general and problem oriented algorithms considering recent advances in string matching. We introduce a new software which is orders of magnitudes faster than current tools for building VOMCs, and is suitable for large scale analysis. Along the way we show that the lazy suffix tree algorithm by Giegerich and others can compete with state-of-the-art suffix array methods in terms of time and space under the type of constraints we have analyzed in this work.