Институт математических проблем биологии РАН - филиал Института прикладной математики им. М.В. Келдыша РАН, Пущино, Россия

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

Ключевые слова: P-значение, вхождение образцов, перекрытие слов, автомат Ахо-Корасик, минимизация конечного автомата