"VOGUE: A Novel Variable Order-Gap State Machine
For Modeling Sequences"
Bouchra Bouqata.
Ph.D. Thesis, Department of Computer Science, Rensselaer
Polytechnic Institute, September 2006.
ABSTRACT
In this thesis we present VOGUE, a new state machine that combines two
separate techniques for modeling complex patterns in sequential data:
data mining and data modeling. VOGUE relies on a novel Variable-Gap
Sequence miner (VGS), to mine frequent patterns with different lengths
and gaps between elements. It then uses these mined sequences to build
the state machine. Moreover, we propose two variations of VOGUE:
C-VOGUE that tends to decrease even further the state space complexity
of VOGUE by pruning frequent sequences that are artifacts of other
primary frequent sequences; and K-VOGUE that allows for sequences to
form the same frequent pattern even if they do not have an exact match
of elements in all the positions. However, the different elements
have to share similar characteristics. We apply VOGUE to the task of
protein sequence classification on real data from the PROSITE and SCOP
protein families. We show that VOGUEs classification sensitivity
outperforms that of higher-order Hidden Markov Models and of HMMER, a
state-of-the-art method for protein classification, by decreasing the
sate space complexity and improving the accuracy and coverage.