Оценка полученных результатов

Несмотря на довольно большой спектр доступных для использования идей оптимизации, особый интерес представляет исследование наиболее эффективной комбинации выше предложенных способов. Соответственно, необходимо выбрать некую метрику, на основе которой будет проведено сравнение. В рамках данной исследовательской работы мы остановились на сочетании расстояния Левенштейна, отображающего «минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую» [39], а также среднего анализа идентичности нуклеотидов [3]. Благодаря этому удалось решить проблему с некорректным отображением точности в ситуациях, когда исходная строка при посимвольном сравнении незначительно отличалась от результата секвенирования, но после деления на нуклеотиды и их сортировки подтверждала некорректность всего процесса восстановления.

Рассмотрим предложенные метрики подробнее. В основу расстояния Левенштейна положена идея динамического программирования по префиксу. Будем хранить матрицу, где — расстояние Дамерау-Левенштейна между префиксами строк и, длины префиксов — и соответственно. Для учёта транспозиции потребуется хранение следующей информации. Инвариант: — индекс последнего вхождения в, last — наой итерации внешнего цикла индекс последнего символа.

.

Тогда если на очередной итерации внутреннего цикла положить.

то.

.

Где.

Расстояние Левенштейна широко применяется для сравнения генов, хромосом и белков [20], но обладает двумя существенными для рассматриваемой задачи минусами: при перестановке местами слов или частей слов расстояния значительно увеличиваются, а также из-за отсутствия учёта длины итогового слова нередки ситуации с небольшим редакционным расстоянием между двумя совершенно разными короткими словами или с большим редакционным расстоянием между двумя очень похожими длинными словами. Не смотря на минусы, в данной работе всё равно учитывается расстояние Левенштейна, потому что в большинстве случаев прослеживается прямая зависимость между его значением и точностью реконструкции [31].

Для повышения точности итоговой оценки результатов исследования было принято решение дополнительно проверять полученные строки на среднюю нуклеотидную идентичность (ANI). Иными словами, попарно сопоставить фрагменты исходного и полученного ДНК, полученные в результате разрезания строки по эндонуклеазам рестрикции. Такой подход не только позволяет ввести метрику, более устойчивую к перегруппировке генома [19], но и принять во внимание возможность горизонтальной транспортировки генов [22]. В данной работе за основу принимается утверждение, что при ANI равном 95% или выше, тестируемые строки относятся к одному и тому же виду и были восстановлены корректно ]22].

Вычисление ANI обычно включает фрагментацию последовательностей генома с последующим поиском, выравниванием и определением нуклеотидной последовательности. Исходный алгоритм вычисления ANI использовал в качестве поисковой системы программу BLAST, но за последние несколько лет были предложены ряд улучшений, в том числе ANIb (алгоритм ANI с использованием BLAST), ANIm (ANI с использованием MUMmer), OrthoANIb (OrthoANI с использованием BLAST) и OrthoANIu (OrthoANI с использованием USEARCH). После тестирования, проведенного на более чем 100 000 парах геномов с различными размерами, значения сравнили с ANIb, который считается стандартным. OrthoANIb и OrthoANIu показали хорошую корреляцию во всем диапазоне значений ANI, ANIm показал низкую корреляцию для ANI <90%. ANIm и OrthoANIu работают на порядок быстрее, чем ANIb. Когда были проанализированы геномы размером более 7 Мбит, время работы ANIm и OrthoANIu было короче, чем у ANIb на 53 и 22 раза, соответственно [22]. Таким образом, в рамках данной работы было решено остановиться на OrthoANIu, так как этот алгоритм позволяет значительно ускорить получение результатов без потери точности.

Выводы по главе 2

В данной главе были предложены способы оптимизации алгоритмов реконструкции ДНК, высказаны предположения об их влиянии на итоговый результат, а также рассмотрены подходы для измерения эффективности и риски их использования.