МОЛЕКУЛЯРНАЯ БИОЛОГИЯ, 2015, том 49, № 3, с. 372-383
= МОЛЕКУЛЯРНАЯ ФИЛОГЕНЕТИКА
УДК 575.852
ПЕРЕСТРОЙКА И РЕКОНСТРУКЦИЯ ХРОМОСОМНЫХ СТРУКТУР
© 2015 г. К. Ю. Горбунов, Р. А. Гершгорин, В. А. Любецкий*
Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, Москва 127051
Поступила в редакцию 17.12.2014 г.
Принята к печати 24.12.2014 г.
Под хромосомной структурой понимают набор хромосом, состоящих из генов с указанием их принадлежности одной из цепей ДНК, а также циклический или линейный порядок в хромосоме. Широко исследуемая задача — определение кратчайшей последовательности операций по перестройке хромосом, которая переводит одну структуру в другую. В случае одинаковых цен всех операций и постоянного состава генов решение задачи известно. В нашей работе представлен принципиально новый метод, который позволяет решить как эту задачу, так и ряд ее обобщений. А именно, для постоянного набора генов создан новый точный алгоритм решения задачи для равных и неравных цен, который имеет линейную вычислительную сложность. Также получены как точный, так и эвристический алгоритмы решения новой задачи: реконструкции на внутренние вершины дерева видов хромосомных структур с разными наборами генов, когда исходные структуры заданы только в листьях.
Ключевые слова: хромосомная структура, хромосомная перестройка, точный алгоритм, линейная сложность алгоритма, предковая структура, дерево видов, эволюция вдоль дерева, принцип парсимонии.
REARRANGEMENT AND INFERENCE OF CHROMOSOME STRUCTURES, by K. Yu. Gorbunov, R. A. Gershgorin, V. A. Lyubetsky* (Kharkevich Institute for Information Transmission Problems, Russian Academy of Science, Moscow, 127051 Russia; *e-mail: lyubetsk@iitp.ru). A chromosome structure is defined as a set of chromosomes with genes assigned to one of the DNA strands and having a cyclic or linear arrangement. A well-known problem is to infer the shortest path of chromosome rearrangements connecting a pair of structures. In cases with equal rearrangement costs the solution was known; our solution is based on a principally novel approach. The study presents an original exact solving algorithm with linear complexity for both equal and unequal costs. We consider the case of structures consisting of the same set of genes. The study also presents the exact and heuristic algorithms to solve another problem, the inference of ancestral chromosome structures given fixed structures in leaves.
Keywords: chromosome structure, chromosome rearrangement, effective algorithm, ancestral structure, species tree, evolution along a species tree, parsimony.
DOI: 10.7868/S0026898415030076
Ранее в работах [1—3] и в других публикациях рассматривали задачи оценки числа хромосомных перестроек в разных частях геномов у разных видов, определения участков наиболее и наименее подверженных перестройкам, оценки частот перестроек на разных этапах эволюции, выявления этапов их резкого возрастания и т.д. Их решали, в основном, на основе выделения и сравнения участков синтении. Этот метод дает приближенные решения упомянутых задач, позволяет описать наиболее крупные события, связанные с перестройками, приближенно восстановить структуру предковых геномов. Однако он не позволяет строить сценарии эволюции хромосомных перестроек вдоль всего дерева видов. Разработка эф-
* Эл. почта: lyubetsk@iitp.ru
фективных алгоритмов вычисления расстояния между хромосомными структурами и на этой основе построение полного сценария хромосомных перестроек в геномах видов - актуальные задачи. Первая из них состоит в определении кратчайшей последовательности операций, переводящей одну хромосомную структуру в другую. Вторая из них позволяет находить наиболее вероятные сценарии хромосомных перестроек, оценивать эволюционную близость видов, выявлять перестройки, связанные с мобильными элементами и характерными белками.
При одинаковых ценах операций и постоянном наборе генов задача решена в работе [4], см. также последующие книги [5, 6]. В работах [1-6] приведены ссылки по истории вопроса вместе с подробными биологическими мотивировками
перестройка и реконструкция хромосомных структур
373
Структура a
Структура b
1 a
'1 a
1
Рис. 1. Две хромосомные структуры а и Ь из п = 11 генов каждая (слева) и их общий граф а + Ь (справа).
задач. Отметим большой цикл работ П. Певзнера и его школы, в котором получены алгоритмы хромосомных перестроек с помощью операций инверсии и, частично, трансверсии и транслокации, см. обзорную главу 4 в работе [6]. Насколько авторы могут судить, в этой главе точные полиномиальные алгоритмы обсуждали только для хромосомной структуры, состоящей из одной линейной цепи без паралогов, а операция состоит в инверсии участка цепи. Это — специальный случай двойной переклейки, одной из операций в более широком списке, рассматриваемом ниже.
В данной работе предложен новый точный и линейный по вычислительной сложности алгоритм решения этой задачи, который основан на методе, принципиально отличном от методов, использованных в работах [4—6]. Затем представлен эвристический алгоритм решения более общей задачи: определения кратчайшей последовательности операций по перестройке хромосом при неравных ценах операций, когда минимизируется суммарная цена последовательности. При некоторых ограничениях она может быть решена также и точным линейным алгоритмом, который, однако, представлен в журнал "Проблемы передачи информации", так как его изложение требует специальных математических средств.
"Точный" алгоритм сопровождается доказательством того, что он всегда выдает (глобальный) минимум соответствующей цены или иного функционала, указанного в постановке задачи.
Затем нами предложен как кубический точный, так и эвристический алгоритмы решения новой задачи: реконструкции на внутренние вершины дерева видов хромосомных структур с разными наборами генов, структуры заданы в листьях. Эти два алгоритма относятся к разным определениям расстояния между парами структур, приписанных концам ребер в дереве видов. Для одного расстояния доказывается точность алгоритма, для второго нет, но, по-видимому, оно
более содержательное с эволюционной точки зрения.
Все алгоритмы компьютерно реализованы, примеры применения соответствующих компьютерных программ приведены ниже и подробнее на сайте http://lab6.iitp.ru/ru/pr_chromo/: две программы chromo и chrom_reconstruction. Программирование, счет, подготовка и анализ данных выполнены Р. Гершгориным. Понятия и результаты, приведенные в разделе "Алгоритм решения задачи и его обоснование" и в пунктах "Специальное расстояние" и "Случай разных цен операций" получены двумя другими авторами.
Данная статья - расширенный вариант двух пленарных докладов авторов на конференциях [7, 8].
ПОСТАНОВКА ЗАДАЧИ О КРАТЧАЙШЕЙ ПОСЛЕДОВАТЕЛЬНОСТИ ХРОМОСОМНЫХ ПЕРЕСТРОЕК
Хромосомная структура — набор линейных и циклических хромосом, каждый ген в хромосоме задан началом и концом; длина гена, нуклеотид-ный состав и межгенные участки хромосомы не учтены. В этой модели гены в хромосоме считают расположенными "линейно" в виде цепи или цикла и примыкающими друг к другу. С учетом двух цепей для примыкающих генов возможны варианты: конец одного гена совпадает с началом другого или того же гена, конец — с концом другого гена, начало — с началом другого гена. Хромосомную структуру удобно рассматривать как граф, состоящий из компонент, каждая из которых изображает хромосому. Ребрам приписаны имена (номера) генов — числа от 1 до n без повторений. Таким образом, ген представлен только своим именем (номером). На рис. 1 слева приведен пример двух хромосомных структур а и b. В вершине, соединяющей два гена, отождествлены начала и/или концы этих генов (в соответствии со стрелками); крайней вершине цепи приписаны начало или конец гена. Пометка i, означает нача-
1. Двойная переклейка
Рис. 2. Операции над хромосомной структурой. Крестик указывает на разрез (расклейку двух склеенных вершин), двойная стрелка — на результат операции. Эти операции предложены в работе [4].
ло гена с номером i (при} = 1) или его конец (при } = 2); петля в некоторой вершине означает ген, у которого начало совпадает с концом, например ген 11 в структуре a, показанной на рис. 1 слева.
Пусть далее фиксированы две структуры а и Ь с одинаковым числом п генов; например, показанные на рис. 1 слева, где п = 11.
Знак ~ указывает на отождествление начал и концов ("краев") генов, соответствующее их соседству на хромосоме; например, для цикла на рис. 1 слева имеем 52 ~ 61, 42 ~ 51, 31 ~ 41, 22 ~ 32,
12 ~ 2ъ 11 ~ 62.
Новый метод, на котором основан наш подход, состоит в использовании двух понятий: общего графа и его качества, которые обладают нетривиальными свойствами. А именно, общим графом структур а и Ь назовем граф, в котором вершины - это края ^ всех генов из а (они же из Ь), и ребра соединяют две вершины, если они отождествлены в а или в Ь. Каждое ребро отмечаем именем структуры, в которой произошло отождествление краев генов, т.е. именами структур а или Ь. В графе ребра могут быть параллельными: одно ребро из а, другое — из Ь (циклы длины 2). Общий граф (обозначим его а + Ь) легко описать: это чередующиеся (а, Ь)-цепи и (а, Ь)-циклы, рис. 1 справа. Итак, общий граф а + Ь показывает, какие края генов отождествлены в структурах а и Ь. Вместо отождествления часто говорят о склейке соответствующих краев г}.
Длина цепи (или цикла) - число ребер в ней (в нем), изолированные вершины считаем цепями длины 0 (будем считать нуль четным числом). Качество общего графа - число циклов, сложенное с половиной числа четных цепей в нем (четная
цепь содержит четное число ребер, цепи нечетной длины не учитывают).
Исходную задачу можно сформулировать в терминах самих структур а и Ь или в терминах их общего графа а + Ь. Начнем с первой формулировки. Для двух структур а и Ь найти последовательность операций, минимальную по их числу, которая переводит одну из них в другую, например, структуру а в структуру Ь, рис. 1 слева. Саму последовательность назовем минимальной, ее длину — минима
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.