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

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

Обоснование и актуальность темы

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

Расшифровка генома сводится к созданию полной записи ДНК, также представляемую в виде нескольких миллиардов нуклеотидов, объединенных в одну строку. Побочным результатом этого процесса можно считать создание так называемой «карты генома», описывающей расположение STS и EST, что позволит ускорить процесс расшифровки ДНК.

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

Использование реконструкции с запретами в гипотезе сдвига 1, а также генетической диагностики, в свою очередь, комбинирует два подхода к ускорению существующих алгоритмов восстановления ДНК практически без потери точности, исследование преимуществ и недостатков которых даёт возможность наиболее оптимально подбирать способы реконструкции, руководствуясь не только имеющимися средствами (место на жестком диске, время работы, ОЗУ), но и входными данными, что позволяет сделать вывод об актуальности выполненного исследования.

Цели и задачи работы

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

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

Предмет и методы исследования

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

Новизна и достоверность полученных результатов

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

Теоретическая значимость и практическая ценность

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

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

Структура работы

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