"Build a Dictionary, Learn a Grammar, Discover Hidden Motifs, and Decipher a Stego Script"

4/23/2004: 10:30am - 12:00pm
10th FL Conference Room

Abstract: Steganography, or information hiding, is to conceal the existence of messages so as to protect their confidentiality. We consider deciphering a stego script, a text with secret messages embedded within a covertext, and identifying the vocabularies used in the messages, with no knowledge of the vocabularies and grammar in which the script was written. Our research was motivated by the problem of identifying conserved non-coding functional elements in genome sequences, which we hypothesize to be constructed by nature using a dictionary of vocabularies (motifs) and a set of grammatical rules of constructing long words from short ones. Our approach identifies significant motifs, which form a dictionary, while learning a stochastic grammar from a stego script, and then applies the dictionary and grammar to identify the embedded secret messages. We apply our algorithm, called WordSpy, to recover the most possible text of the first ten chapters of a novel embedded in a stego script and identify the transcription factor binding motifs in the upstream regions of ~800 genes in budding yeast. This is a joint work with Guandong Wang

About Weixiong Zhang: Dr. Weixiong Zhang is Associate Professor in computer science and genetics at Washington University in Saint Louis. He received his B.S. and M.S. in computer engineering from Tsinghua University, Beijing, China, and his Ph.D. in computer science from UCLA. From 1994 to 2000, he was Senior Scientist at Information Sciences Institute of USC and research assistant professor at USC. Dr. Zhang's research areas include artificial intelligence (e.g., heuristic search, distributed multiagent systems), combinatorial optimization (e.g., TSP and Boolean satisfiability) and computational biology (e.g., RNA folding, targeted gene finding, transcription factor binding motif finding, noncoding small RNA genes, and gene regulatory networks).

Last updated: Mon Jun 19 17:44:06 2006