title: Finding optimal degenerate patterns in DNA sequences.
abstract: BACKGROUND
  The problem of finding transcription factor binding sites in the upstream regions of given genes is algorithmically an interesting and challenging problem in computational biology. A degenerate pattern over a finite alphabet Sigma is a sequence of subsets of Sigma. A string over IUPAC nucleic acid codes is also a degenerate pattern over Sigma = {A, C, G, T}, and is used as one of the major patterns modeling transcription factor binding sites in the upstream regions of genes. However, it is known that the problem of finding a degenerate pattern consistent with both positive and negative string sets is in general NP-complete. Our aim is to devise a heuristic algorithm to find a degenerate pattern which is optimal for positive and negative string sets w.r.t. a given score function.
  
  
  RESULTS
  We have proposed an enumerative algorithm called SUPERPOSITION for finding optimal degenerate patterns with a pruning technique, which works with most all reasonable score functions. The performance score of the algorithm has been compared with those of other popular motif-finding algorithms YMF, MEME and AlignACE on various sets of co-regulated genes of yeast. In the computational experiment, SUPERPOSITION has outperformed the others on several gene sets.
  
  
  BACKGROUND
  The python script SUPERPOSITION is available at http://www.math.kyushu-u.ac.jp/~om/softwares.html
authors.affiliation: Graduate School of Mathematics, Kyushu University, Fukuoka, Japan.
authors.forename: Daisuke
authors.initials: D
authors.lastname: Shinozaki
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
authors.forename: Osamu
authors.initials: O
authors.lastname: Maruyama
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D001665:Binding Sites; D002874:Chromosome Mapping / Q000379:methods*; D004252:DNA Mutational Analysis / Q000379:methods; D008969:Molecular Sequence Data; D009154:Mutation; D011485:Protein Binding; D050436:Regulatory Elements, Transcriptional / Q000235:genetics*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software; D014157:Transcription Factors / Q000235:genetics*; D014158:Transcription, Genetic / Q000235:genetics*
chemical_list: D014157:Transcription Factors