Пятницкий А.М., Гукасов В.М.

СТАТИСТИЧЕСКИ МОТИВИРОВАННЫЙ ПОИСК КЛАСТЕРОВ СОБЫТИЙ В ПОСЛЕДОВАТЕЛЬНОСТЯХ И АНАЛИЗ МЕДИКО-БИОЛОГИЧЕСКИХ ДАННЫХ

Резюме: Задача поиска кластеров в последовательностях возникает при анализе различных медико-биологических данных. Это может быть поиск кластеров событий (вспышек событий) в эпидемиологии, поиск областей повышенной частоты мутаций в нуклеотидной последовательности и т.д. Для случая непрерывного времени поиск сгущений и разряжений в потоке событий был рассмотрен нами ранее. В данной публикации задача поиска кластеров решается для дискретного времени. В качестве нулевых гипотез, предполагающих отсутствие кластеров, рассматриваются модель независимых испытаний и модель однородной марковской цепи с двумя состояниями. События, отстоящие друг от друга меньше, чем на некоторое фиксированное расстояние, объединяются в компоненты, каждый из которых характеризуется двумя числами – общим число составляющих его событий и компактностью, измеряющейся общим числом моментов времени, когда событий не было (числом пустых ячеек). На плоскости – (число точек, компактность) с учетом множественных сравнений строится критическая область, и слишком большие или слишком компактные компоненты признаются значимыми кластерами. Предлагаемый метод сравнивается с популярным в эпидемиологии методом сканирующей статистики и с распространенным в биоинформатике методом, основанным на модели скрытой марковской цепи и алгоритме Витерби. В отличие от метода сканирующей статистики предлагаемый метод может искать несколько кластеров. Эффективность предлагаемого метода сравнима с методом Витерби, однако его важным преимуществом является то, что нет необходимости оценивать параметры скрытой марковской цепи, что можно сделать лишь, имея очень большую обучающую выборку.

Ключевые слова: статистически мотивированный поиск кластеров, вспышка событий, двумерная критическая область, ретроспективный поиск точек разладки, сканирующая статистика, сегментация скрытой марковской цепи, алгоритм Витерби.

A.M. Pyatnitskiy, V.M. Gukasov

STATISTICALLY MOTIVATED SEARCH FOR CLUSTERS OF EVENTS IN SEQUENCES AND ANALYSIS OF BIOMEDICAL DATA

Summary: The task of searching for clusters in sequences arises when analyzing various medical and biological data. This may be searching for clusters of events (outbreaks of events) in epidemiology, searching for areas of increased mutation frequency in a nucleotide sequence, etc. For the case of continuous time, the search for condensations and rarefactions in the event flow was considered by us earlier. In this publication, the problem of finding clusters is solved for discrete time. The independent trials model and the homogeneous two-state Markov chain model are considered as null hypotheses assuming the absence of clusters. Events that are separated from each other by less than some fixed distance are combined into components, each of which is characterized by two numbers — the total number of events that make it up and compactness, measured by the total number of moments in time when there were no events (the number of empty cells). The critical region is constructed on the plane — (number of points, compactness) taking into account multiple comparisons, and too large or too compact components are recognized as significant clusters. The proposed method is compared with the scanning statistics method popular in epidemiology and with the method common in bioinformatics based on the hidden Markov chain model and the Viterbi algorithm. Unlike the scanning statistics method, the proposed method can search for several clusters. The efficiency of the proposed method is comparable to the Viterbi method, but its important advantage is that there is no need to estimate the parameters of the hidden Markov chain, which can only be done with a very large training sample.

Keywords: statistically motivated search for clusters, outbreak of events, two-dimensional critical region, rеtrospective change point detection, scanning statistics, segmentation of hidden Markov chain, Viterbi algorithm.

DOI: 10.34219/2306-3645-2025-15-1-7-18

Пятницкий Алексей Михайлович – кандидат физико-математических наук, доцент; ФГАОУ ВО РНИМУ «Российский национальный исследовательский медицинский университет имени Н.И. Пирогова»
Минздрава России, e-mail: alpyat@bk.ru

Гукасов Вадим Михайлович – доктор биологических наук, главный научный сотрудник, ФГБНУ НИИ Республиканский исследовательский научно-консультационный центр экспертизы, e-mail: v_m_gukasov@mail.ru

Pyatnitskiy, Alexey M. – Ph.D., Associate Professor, De- partment of Higher Mathematics, PRNRMU, Moscow,
e-mail: alpyat@bk.ru

Gukasov v.M. – Doctor of Biological Sciences, Chief Researcher, Pirogov Russian National Research Medical University,
e-mail: v_m_gukasov@mail.ru