Repository: Freie Universität Berlin, Math Department

Fast and Adaptive Variable Order Markov Chain Construction

Schulz, M. H. and Weese, D. and Rausch, T. and Döring, A. and Reinert, K. and Vingron, M. (2008) Fast and Adaptive Variable Order Markov Chain Construction. In: Proceedings of the 8th International Workshop in Algorithms in Bioinformatics (WABI'08).

Full text not available from this repository.


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.

Item Type:Conference or Workshop Item (UNSPECIFIED)
Subjects:Mathematical and Computer Sciences > Computer Science
Divisions:Department of Mathematics and Computer Science > Institute of Computer Science > Algorithmic Bioinformatics Group
ID Code:401
Deposited By: Admin Administrator
Deposited On:15 Apr 2009 07:15
Last Modified:15 Apr 2009 07:16

Repository Staff Only: item control page