АПОСТЕРИОРНОЕ ОБНАРУЖЕНИЕ КВАЗИПЕРИОДИЧЕСКИХ ФРАГМЕНТОВ ИЗ ЭТАЛОННОГО НАБОРА В ЧИСЛОВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ

摘要

Рассматривается апостериорный подход к решению задачи совместного обнаружения квазипериодических фрагментов (заданного размера) из эталонного набора в числовой последовательности и ее разбиения на участки, включающие серии повторяющихся фрагментов из этого набора. Проанализирован такой случай: 1) число искомых фрагментов неизвестно, 2) задан упорядоченный эталонный набор последовательностей, которые в качестве фрагментов входят в состав числовой последовательности и подлежат обнаружению, 3) номер члена последовательности, соответствующий началу фрагмента, - детерминированная (не случайная) величина, 4) для наблюдения доступна последовательность, искаженная аддитивной гауссо-вской некоррелированной помехой. Установлено, что рассматриваемая задача состоит в проверке совокупности гипотез о среднем случайного гауссовского вектора; мощность этой совокупности экспоненциально растет при увеличении размерности вектора, т.е. длины последовательности. Показано, что поиск максимально правдоподобной гипотезы эквивалентен отысканию аргументов, доставляющих минимум вспомогательной целевой функции. Доказано, что задача минимизации этой функции разрешима за полиномиальное время. Обоснован точный алгоритм ее решения. Предложен эффективный алгоритм апостериорного типа, гарантирующий оптимальное (максимально правдоподобное) разбиение последовательности на серии повторяющихся фрагментов и обнаружение этих фрагментов; его ядром является решение вспомогательной экстремальной задачи. Результатами численного моделирования продемонстрирована помехоустойчивость алгоритма.