Laboratory of Mathematical Logic at PDMI

Пятница, 12 октября, ауд. 106. Начало в 14:00.

Докладчик: Александр Куликов (ПОМИ РАН).

Тема: Жадная гипотеза для задачи о надстроке.

Abstract

Задача о (кратчайшей общей) надстроке — классическая труднорешаемая задача, являющаяся, в частности, математической моделью задачи сборки генома. В ней на вход даётся множество строк и требуется найти самую короткую строку, содержащую их все как подстроки. На сегодняшний день мы не знаем эффективных точных алгоритмов для её решения. Наилучший известный приближённый алгоритм для этой задачи находит решение, которое гарантированно не более чем в 2,5 раза длиннее оптимальной надстроки. Соответствующий алгоритм и его анализ довольно сложны. В то же время уже более тридцати лет остаётся открытой так называемая жадная гипотеза. Она утверждает, что следующий (до безобразия простой) жадный алгоритм является 2-приближённым: пока строк больше двух, взять две из них с максимальным наложением и заменить на их склейку (в итоге останется одно строка, которая обязательно будет надстрокой исходного набора).

Пытаясь доказать эту гипотезу, мы пришли к понятию иерархического графа, который в некотором смысле является обобщением графов де Брюйна (которые, с свою очередь, активно используются в современных геномных ассемблерах). В этом графе тоже легко строится жадный алгоритм, который обладает некоторыми замечательными свойствами. Например, в отличие от обычного жадного алгоритма он находит оптимальные решения для некоторых полиномиально разрешимых частных случаев. Для данного жадного алгоритмы мы экспериментально установили, что всегда выполняется достаточно сильное условие, из которого, в частности, следует 2-приближение. Доказывать это сильное условие мы на сегодняшний день умеем только в случае, когда все исходные строки имеют длину три.

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

Доклад по совместной работе с Александром Головнёвым, Александром Логуновым и Иваном Михайлиным:
https://arxiv.org/abs/1809.08669
Веб-сервис с пошаговой визуализацией всех алгоритмов из статьи: https://compsciclub.ru/scs
(используя его, можно проверить сформулированные гипотезы на произвольном датасете).