Алгоритм вычисления $P$-значения числа вхождений образцов в случайной последовательности. Минимизация графа перекрытий

Разработан алгоритм MinSufPref для нахождения вероятности ($P$-значения) обнаружения $S$ вхождений слов из набора $\mathcal{H}$ в случайной последовательности длины $N$. $P$-значение широко используется в компьютерных науках в качестве критерия для отбора слов-образцов определенного вида. В частности, в биоинформатике при поиске функциональных фрагментов в биологических последовательностях. Предложенный алгоритм основан на ранее разработанном алгоритме SufPref для вычисления точного $P$-значения. Алгоритм SufPref использует для вычислений граф перекрытий, вершины которого соответствуют словам из $\mathcal{H}$ и их перекрытиям. Ограничения SufPref состоят в том, что он допускает лишь наборы, состоящие из слов одинаковой длины, а также в ряде случаев не применим для наборов, состоящих из большого числа слов. В данной работе алгоритм расширен на наборы, состоящие из слов произвольных длин, с ограничением в том, что ни одно слово не должно быть фрагментом другого слова. Кроме того, на множестве префиксов слов из $\mathcal{H}$ введено отношение $\overset{R}\sim$ -эквивалентности, граф перекрытий минимизирован относительно этого отношения. Пространственная и временная сложности основной части работы алгоритма MinSufPref линейны по числу вершин и ребер минимизированного графа перекрытий. Временная сложность алгоритма не зависит от размера алфавита и длин слов в наборе. Проведены компьютерные эксперименты, которые показали высокую эффективность MinSufPref по сравнению с другими алгоритмами.