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

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

Процесс физического картирования можно разбить на несколько частей. Первым этапом выбираются маркеры STS или уже известные гены в коде ДНК — своего рода «ориентиры» для алгоритма. Затем на основе каких-либо физических параметров определяются метрики (например, число нуклеотидов между двумя маркерами). Полученные данные кодируются в предпочитаемый формат и дальнейшей взаимодействие уже ведется с полученным набором слов над алфавитом {A, T, G, C}.

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

Рассмотрим STS-картирование. В данном случае исследование строится на коротких подстроках ДНК, встречающихся только в определенных местах всего генома — STS. Это свойство даёт возможность построить «библиотеку клонов», набор маркеров, о которых известно в каких случаях они перекрываются (впрочем, порядок и изначальное положение могут быть недоступны). В рамках данной работы мы будем рассматривать только упорядоченные библиотеки клонов, так как для каждого блока в них известно физическое расположение STS-маркеров относительно оригинального ДНК.

Иными словами, процесс создания STS-карты, о котором шла речь выше — это упорядочивания STS с одновременным созданием физической карты для упорядоченной библиотеки клонов.

Рисунок 2. Данные для клонов, представленные в виде матрицы (см. Рис. 1). Так как правильный порядок STS неизвестен, они размещены случайным образом.

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

Рисунок 3. Когда данные об STS не содержат ошибок, можно переставить столбцы в матрице так, чтобы единицы шли подряд.

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

Второй подход, радиационно-гибридное картирование, более популярен для работы с библиотеками клонов более крупного размера. Отчасти он сводится к решению задачи о коммовояжёре. Сам же метод изначально основывался на процессе облучения отдельной хромосомы из генома человека, которая разбивалась на некоторое число фрагментов и внедрялась в клетку какого-либо грызуна. В результате этого, на протяжении нескольких поколений каждая клетка грызуна всё реже и реже воспроизводит изначальную человеческую ДНК, но при этом создает новые, гибридные клетки, оставляя от человеческой хромосомы не больше 20%. Данный процесс неоднократно повторяется в случайном порядке с разными экземплярами одной и той же хромосомы и позволяет понять, какие из изначальных неупорядоченных STS содержатся в тех или иных «человеческих» фрагментах каждой из клеток (см. Рис. 4). Соответственно, кардинальное отличие такого подхода от простого STS-картирования в невозможности определить непосредственно фрагмент с маркером на основе полученных данных.

.

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

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

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

Рисунок 5. Схема гипотетической крупномашстабной расшифровки. Рисунок не передает масштаба.

Вышеописанная методика является одним из стандартных подходов к обработке нуклеотидных последовательностей и широко используется в исследовательской сфере [7, 14]. К сожалению, с ростом длины последовательности увеличиваются не только требования к техническим устройствам, на которых происходит обработка данных и расшифровка, но и непосредственно время, необходимое для разбора всех возможных случаев, поэтому на протяжение уже нескольких десятилетий ведется непрерывная работа над улучшением и оптимизацией вышеупомянутых этапов.

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