Восстановление кода дезоксирибонуклеиновой кислоты из библиотеки клонов sequence tagged site

YAC (yeast artificial chromosomes) -- рекомбинантные ДНК, созданные методами генетической инженерии [26].

Гамильтонов цикл -- цикл, который содержит все вершины графа [25].

ГБ -- гигабайт.

Генбанк (GenBank Публично доступная база размещена по адресу http://www.ncbi.nlm.nih.gov/genbank/ в сети Интернет.) -- база данных, в которой содержатся аннотированные последовательности ДНК и РНК [10].

Генетическая диагностика -- исследование генома, направленное на определение генетических склонностей к наследственным заболеваниям [9].

Граф де Брёйна -- графом де Брёйна для натуральных параметров и называется ориентированный граф, вершинам которого соответствуют все возможные -значные -ичные последовательности, а рёбра соединяют те и только те пары вершин, для которых последние цифр первого числа совпадают с первыми цифрами второго числа [37].

ДНК (дезоксирибонуклеиновая кислота) -- макромолекула, обеспечивающая хранение, передачу из поколения в поколение и реализацию генетической программы развития и функционирования живых организмов [28].

Задача о коммивояжёре -- задача о поиске наиболее выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город [29].

Интервальный граф -- граф пересечений мультимножества интервалов на прямой [30].

Контиг -- набор перекрывающихся фрагментов ДНК, которые в совокупности представляют собой консенсусную область ДНК [32].

Космидная строка -- Строка, содержащая участок начала репликации и позволяющая упаковывать молекулу ДНК в фаговую частицу [26].

Локус -- местоположение определённого гена на генетической или цитологической карте хромосомы [34].

Мультиорграф -- ориентированный граф, в котором разрешены кратные дуги, то есть дуги, имеющие те же начальные и конечные вершины [36].

ОЗУ -- оперативное запоминающее устройство.

Рестриктазы -- эндонуклеазы рестрикции [26].

РНК (рибонуклеиновая кислота) -- тип нуклеиновых кислот, имеющих универсальное распространение в живой природе [40].

Предмет исследования данной работы -- возможность восстановить код ДНК из STS-библиотеки клонов. Методы исследования включают в себя инструменты прикладной лингвистики, разработку программы для проведения тестирования, математическое моделирование, генетическую диагностику и работу с файлами Генбанка.

В последние годы был опубликован ряд исследований, посвященных проблеме восстановления кода ДНК [1, 2, 18]. К сожалению, большинство описанных идей строится на использовании физических меток [1] и не рассматривает алгоритмы реконструкции слов в достаточном масштабе. Идея реконструкции с запретами в гипотезе сдвига 1 ещё не нашла широкого распространения в промышленном производстве, и данные о её эффективности при использовании комбинированного подхода также отсутствуют, как и исследования об эффективности использования генетической диагностики в сочетании с другими способами оптимизации. Данная работа частично восполненяет этот пробел.

Теоретическая значимость исследования заключается в том, что после анализа алгоритмов реконструкции слов появится возможность выбирать оптимальные способы восстановления кода ДНК в зависимости от различных факторов (объем входных данных, ожидаемое время выполнения, необходимая точность и т.д.).

где

Генетическая диагностика, получившая распространение в первую очередь в медицинских заведениях, позволяет не только исследовать предрасположенности к наследственным заболеваниям (предимплантационная генетическая диагностика, [38]), но и максимально подробно сформулировать набор правил, по которым будут отсекаться или наоборот выбираться возможные варианты из множества, полученного после секвенирования.

В первую очередь данный подход основывается на использовании баз данных, содержащих аннотированные последовательности ДНК и РНК, а также последовательности закодированных в них белков. Это позволяет сэкономить часть ресурсов при реконструкции ДНК и воспользоваться уже доступной информацией о наиболее вероятных комбинациях нуклеотидов, а также отсеять шумы и погрешности реконструкции на основе STS-маркеров [26].

Более подробно об использовании генетической диагностики, которая сводится к алгоритмам над строками, пишут [4] и [13], но в рамках данной работы будет использоваться в первую очередь поиск множества подстрок в строке, а также перебор комбинаций на основе правил реконструкции.

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

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

Глава 2. Способы оптимизации алгоритмов реконструкции ДНК

Эта часть посвящена способам оптимизации алгоритмов реконструкции ДНК, которые были рассмотрены в предыдущей главе, в том числе и более детально рассмотрены методы генетической диагностики и реконструкции слов с запретами в гипотезе сдвига 1. Помимо описания самих подходов к оптимизации, в главе приведены необходимые теоретические сведения, а также рассмотрены способы оценки корректности полученных результатов.

2.1 Сжатие входных данных

Первая проблема, возникающая при программной реализации вышеописанных алгоритмов, как требующих хранения исходных значений для генетической диагностики, так и оперирующих матрицами смежности -- это проблема большого объема данных. В процесе реконструкции слов по мультимножеству подслов в гипотезе сдвига 1 необходимо как поддерживать регулярные операции удаления и добавления символов, так и обрабатывать значительное количество строк [41], что приводит к высокой загруженности как дискового пространства, так и оперативной памяти. Для оптимизации данного аспекта предлагается использовать так называемые карты рестриктаз, то есть строки, в которых каждый нечетный символ описывает расстояние между элементами, а каждый четный -- непосредственно элемент конечного алфавита, входящий в состав изначальной строки.

Например, для строкового представления ДНК вида TTTTTTTTTTTTTTTTTTTTTTTTTGGAAAAAAAAAAAAAAAAAAAAAAAAAAA может быть составлена карта 25T2G27A. В виду свойств ДНК, которые подробно рассмотрены в сторонних источниках [26, 27], подобная система сжатия позволяет сократить размер исходной строки на 60-75% [26]. Кроме того, подобное разбиение возможно на основе реальных биологических ферментов, относящихся к классу гидролиза, которые расщепляют нуклеиновые кислоты не с конца молекулы, а в середине и таким образом "узнают" участки ДНК.

2.2 Группировка

Еще одна проблема, связанная с обоими методами секвенирования, заключается в высокой стоимости выполнения тестов для каждой пары STS и клонов. Вместо этого предлагается группировать клонов в блоки и тестировать STS на перекрытие с каждым блоком по отдельности [26] -- этого достаточно, чтобы понял, присутствует ли данный STS хотя бы в одном из объектов блока. Соответственно, для группировки можно или один раз случайным образом отобрать клонов, или после каждого теста перестраивать блоки для улучшения полученных ранее результатов, что даёт простор для применения генетических алгоритмов и элементов машинного обучения.

2.3 Интервальный граф

В базовой реализации алгоритма один из этапов включает в себя поиск перестановок, которые приводят к образованию строк из нескольких идущих подряд единиц (см. Рис. 3). В изначальной версии используется алгоритм , предложенный Бутом и Люкером [26] и работающий за . Эту задачу можно решить за меньшее число операций, используя лексикографический поиск в ширину и тот факт, что интервальным может быть только хордальный граф [33].

Алгоритм выглядит следующим образом (см. схему 2).

2.4 Эвристическое ускорение

Аналогично с п. 2.3, Shotgun включает в себя сборку последовательностей, на этапе которой производится поиск наилучшего суффиксно-префиксного совпадения. Асимптотическая сложность этого алгоритма , то есть при поиске для всех фрагментов получается , что и занимает почти всё время работы программы.

Чтобы избежать данной проблемы, предлагается на первом этапе распознавать те пары строк, которые не имеют достаточного сходства и гарантированно не могут использоваться как части итоговой ДНК. В данном случае эвристическое ускорение позволяет оптимизировать время работы программы путем отсечения лишних данных до обработки [26].

Аналогично, эвристические методы позволяют улучшить алгоритм поиска гамильтонового цикла с помощью алгоритма Кристофидеса [26]: пусть на входе мы имеем матрицу расстояний для графа . Тогда алгоритм будет состоять из следующих шагов (см. схему 3):

1. Найти минимальное остовное дерево с матрицей весов ;

2. Выделить множество всех вершин нечетной степени в и найти кратчайшее совершенное паросочетание в полном графе с множеством вершин ;

3. Построить эйлеров граф с множеством вершин и множеством ребер ;

4. Найти эйлеров путь в ;

5. Пользуясь последовательным исключением посещенных вершин, построить гамильтонов цикл из .

Схема 3. Алгоритм Кристофидеса [26].

2.5 Оптимизация реконструкции с запретами в гипотезе сдвига 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].

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

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

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

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

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

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

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

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

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

