title: A graph-based motif detection algorithm models complex nucleotide dependencies in transcription factor binding sites.
abstract: Given a set of known binding sites for a specific transcription factor, it is possible to build a model of the transcription factor binding site, usually called a motif model, and use this model to search for other sites that bind the same transcription factor. Typically, this search is performed using a position-specific scoring matrix (PSSM), also known as a position weight matrix. In this paper we analyze a set of eukaryotic transcription factor binding sites and show that there is extensive clustering of similar k-mers in eukaryotic motifs, owing to both functional and evolutionary constraints. The apparent limitations of probabilistic models in representing complex nucleotide dependencies lead us to a graph-based representation of motifs. When deciding whether a candidate k-mer is part of a motif or not, we base our decision not on how well the k-mer conforms to a model of the motif as a whole, but how similar it is to specific, known k-mers in the motif. We elucidate the reasons why we expect graph-based methods to perform well on motif data. Our MotifScan algorithm shows greatly improved performance over the prevalent PSSM-based method for the detection of eukaryotic motifs.
authors.affiliation: Department of Biochemistry, Stanford University, CA 94305, USA. briannau@stanford.edu
authors.forename: Brian T
authors.initials: BT
authors.lastname: Naughton
authors.forename: Eugene
authors.initials: E
authors.lastname: Fratkin
authors.forename: Serafim
authors.initials: S
authors.lastname: Batzoglou
authors.forename: Douglas L
authors.initials: DL
authors.lastname: Brutlag
mesh_terms: D000465:Algorithms; D001665:Binding Sites; D015870:Gene Expression; D006801:Humans; D008957:Models, Genetic; D015233:Models, Statistical; D009711:Nucleotides / Q000032:analysis; D050436:Regulatory Elements, Transcriptional; D012441:Saccharomyces cerevisiae / Q000235:genetics; D017422:Sequence Analysis, DNA / Q000379:methods*; D014157:Transcription Factors / Q000378:metabolism*
chemical_list: D009711:Nucleotides; D014157:Transcription Factors