title: A statistical method for alignment-free comparison of regulatory sequences.
abstract: BACKGROUND
  The similarity of two biological sequences has traditionally been assessed within the well-established framework of alignment. Here we focus on the task of identifying functional relationships between cis-regulatory sequences that are non-orthologous or greatly diverged. 'Alignment-free' measures of sequence similarity are required in this regime.
  
  
  RESULTS
  We investigate the use of a new score for alignment-free sequence comparison, called the score. It is based on comparing the frequencies of all fixed-length words in the two sequences. An important, novel feature of the score is that it is comparable across sequence pairs drawn from arbitrary background distributions. We present a method that gives quadratic improvement in the time complexity of calculating the score, over the naïve method. We then evaluate the score on several tissue-specific families of cis-regulatory modules (in Drosophila and human). The new score is highly successful in discriminating functionally related regulatory sequences from unrelated sequence pairs. The performance of the score is compared to five other alignment-free similarity measures, and shown to be consistently superior to all of these measures.
  
  
  BACKGROUND
  Our implementation of the score will be made freely available as source code, upon publication of this article, at: http://veda.cs.uiuc.edu/d2z/.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Computer Science, University of Illinois, Urbana-Champaign, Illinois, USA.
authors.forename: Miriam R
authors.initials: MR
authors.lastname: Kantorovitz
authors.forename: Gene E
authors.initials: GE
authors.lastname: Robinson
authors.forename: Saurabh
authors.initials: S
authors.lastname: Sinha
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D003627:Data Interpretation, Statistical; D008957:Models, Genetic; D015233:Models, Statistical; D012045:Regulatory Sequences, Nucleic Acid / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid