title: Finding subtle motifs by branching from sample strings.
abstract: Many motif finding algorithms apply local search techniques to a set of seeds. For example, GibbsDNA (Lawrence et al. 1993, Science, 262, 208-214) applies Gibbs sampling to random seeds, and MEME (Bailey and Elkan, 1994, Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology (ISMB-94), 28-36) applies the EM algorithm to selected sample strings, i.e. substrings of the sample. In the case of subtle motifs, recent benchmarking efforts show that both random seeds and selected sample strings may never get close to the globally optimal motif. We propose a new approach which searches motif space by branching from sample strings, and implement this idea in both pattern-based and profile-based settings. Our PatternBranching and ProfileBranching algorithms achieve favorable results relative to other motif finding algorithms.
  
  
  BACKGROUND
  http://www-cse.ucsd.edu/groups/bioinformatics/software.html
authors.affiliation: Department of Computer Science and Engineering, University of California at San Diego, La Jolla, CA 92093-0114, USA. aprice@cs.ucsd.edu
authors.forename: Alkes
authors.initials: A
authors.lastname: Price
authors.forename: Sriram
authors.initials: S
authors.lastname: Ramabhadran
authors.forename: Pavel A
authors.initials: PA
authors.lastname: Pevzner
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D000595:Amino Acid Sequence; D001483:Base Sequence; D008969:Molecular Sequence Data; D011506:Proteins / Q000737:chemistry* / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*
chemical_list: D011506:Proteins