--

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

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

,

где -- сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам. Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут быть найдены при помощи ленивой рекурсии.

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

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

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

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

Несмотря на довольно большой спектр доступных для использования идей оптимизации, особый интерес представляет исследование наиболее эффективной комбинации выше предложенных способов. Соответственно, необходимо выбрать некую метрику, на основе которой будет проведено сравнение. В рамках данной исследовательской работы мы остановились на сочетании расстояния Левенштейна, отображающего "минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую" [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). После тестирования, проведенного на более чем 100000 парах геномов с различными размерами, значения сравнили с ANIb, который считается стандартным. OrthoANIb и OrthoANIu показали хорошую корреляцию во всем диапазоне значений ANI, ANIm показал низкую корреляцию для ANI <90%. ANIm и OrthoANIu работают на порядок быстрее, чем ANIb. Когда были проанализированы геномы размером более 7 Мбит, время работы ANIm и OrthoANIu было короче, чем у ANIb на 53 и 22 раза, соответственно [22]. Таким образом, в рамках данной работы было решено остановиться на OrthoANIu, так как этот алгоритм позволяет значительно ускорить получение результатов без потери точности.

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

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

Глава 3. Экспериментальный раздел

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

3.1 Гипотеза

На основе работ [4, 12, 17, 42] можно сделать вывод о том, что теоретический предел для реконструкции ДНК на основе генетической диагностики и реконструкции слов с запретами в гипотезе сдвига 1 ещё не достигнут. Утверждается, что использование вышеописанных способов оптимизации способно значительно уменьшить временные затраты без существенного (отклонение < 3% ANI) ухудшения качества.

