title: RefSelect: a reference sequence selection algorithm for planted (l, d) motif search.
abstract: BACKGROUND
  The planted (l, d) motif search (PMS) is an important yet challenging problem in computational biology. Pattern-driven PMS algorithms usually use k out of t input sequences as reference sequences to generate candidate motifs, and they can find all the (l, d) motifs in the input sequences. However, most of them simply take the first k sequences in the input as reference sequences without elaborate selection processes, and thus they may exhibit sharp fluctuations in running time, especially for large alphabets.
  
  
  RESULTS
  In this paper, we build the reference sequence selection problem and propose a method named RefSelect to quickly solve it by evaluating the number of candidate motifs for the reference sequences. RefSelect can bring a practical time improvement of the state-of-the-art pattern-driven PMS algorithms. Experimental results show that RefSelect (1) makes the tested algorithms solve the PMS problem steadily in an efficient way, (2) particularly, makes them achieve a speedup of up to about 100× on the protein data, and (3) is also suitable for large data sets which contain hundreds or more sequences.
  
  
  CONCLUSIONS
  The proposed algorithm RefSelect can be used to solve the problem that many pattern-driven PMS algorithms present execution time instability. RefSelect requires a small amount of storage space and is capable of selecting reference sequences efficiently and effectively. Also, the parallel version of RefSelect is provided for handling large data sets.
authors.affiliation: School of Computer Science and Technology, Xidian University, Xi'an, 710071, China.
authors.forename: Qiang
authors.initials: Q
authors.lastname: Yu
authors.affiliation: School of Computer Science and Technology, Xidian University, Xi'an, 710071, China. hwhuo@mail.xidian.edu.cn.
authors.forename: Hongwei
authors.initials: H
authors.lastname: Huo
authors.affiliation: School of Computer Science and Technology, Xidian University, Xi'an, 710071, China.
authors.forename: Ruixing
authors.initials: R
authors.lastname: Zhao
authors.affiliation: School of Electronic Engineering, Xidian University, Xi'an, 710071, China.
authors.forename: Dazheng
authors.initials: D
authors.lastname: Feng
authors.affiliation: Department of Computer and Information Science, The University of Mississippi, Oxford, MS, 38677-1848, USA.
authors.forename: Jeffrey Scott
authors.initials: JS
authors.lastname: Vitter
authors.affiliation: Department of Electrical Engineering and Computer Science, the University of Kansas, Lawrence, KS, 66045, USA.
authors.forename: Jun
authors.initials: J
authors.lastname: Huan
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D019295:Computational Biology / Q000379:methods*; D000072417:Protein Domains; D011506:Proteins / Q000737:chemistry* / Q000235:genetics; D020539:Sequence Analysis, Protein; D012984:Software
chemical_list: D011506:Proteins
keywords: Pattern-driven; Planted (l, d) motif search; Reference sequences