U маленький алфавит 0, 1 или A, C, G, T, k <= n.Минимальный интервал измерения Хэмминга
Я хочу найти минимальное расстояние Хэмминга между u = (u_1,...,u_k) и смежными подпоследовательностями v = (v_1,...,v_n) длиной k во время O(n log n).
Возможно ли это?
Благодарим за помощь!
Для алфавита {1, -1}, умножать многочлены
(u_k + u_{k-1} x + u_{k-2} x^2 + ... + u_1 x^{k-1})
и
(v_1 + v_2 x + v_3 x^2 + ... + v_n x^{n-1}).
Коэффициент x^i в продукте является простым аффинная функция расстояния Хэмминга между u_1 ... u_k и v_{i-k+2} ... v_{i+1}.
Мы можем кодировать другие алфавиты, встраивая их, чтобы сделать Хэмминг расстояние работать, например,
A -> 0000
C -> 0011
G -> 0101
T -> 1001.
Если это позволяет предварительной обработке 'V', что бы ограничение по времени и пространству? Не считая фиксированного k, он может отображаться в функции, описывающей рост сложности с размером проблемы. См., Например, [Википедия об оптимальном выравнивании строк] (https://en.wikipedia.org/wiki/Hirschberg's_algorithm). (Приветствия и aTdHvAaNnKcSe не приветствуются здесь.) – greybeard
Нет, 'k' не исправлено. Например, если 'k = n/2', то в алгоритме Гиршберга время' O (n^2) ' –