Optimal Computation of Avoided Words
Abstract
The deviation of the observed frequency of a word w from its
expected frequency in a given sequence x is used to determine whether
or not the word is avoided. This concept is particularly useful in DNA
linguistic analysis. The value of the standard deviation of w, denoted by
std(w), effectively characterises the extent of a word by its edge contrast
in the context in which it occurs. A word w of length k > 2 is a ρ-avoided
word in x if std(w) ≤ ρ, for a given threshold ρ < 0. Notice that such a
word may be completely absent from x. Hence computing all such words
naïvely can be a very time-consuming procedure, in particular for large
k. In this talk, we propose an O(n)-time and O(n)-space algorithm
to compute all ρ-avoided words of length k in a given sequence x of
length n over a fixed-sized alphabet. We also present a time-optimal
O(σn)-time algorithm to compute all ρ-avoided words (of any length) in
a sequence of length n over an integer alphabet of size σ.
Bio
http://www.inf.kcl.ac.uk/staff/solon/
Date: 2016-Jun-28 Time: 14:00:00 Room: 408
For more information:
- luis.russo@tecnico.ulisboa.pt
- 21 31 00272
