title: A tree-based approach for motif discovery and sequence classification.
abstract: BACKGROUND
  Pattern discovery algorithms are widely used for the analysis of DNA and protein sequences. Most algorithms have been designed to find overrepresented motifs in sparse datasets of long sequences, and ignore most positional information. We introduce an algorithm optimized to exploit spatial information in sparse-but-populous datasets.
  
  
  RESULTS
  Our algorithm Tree-based Weighted-Position Pattern Discovery and Classification (T-WPPDC) supports both unsupervised pattern discovery and supervised sequence classification. It identifies positionally enriched patterns using the Kullback-Leibler distance between foreground and background sequences at each position. This spatial information is used to discover positionally important patterns. T-WPPDC then uses a scoring function to discriminate different biological classes. We validated T-WPPDC on an important biological problem: prediction of single nucleotide polymorphisms (SNPs) from flanking sequence. We evaluated 672 separate experiments on 120 datasets derived from multiple species. T-WPPDC outperformed other pattern discovery methods and was comparable to the supervised machine learning algorithms. The algorithm is computationally efficient and largely insensitive to dataset size. It allows arbitrary parameterization and is embarrassingly parallelizable.
  
  
  CONCLUSIONS
  T-WPPDC is a minimally parameterized algorithm for both pattern discovery and sequence classification that directly incorporates positional information. We use it to confirm the predictability of SNPs from flanking sequence, and show that positional information is a key to this biological problem.
  
  
  BACKGROUND
  The algorithm, code and data are available at: http://www.cs.utoronto.ca/~juris/data/TWPPDC
authors.affiliation: Department of Computer Science, University of Toronto, Toronto, Canada M5S 3G4. ruiyan@cs.toronto.edu
authors.forename: Rui
authors.initials: R
authors.lastname: Yan
authors.forename: Paul C
authors.initials: PC
authors.lastname: Boutros
authors.forename: Igor
authors.initials: I
authors.lastname: Jurisica
mesh_terms: D000465:Algorithms; D000818:Animals; D001185:Artificial Intelligence; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D004247:DNA / Q000235:genetics; D006801:Humans; D051379:Mice; D020641:Polymorphism, Single Nucleotide; D017422:Sequence Analysis, DNA / Q000379:methods*
chemical_list: D004247:DNA