* Faculty       * Staff       * Contact       * Institute Directory
* Research Groups      
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Events       * Institute Events      
* Lab Manual       * Institute Computing      
No Menu Selected

* Research

Ph.D. Theses

VOGUE: A Novel Variable Order-Gap State Machine For Modeling Sequences

By Bouchra Bouqata
Advisor: Christopher Carothers
August 31, 2006

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 VOGUE's 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.

* Return to main PhD Theses page