Поиск сложных непериодических шаблонов в последовательностях чисел и символов

В докладе приводится ряд примеров решения задач поиска сложных непериодических шаблонов в числовых и символьных последовательностях из областей молекулярной биологии и электрофизиологии

Методы анализа последовательностей – временных или иных рядов чисел и символов – в настоящее время испытывают определенные затруднения. Специалисты отмечают, что несколько основных моделей, используемых при таком анализе, оказались плохо совместимыми друг с другом по базовым посылкам. Например, для числовых рядов Фурье-анализ требует отсутствия непериодических составляющих, методы Бокса чувствительны к виду одномерных распределений и т.д. Алгоритмы поиска закономерностей в последовательностях символов основываются на переборах, которые можно реализовать только в очень ограниченных вариантах, либо опираются на сильные эвристические допущения.

Продуктивным направлением анализа временных рядов сегодня является подход, связанный с преобразованием временного ряда в матрицу с помощью процедуры “Гусеница”. Этот подход независимо разрабатывался в России (Санкт-Петербург, Москва) и США (там его аналог получил название SSA – Singular Spectrum Analysis) и показал себя мощным средством исследования временных рядов (в основном в метеорологии, гидрологии, климатологии).

Алгоритм преобразования временного ряда в матрицу данных заключается в следующем.

Анализу подвергается временной ряд , образованный последовательностью N равноотстоящих значений некоторой (возможно, случайной) функции f(t):

, где i = 1, 2,…, N.

Выбирают некоторое число M<N , называемое длиной гусеницы, и первые M значений последовательности f представляют в качестве первой строки матрицы X . В качестве второй строки матрицы берут значения последовательности с x₂ по x_M+1. Последнюю строку с номером k = N - M + 1 составляют последние M элементов последовательности.

Построенную матрицу, элементы которой равны x_ij = x_i+j-1, можно рассматривать как M-мерную выборку объема k или M-мерный временной ряд, которому соответствует M-мерная траектория (ломаная в M-мерном пространстве из k-1 звена. Матрица X (ее называют матрицей ряда) представлена в традиционном для прикладной статистики виде “строка – объект, столбец – признак”. Для ее дальнейшей обработки теперь можно применять различные методы из богатого арсенала математического аппарата многомерного анализа.

Вместе с тем, продуктивным для анализа закономерностей временного ряда оказалось применение технологии обнаружения логических закономерностей на основе представлений локальной геометрии. Как отмечалось ранее, на основе этой технологии удается отыскивать лучшие (наиболее полные при заданной точности) if-then правила для каждой строчки матрицы данных (в контексте задачи анализа многомерного ряда if-then правила выражают его отличие от случайно сгенерированной матрицы данных). С помощью указанной технологии в последовательностях чисел или символов, преобразованных процедурой “Гусеница” в многомерные матрицы, отыскиваются различные (в том числе сложной формы) периодические и непериодические шаблоны (паттерны).