3.2 Протокол тестирования

Для исследования полученных алгоритмов была написана программа на языке Python 2.7 (код программы изложен в Приложении 1), позволяющая генерировать библиотеки клонов на основе заданных ДНК (явно или посредством файлов Генбанка) и реконструировать их различными методами.

Список элементов программы выглядит следующим образом:

· Базовая реализация метода дробного секвенирования;

· Базовая реализация метода восстановления гибридизацией;

· Оптимизированная реализация метода дробного секвенирования с использованием генетической диагностики;

· Оптимизированная реализация метода восстановления гибридизацией с использованием реконструкции слов с запретами в гипотезе сдвига 1;

· Оптимизированная реализация метода восстановления гибридизацией с использованием и генетической диагностики, и реконструкции слов с запретами в гипотезе сдвига 1;

· Парсер файлов Генбанка;

· Модуль вычисления расстояния Левенштейна;

· Модуль вычисления ANI;

· Тестер, собирающий результаты работы алгоритмов.

В целях изучения возможности оптимизации каждого из алгоритмов был проведен ряд тестов:

· Библиотека клонов была сгенерирована один раз на основе файлов Генбанка.

· В изолированной от внешних процессов среде каждый из алгоритмов запускался отдельно;

· Воспроизводился процесс реконструкции ДНК, описанный в Главе 1;

· Замерялось процессорное время от момент прочтения первого элемента библиотеки клонов до закрытия записи в файл с результатами;

· Полученная последовательность или последовательности сохранялись отдельно;

· На основе всех последовательностей производилось сравнение расстояния Левенштейна и ANI с изначальными файлами нуклеотидных последовательностей Генбанка;

· Генерировались графики с результатами работы по времени и точности полученного результата;

· Список алгоритмов ранжировался в соответствии с ANI, временем работы и расстоянием Левенштейна.

Тестирование проводилось на ноутбуке Macbook Air "13 (4 ГБ ОЗУ, 128 ГБ SSD, Core i5 Dual-core 1.4 GHz).

3.3 Исходные данные

Тестирование проводилось на нуклеотидных последовательностях, представленных Генбанком. Для чистоты эксперименты был написан генератор псеводслучайных последовательностей, результаты работы которого использовались для выбора образцов секвенированного генома по совпадению подстрок. В дальнейшем из выборки удалялись элементы с длиной последовательности меньше 30 000 элементов (не представляют достаточно значимых для сравнительного тестирования данных) и больше 5 000 000 элементов (приблизительные ограничения жесткого диска), а удовлетворяющие условиям последовательности были отсортированы по возрастанию количества символов. Список всех нуклеотидных последовательностей, задействованных в тестировании, представлен в Приложении 2.

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

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

Глава 4. Анализ результатов

В данной главе исследуемые способы оптимизации сравниваются на основе расстояния Левенштейна по отношению к исходными строками, а также по показателям производительности в соответствии с протоколом тестирования. Заключительное решение о ранжировании способов оптимизации принимается на основе анализа средней нуклеотидной идентичности.

4.1 Расстояние Левенштейна

Самой тривиальной метрикой в случае данного тестирования было расстояние Левенштейна. Как уже отмечалось выше, с его помощью не всегда можно получить информацию о реальном отличии или сходстве строк, но, так как в нашем случае речь идёт о сравнительном анализе, данным параметром было решено не пренебрегать.

Рассмотрим результаты тестирования на точность по расстоянию Левенштейна (на графиках показано, насколько отличается среднее значение расстояния Левенштейна для реконструированного объекта -- иными словами, процент числа правок, которые нужно внести в новый объект чтобы получить исходный, от его длины):

Исследовались все вышеупомянутые алгоритмы, как неоптимизированные, так и с оптимизацией без комбинирования методов. Для базовых реализаций результаты тестирования незначительно отличаются от описанных в [15, 26]:

