Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой
Проблема обнаружения и идентификации наборов фрагментов
Структура последовательности (модель без вставок):
-, m Î {1,...,M};
Y = X(n1,...,nM, U1,...,UL) + E;
(U1,...,UL) Î Wp – повторяющийся набор эталонных векторов (фрагментов),
Wp – совокупность (словарь) эталонных наборов, |Wp| = Kp
, Wp Î {W1,...,WP} (словарь допустимых наборов).
Имеем следующие варианты задач
Задан словарь наборов | ||||||||
вставок нет |
имеются вставки |
|||||||
задан алфавит вставок B |
множество вставок не ограничено |
|||||||
число вставок J |
=0 |
изв. |
неизв. |
изв. |
неизв. |
|||
по-теря дан-ных |
нет | число фраг- ментов M
|
изв. |
? |
? |
? |
? |
? |
неизв. | ? | ? | ? | ? | ? | |||
есть | изв. | ? | ? | ? | ? | ? | ||
неизв. | ? | ? | ? | ? | ? |
Здесь используются следующие обозначения: |
|
+ |
– обоснован точный полиномиальный алгоритм; |
? |
– статус сложности не выяснен, какие либо алгоритмы неизвестны. |
предыдущая |
следующая |