Locating Transcription Factors Binding Sites Using a Variable Memory Markov Model. Leibintz Center TR 2002-57. Also available at http://www.cs.huji.ac.il/~johnblue/papers/ Blattner

We propose a novel method for locating tran-scription factors binding sites in upstream regions, by employing a variable memory Markov model (VMM) based feature selec-tion method. Using this method we nd a set of features which discriminate well be-tween genes upstream sequences and random sequences. and give each feature a score based on its discriminatory power. We pre-dict that regions in which high-scoring fea-tures are abundant, will be well correlated with transcription factors ' binding sites. We propose a rather strict benchmark for com-paring such predictions with known Data. Rather than look for consensus sequences, we go over the upstream sequences (of Sac-charomyces Cerevisiae), where some binding sites are known (according to the SCPD), and try to nd these sites. Our results are consis-tently and signicantly better than random, and are comparable with those one gets when using MatInspector to make such prediction. MatInspector is a software that looks for speci ed consensus pattern in a DNA se-quence. In contrast with it, our method is completely unsupervised and does not re-quire any prior knowledge about the data. 1