Оптимизация генетической диагностики

Для ускорения сборки можно пользоваться побочной информацией, доступной в открытых источниках — например, информацией о наиболее популярных парах перекрывающихся фрагментов и/или данными о физическом расстоянии между блоками [21]. В файлах Генбанка содержится информация о допустимых и недопустимых последовательностях контингов.

Для работы с базами генетической диагностики, в свою очередь, применяются соответствующие алгоритмы работы со строками. Так, например, можно сократить и объем входных данных, и асимптотическую сложность итогового алгоритма, воспользовавшись структурой данных под названием бор и построив по ней конечный детерминированный аппарат — иными словами, реализовав алгоритм Ахо-Корасик для поиска всех вхождений всех строк-образцов в заданную строку (см. схему 5):

1. Построить бор из строк.

a. Построение выполняется за, где — суммарная длина строк;

2. Преобразовать бор.

a. Обозначим за слово, приводящее в вершину u в боре. Узлы бора можно понимать как состояния автомата, а корень как начальное состояние. Узлы бора, в которых заканчиваются строки, становятся терминальными. Для переходов по автомату заведём в узлах несколько функций:

i. — возвращает родителя вершины u;

ii. — суффиксная ссылка, и существует переход из parent (u) в u по символу c;

-;

функция перехода.

3. Построить сжатые суффиксные ссылки

.

4. Использовать автомат

a. По очереди просматриваем символы текста. Для очередного символа с переходим из текущего состояния u в состояние, которое вернёт функция. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам строки, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему строки тоже отмечаем.

5. Оценить результаты