Longest Biased Interval |
|
1. Rational BiasProblem:
Given a data sequence, e.g. ACGTAGCAGATAGACAGGTTAGACAATAGAG,
and a "bias" criterion, In the HTML-form below, the fraction is p/q where p and q are small integers which (for given p and q) yields a simple, special-case, linear-time algorithm (but the multiplier depends on p and q). key: `choice' -- acceptable characters. `p' and `q' -- p/q is the required fraction of acceptable characters. 2. General BiasGive elements of the sequence a +ve value for "good" and a -ve value for "bad". Compute the cumulative sums from the start of the sequence. The sum of a "good enough" interval is non-negative, i.e. the cumulative sum is flat or increasing across the interval: e.g. required ratio = 1/2
e.g. required ratio = 2/3 (good = +1/3, bad = -2/3) The following HTML-form implements a general algorithm for biases that are not necessarily rational. Its time-complexity is almost always O(n), but can be O(n2) in the worst case for ``pathalogical'' sequences. Note that some numbers, including some common rational numbers, cannot be represented exactly in floating-point. Therefore one might need to give `ratio' a (very, very,) very little ``slack''. 3. NotesUsing binary-search to search (track) the array of cumulative-sum minima would give an O(n.log(n))-time, O(n)-space algorithm. So of course, one could run both algorithms
in parallel and take the result from the first to finish
(also halting the other one):
O(n)-time usually and
O(n.log(n))-time worst case 4. ReferenceL. Allison,
Longest Biased Interval and Longest Non-Negative Sum Interval,
© 3/2002, 3/2003, 4/2003. |
|
|