title: Motif finding in DNA sequences based on skipping nonconserved positions in background Markov chains.
abstract: One strategy to identify transcription factor binding sites is through motif finding in upstream DNA sequences of potentially co-regulated genes. Despite extensive efforts, none of the existing algorithms perform very well. We consider a string representation that allows arbitrary ignored positions within the nonconserved portion of single motifs, and use O(2(l)) Markov chains to model the background distributions of motifs of length l while skipping these positions within each Markov chain. By focusing initially on positions that have fixed nucleotides to define core occurrences, we develop an algorithm to identify motifs of moderate lengths. We compare the performance of our algorithm to other motif finding algorithms on a few benchmark data sets, and show that significant improvement in accuracy can be obtained when the sites are sufficiently conserved within a given sample, while comparable performance is obtained when the site conservation rate is low. A software program (PosMotif ) and detailed results are available online at http://faculty.cse.tamu.edu/shsze/posmotif.
authors.affiliation: Department of Computer Science & Engineering, Texas A&M University, College Station, Texas 77843, USA.
authors.forename: Xiaoyan
authors.initials: X
authors.lastname: Zhao
authors.forename: Sing-Hoi
authors.initials: SH
authors.lastname: Sze
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D001665:Binding Sites; D008390:Markov Chains; D008969:Molecular Sequence Data; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software; D014157:Transcription Factors / Q000378:metabolism
chemical_list: D014157:Transcription Factors