Рисунок 6. Точность базовой реализации метода восстановления гибридизацией на основе расстояния Левенштейна.

Рисунок 7. Точность базовой реализации метода дробного секвенирования на основе расстояния Левенштейна.

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

Рисунок 8. Точность оптимизированной реализации метода восстановления гибридизацией с использованием реконструкции слов по мультимножеству подслов в гипотезе сдвига 1 на основе расстояния Левенштейна.

Рисунок 9. Точность оптимизированной реализации метода дробного секвенирования с использованием генетической диагностики на основе расстояния Левенштейна.

Как можно заметить, чем выше число нуклеотидов в результирующем геноме, тем качественнее, если брать за основу данную метрику, оказывается результат тестирования. Посмотрим на результат прохождения тестов наиболее комплексным алгоритмом, использующим и технологию реконструкции ДНК с помощью восстановления слов по мультимножеству подслов с запретами в гипотезе сдвига 1, но и генетическую диагностику:

Рисунок 10. Точность оптимизированной реализации метода восстановления гибридизацией с использованием и генетической диагностики, и реконструкции слов с запретами в гипотезе сдвига 1 на основе расстояния Левенштейна.

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

4.2 Сравнение производительности

Теперь давайте рассмотрим производительность каждого из методов. Ниже представлен график роста среднего времени (мс), которое необходимо алгоритму для восстановления 10 000 символов (с ростом длины последовательности).

Рисунок 11. Сравнение производительности алгоритмов реконструкции ДНК.

Заметим, что наиболее устойчивыми к увеличению объемов входных данных оказались методы с использованием генетической диагностики. Как косвенно упоминают в своих работах [12] и [26], причиной тому может быть наличие большего объема данных для генерации копий, на основе которых и производится поиск по базам на предмет совпадений и исключений.

4.3 Анализ средней нуклеотидной идентичности

Перейдем к заключительной части анализа -- средней нуклеотидной идентичности. Весьма показательны графики того, насколько отличается процент числа правок, которые нужно внести в новый объект чтобы получить исходный, от его длины.

Рисунок 12. Точность базовой реализации метода восстановления гибридизацией на основе ANI.

Рисунок 13. Точность базовой реализации метода дробного секвенирования на основе ANI.

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

Рисунок 14. Точность оптимизированной реализации метода восстановления гибридизацией с использованием реконструкции слов с запретами в гипотезе сдвига 1 (ANI)

Рисунок 15. Точность оптимизированной реализации метода дробного секвенирования с использованием генетической диагностики (ANI)

Рисунок 16. Точность оптимизированной реализации метода восстановления гибридизацией с использованием реконструкции слов с запретами в гипотезе сдвига 1.

Также подтверждается гипотеза о том, что средняя нуклеотидная идентичность дает куда более точное представление о корректности реконструкции, нежели метрика по расстоянию Левенштейна. Можно заметить, что в ситуациях, когда значение расстояния Левенштейна было незначительным, нуклеотидные последовательности могли кардинально различаться. реконструкция слово генетический диагностика

Рисунок 17. Точность оптимизированной реализации метода восстановления гибридизацией с использованием и генетической диагностики, и реконструкции слов с запретами в гипотезе сдвига 1.

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

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

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

Заключение

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

Полученные результаты

В рамках выполнения выпускной квалификационной работы было проведено исследование способов оптимизации алгоритмов реконструкции ДНК на основе генетической диагностики и реконструкции слов с запретами в гипотезе сдвига 1. Для тестирование гипотезы, выдвинутой в процессе проведения исследования, была разработана вспомогательная программа, позволяющая секвенировать, разрезать и восстанавливать последовательности нуклеотидов из базы Генбанка, а также замерять производительность и точность процесса реконструкции. Кроме того, тривиальные реализации алгоритмов [26] были дополненны предложенными улучшениями (эвристики, сжатие данных, STS-карты) и только после этого проверялись на тестах. Был сделан вывод об эффективности предложенного способа оптимизации в сравнении с работами [1, 42].

Поставленные и выполненные задачи

· предложить методы измерения погрешности в работе алгоритмов (были выбраны ANI и расстояние Левенштейна);

· исследовать возможности оптимизации алгоритмов;

· предложить способы оптимизации и исследовать ожидаемое изменение производительности каждого из алгоритмов в зависимости от оптимизации (был предложен ряд способов оптимизации, ожидаемое изменение было исследовано на основе асимптотической оценки алгоритмов)

· провести тестирование на файлах Генбанка и сделать выводы о возможностях оптимизированной реконструкции кода ДНК (возможность оптимизированной реконструкции подтвердилась)

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

Направления дальнейшей работы