Оптимизация реконструкции с запретами в гипотезе сдвига 1

Ряд эндонуклеаз рестрикции может быть использован для индикации блоков ДНК, которые не существуют в условиях реального мира [18]. Таким образом, на этапе сборки генома можно отсечь существенное количество невозможных вариантов, уменьшив количество итераций алгоритма и сократив необходимые для его работы ресурсы (ОЗУ, дисковое пространство).

В отличие от простой реконструкции в гипотезе сдвига 1, описанной в предыдущей главе, реконструкция с запретами позволяет учитывать дополнительные ограничения на этапе непосредственно реконструкции. Такими ограничениями могут быть как данные генетической диагностики (например, невозможность в реальных условиях получить конкретный набор нуклеотидов в последовательности), так и более глобальные условия — заранее описанный набор исключений или «стоп-слов», появление которых в результирующей цепочки не устраивает авторов (например, последовательность генов, отвечающая за наследственное заболевание).

В рамках данной работы особый интерес для нас представляет поиск решений в частных случаях на основе редукции графа де Брейна, потому что рассмотренные в [42] тривиальные случаи, а также решение перечислением всех эйлеровых путей сводятся к проверке вхождений запрещенного слова или слов в множество слов реконструкции — иными словами, к фактически переборному решению из нескольких этапов, что в плане асимптотической трудоемкости незначительно отличается от оптимизационных решений с помощью генетической диагностики. В случае же с редукцией графа, результат может быть получен с меньшеи? трудоемкостью, чем через прямое решение задачи реконструкции без запретов. Обсудим этот подход более детально в системе обозначений [42].

Процедура редукции включает следующие два этапа (см. схему 4).

Поиск запрещенного слова в мультиорграфе де Брейна (I)

1. Строим упорядоченное мультимножество подслов длины k из запрещенного слова посредством оператора сдвига 1;

2. Полагаем и присваиваем кортежу t значение пусто;

• 3. Ищем в дугу, значение которой совпадает с i-ым сдвигом по запрещенному слову. Если такой дуги нет, то мы решаем задачу в постановке без запрещенных слов, иначе увеличиваем кортеж элементов.
• 4. Увеличиваем значение i i 1 и переходим к шагу 3 для всех i n k 1.
• 5. Путь по дугам, описываемый кортежем t, порождает запрещенное слово.

Редукция мультиорграфа

(II)

По мультиорграфу строим редуцированный мультиорграф.

сле дующим образом:

1. По всем элементам кортежа выполняем редукцию ребер;

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

Схема 4. Редукция мультиорграфа де Брёйна [42].