title: On avoided words, absent words, and their application to biological sequence analysis.
abstract: BACKGROUND
  The deviation of the observed frequency of a wordwfrom its expected frequency in a given sequencexis used to determine whether or not the word isavoided. This concept is particularly useful in DNA linguistic analysis. The value of the deviation ofw, denoted by [Formula: see text], effectively characterises the extent of a word by its edge contrast in the context in which it occurs. A wordwof length [Formula: see text] is a [Formula: see text]-avoided word inxif [Formula: see text], for a given threshold [Formula: see text]. Notice that such a word may be completelyabsentfromx. Hence, computing all such words naïvely can be a very time-consuming procedure, in particular for largek.
  
  
  RESULTS
  In this article, we propose an [Formula: see text]-time and [Formula: see text]-space algorithm to compute all [Formula: see text]-avoided words of lengthkin a given sequence of lengthnover a fixed-sized alphabet. We also present a time-optimal [Formula: see text]-time algorithm to compute all [Formula: see text]-avoided words (of any length) in a sequence of lengthnover an integer alphabet of size [Formula: see text]. In addition, we provide a tight asymptotic upper bound for the number of [Formula: see text]-avoided words over an integer alphabet and the expected length of the longest one. We make available an implementation of our algorithm. Experimental results, using both real and synthetic data, show the efficiency and applicability of our implementation in biological sequence analysis.
  
  
  CONCLUSIONS
  The systematic search for avoided words is particularly useful for biological sequence analysis. We present a linear-time and linear-space algorithm for the computation of avoided words of lengthkin a given sequencex. We suggest a modification to this algorithm so that it computes all avoided words ofx, irrespective of their length, within the same time complexity. We also present combinatorial results with regards to avoided words and absent words.
authors.affiliation: National Center for Scientific Research Demokritos, Neapoleos, 153 10 Athens, Greece.
authors.forename: Yannis
authors.initials: Y
authors.lastname: Almirantis
authors.affiliation: Department of Informatics, King's College London, The Strand, London, WC2R 2LS UK.
authors.forename: Panagiotis
authors.initials: P
authors.lastname: Charalampopoulos
authors.affiliation: Department of Informatics, King's College London, The Strand, London, WC2R 2LS UK.
authors.forename: Jia
authors.initials: J
authors.lastname: Gao
authors.affiliation: Department of Informatics, King's College London, The Strand, London, WC2R 2LS UK.
authors.forename: Costas S
authors.initials: CS
authors.lastname: Iliopoulos
authors.affiliation: Department of Informatics, King's College London, The Strand, London, WC2R 2LS UK.
authors.forename: Manal
authors.initials: M
authors.lastname: Mohamed
authors.affiliation: Department of Informatics, King's College London, The Strand, London, WC2R 2LS UK.
authors.forename: Solon P
authors.initials: SP
authors.lastname: Pissis
authors.affiliation: Computational Regulatory Genomics, MRC Clinical Sciences Centre (CSC), Du Cane Road, London, W12 0NN UK.
authors.forename: Dimitris
authors.initials: D
authors.lastname: Polychronopoulos
keywords: Absent words; Avoided words; Conserved non-coding elements; Suffix tree; Ultraconserved elements; Underrepresented words