Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой


Проблема обнаружения и идентификации наборов фрагментов

 

Структура последовательности (модель без вставок):

 

l(m | L) = (m-1) mod L+1,   m Î {1,...,M};

Y = X(n1,...,nM, U1,...,UL) + E;

(U1,...,UL) Î Wp повторяющийся набор эталонных векторов (фрагментов),

Wp совокупность (словарь) эталонных наборов, |Wp| = Kp, Wp Î {W1,...,WP} (словарь допустимых наборов).

 

Имеем следующие варианты задач

 
Задан словарь наборов

вставок нет

имеются вставки

 

задан алфавит

вставок

B

множество

вставок не

ограничено

число вставок J

=0

изв.

неизв.

изв.

неизв.

по-теря

дан-ных

нет число

фраг-

ментов

M

 

изв.

?

?

?

?

?

неизв. ? ? ? ? ?
есть изв. ? ? ? ? ?
неизв. ? ? ? ? ?

 

 Здесь используются следующие обозначения:

+

  обоснован точный полиномиальный алгоритм;

?

  статус сложности не выяснен, какие либо алгоритмы неизвестны.

 


начало страницы

предыдущая

следующая

главная страница