A MODIFIED ALGORITHM FOR TRANSFORMATION OF CHROMOSOMAL

STRUCTURES: A CONDITION OF ABSOLUTE EXACTNESS In the article the modification of an algorithm for transformation of one chromosomal structure into another one is presented. The algorithm was developed by the authors earlier; for its modification a sufficient condition of absolute exactness has been proved.

Chromosomal structure; chromosomal rearrangement; linear algorithm; exact algorithm; parsimony principle; operation cost; combinatorial optimization. Определения и постановка задачи структуру b последовательностью операции минимальнои суммарнои цены. Искомую последовательность называем кратчайшей.

Для двух структур a и b полезно введённое нами понятие общего графа a+b; для удобства читателя определим его сначала для равных составов, а затем для общего случая. Это – неориентированныи граф без петель, вершины которого – имена краёв всех генов; например, начало гена 3 обозначается 31, конец – 32. Ребро общего графа соединяет две вершины, если соответствующие им края отождествлены (вместо этого говорят: склеены) в а или в b; оно помечается соответственно как a- или b-ребро. Если они склеены в обеих структурах, то соединяются двумя рёбрами, одно помечено a и другое b. Например, общий граф структур, показанных слева на рис. 1 в [ 1 ], показан справа на том же рисунке. Таким образом, общии граф a+b несёт информацию о склеиках вершин как в a, так и в b. Легко видеть, что a+b всегда состоит из цепеи и циклов (в том числе, изолированных вершин и циклов длины 2), в которых a-рёбра и bрёбра чередуются. Эти цепи и циклы будем называть компонентами.

Граф c+c состоит из циклов длины 2 и изолированных вершин. Граф такого вида назовём финальным (или: финального вида). Легко видеть, что наша задача эквивалентна задаче приведения графа a+b к финальному виду следующими операциями над общим графом, которые иллюстрируются в первом дополнительном материале к [ 2 ].

Двойная переклейка: удаление двух одинаково помеченных рёбер и соединение четырёх образовавшихся концов двумя новыми неинцидентными рёбрами с той же пометкой.

Полуторная переклейка: удаление ребра и соединение одного из его концов ребром с той же пометкой с вершиной, не инцидентной ребру с этой пометкой.

Разрез: удаление любого ребра.

Склейка: добавление ребра (скажем, с пометкой a) между вершинами, каждая из которых не инцидентна ребру с пометкой a.

Эти четыре операции назовём стандартными.

Рассмотрим случаи неравного генного состава, т.е. множества имён генов в структурах a и b могут не совпадать (но имена в структуре не повторяются). Ген, которыи представлен в a и в b назовём общим; ген, представленныи лишь в однои из структур – особым: соответственно, имеются a- и b-особые гены.

В случае неравного состава, кроме четырёх указанных операции разрешаются ещё две дополнительные операции над хромосомои – удаление и вставка, их рисунки приведены в первом дополнительном материале к [ 2 ]. Удаление: удалить из хромосомы связныи отрезок из a-особых генов. Отрезок может удаляться из кольцевои или линеинои хромосомы, а также, если он сам – хромосома. Если у удаляемого отрезка имеются два соседних гена, их края склеиваются между собои. Вставка: вставить в хромосому связныи отрезок из b-особых генов. Отрезок может вставляться в любую хромосому, а также – в виде новои линеинои или кольцевои хромосомы.

В случае неравного состава определение общего графа a+b изменяется следующим образом. Он содержит обычные вершины – края общих генов вида k1 и k2, и особые вершины – максимальные по включению связные участки из a-особых или из b-особых генов. Последние будем называть блоками. Блок принадлежит однои из структур, и соответствующая ему особая вершина помечается как a- или b-вершина, еи также приписывается множество (точнее, последовательность) генов, составляющих блок. Общии граф содержит следующие рёбра. Обычное ребро соединяет две обычные вершины, если соответствующие им края отождествлены (склеены) в а или в b; особое ребро соединяет обычную вершину с особой, если в а или в b край, соответствующий обычной вершине, отождествлён (склеен) с краем блока, соответствующего особой вершине. Такое ребро помечается как a- или b-ребро. Здесь также возможны двоиные обычные рёбра. Петля в a+b соответствует циклу, которыи является блоком; иными словами, особая вершина этого блока соединяется с собои. Висячим называется особое ребро, инцидентное особои вершине степени 1.

Как и прежде, общии граф неориентированныи и состоит из связных компонент – цепеи и циклов. Невисячие особые рёбра присутствуют в нём парами – рёбра, инцидентные однои особои вершине; такую пару удобно считать за одно двоиное ребро; с этои оговоркои сохраняется чередование a- и b-рёбер. Поэтому размером компоненты назовём сумму в неи числа обычных рёбер с половинои числа особых невисячих рёбер. Для изолированных обычных вершин и петель считаем размер равным 0, для изолированных особых вершин (не петель) – равным "минус 1". Общии граф называется финальным (финального вида), если каждая его компонента – изолированная обычная вершина или цикл без особых рёбер размера (в данном случае, то же самое – длины) 2, одно ребро из а и другое из b.

В [ 2 ] на рис. 1 приведён пример двух структур с неравным генным составом, а на рис. 2 показан их общии граф. Над общим графом разрешаются четыре стандартные операции, которые уточняются следующим образом [ 2–4 ]. Двойная переклейка: удаление двух одинаково помеченных рёбер общего графа и соединение четырёх образовавшихся концов двумя новыми неинцидентными рёбрами с той же пометкой. Если при этом образуется ребро с особыми концами (оба относятся к a или оба к b), то оно заменяется одной особой вершиной, которой приписана конкатенация последовательностей двух исходных особых вершин. Полуторная переклейка: удаление ребра общего графа и соединение ребром с той же пометкой одного из его концов с обычной вершиной, не инцидентной ребру с этой пометкой, или с особой вершиной степени не больше 1 с той же пометкой (с возможным последующим отождествлением двух особых вершин). Склейка: добавление ребра (скажем, с пометкой a) между вершинами, каждая из которых является или обычной, не инцидентной ребру с пометкой a или особой степени не больше 1 с той же пометкой (с возможным последующим отождествлением двух особых вершин). Разрез: удаление любого ребра.

Кроме того, вводится только одна дополнительная операция: удаление особой вершины (блока). А именно, если эта вершина степени 2, то она удаляется и инцидентные ей рёбра сливаются в одно ребро, на которое переносится пометка вершины, показано на рисунке из первого дополнительного материала к [ 2 ]; если вершина степени 1, то она удаляется вместе с инцидентным ей ребром; если вершина степени 0 или с петлёй, то вершина и петля удаляются.

В [ 2–3 ] мы свели задачу о преобразовании указанными шестью операциями однои хромосомнои структуры в другую уже при неравных составах к задаче приведения их общего графа к финальному виду этими пятью операциями (называем такое приведение финализацией графа). Сведение произведено для случая, когда цены всех стандартных операции одинаковы, а цены операции удаления и вставки любые. Отметим: на общем графе удалению участка хромосомы соответствует удаление (особои) a-вершины, вставке участка хромосомы – удаление (особои) bвершины. Таким образом, цена финализации – сумма цен операций с оговоркой, что удаление bвершины имеет цену вставки, разрез b-ребра имеет цену склейки, и склейка b-ребром имеет цену разреза.

Здесь мы рассмотрим случаи, когда все цены, кроме операции вставки, одинаковы (скажем, равны 1), а цена вставки больше 1, но не превышает 2, т.е. равна 1+ε, где 0≤ε≤1. Это соотношение цен можно назвать нестационарным, предполагая, что при нём идёт уменьшение числа генов в геноме. В [ 4 ] мы описали алгоритм, выдающии решение, цена которого отличается от цены оптимального решения не более, чем на ε. Здесь мы опишем уточнение этого алгоритма, позволяющее доказать два достаточных условия его абсолютнои точности. Алгоритм финализации общего графа

Итак, дан общии граф a+b и число ε, 0≤ε≤1. Пусть цены стандартных операции и удаления aвершины равны 1, а цена удаления b-вершины равна 1+ε. В описываемыи далее алгоритм мы включили некоторые эвристические усовершенствования, рассчитанные на эвристическое его использование при неравных ценах стандартных операции.

Шаги 1 и 2 те же, что и в [ 4 ], т.е. удаление a-петель и вырезание обычных рёбер. Для описания дальнейших шагов определим типы компонент общего графа, построенного после выполнения шагов 1–2. Их обобщения на компоненты исходного общего графа однозначно определяются по правилу: компонента имеет тип T, если после выполнения шага 2 (т.е. вырезания из неё обычных рёбер) она превращается в компоненту типа T (см. лемму 6 из [ 3 ]). Исключением является случай, когда компонента в исходном графе не содержит особых рёбер, в этом случае припишем ей тип 0.

Нечетной (четной) цепью назовём цепь нечетного (четного) размера. a-Цепью называется нечётная цепь, у которои краиние невисячие ребра помечены a, или изолированная b-вершина. Аналогично определяется b-цепь. Цепям (кроме изолированных обычных вершин) припишем следующие типы. a-Цепи приписываем типы: 1а, если в неи одно висячее ребро; 2а, если в неи два таких ребра или если это изолированная b-вершина; 3а, если у неё нет висячих рёбер. b-Цепям тип приписывается аналогично. Чётнои цепи приписывается тип: 1, если в неи одно висячее ребро и имеется b-вершина и a-вершина; 2, если в неи два висячих ребра; 3, если в неи имеется хотя бы одно ребро и нет висячих рёбер. Среди цепеи типа 1 выделим цепи типа 1a (если висячая вершина – aвершина) и 1b (если она – b-вершина).

Циклу, содержащему a-вершину, но не b-вершину, припишем тип «a-цикл»; симметрично – «b-цикл». Циклу, в котором имеются как a-вершины, так и b-вершины, приписываем тип «(a,b)цикл». Петле с b-вершинои припишем тип «b-петля». Среди цепеи: в типе 2a выделяем подтип 2a' – если это изолированная b-вершина (обобщение на исходныи граф: нет a-вершин) и 2a* для остальных цепеи, аналогично для типа 2b. В типе 3a выделяем подтип 3a' – если это цепь размера 1 (обобщение: нет b-вершин) и 3a* для остальных цепеи, аналогично для типа 3b. В типе 1a выделяем подтип 1'a – если это цепь размера 0, т.е. если она состоит из однои обычнои вершины и инцидентнои еи a-вершины (обобщение: нет b-вершин) и 1*a для остальных цепеи, аналогично для типа 1b. В типе 2 выделяем подтип 2' – если это цепь размера 0, т.е. в неи два висячих ребра и нет других рёбер (обобщение: с однои стороны, все a-вершины, с другои – все b-вершины) и 2* для остальных цепеи. Цепь, содержащую a- и b-вершины назовём (a,b)-цепью; если цепь содержит только вершины одного типа, назовём её, соответственно, (a\b)-цепью или (b\a)-цепью. Компоненту, содержащую b-вершину, но не являющуюся b-циклом, назовём ценной.

Шаг 3. Последовательно выполняем следующие операции между компонентами указанных типов: каждая из них выполняется, пока возможно. Описание даём для первои операции, для других оно аналогично (кроме пункта 3.0). На рисунках маленькие кружочки означают обычные вершины, большие – особые. Перечислим усовершенствования, внесённые здесь по сравнению с описанием в [ 4 ]. Они связаны с тем, что мы желаем максимально избавиться от цепеи типов 2a', 3b' и 1'b, (назовём эти цепи проблемными) поскольку эти цепи не взаимодействуют с (a,b)-циклами, что затрудняет слияние b-вершин.

Вводится предварительный шаг 3.0, на котором проводятся взаимодействия 1'b+2a'=2a' и 1'b+3b'=3b' (это частный вид взаимодействий 4.17 и 4.18 ниже). Это позволяет уменьшить число цепей типа 1'b. На шагах 3.1, 3.3, 3.4, 3.5, 3.8, 3.14, 3.15 выбирается c=b. Это связано с тем, что цепь типа 1*b взаимодействует с проблемными цепями, а цепь типа 1*a – не взаимодействует. На шаге 3.2 взаимодействие 2a+3b=1b разбивается: сначала 2a'+3b*=1*b и 2a*+3b'=1*b, затем 2a*+3b*=1*b и 2a'+3b'=1b. Это связано с желанием максимально избавиться от проблемных цепей. Аналогичное разбиение проводится также на шагах 3.4, 3.5, 3.8, 3.9, 3.10, 3.12–3.19.

3.0. 1'b+2a'=2a', 1'b+3b'=3b'. В 1'b -цепи расклеить ребро и особую вершину склеить с особой вершиной 2a'-цепи, рис. 1a. В 3b'-цепи расклеить любое ребро и особую вершину склеить с особой вершиной 1'b-цепи, рис. 1b.

Рис.1. Шаг 3.0 алгоритма 3.1. 1a+1b=1b. Расклеим крайнее невисячее ребро (назовём его внешним) в цепи типа 1a и соответствующую особую вершину склеим с крайней особой вершинои другой цепи (полуторная переклейка), рис. 2.

Рис.2. Шаг 3.1 алгоритма 3.2. 2b+3a=1a; 2a'+3b*=1*b, 2a*+3b'=1*b, 2a*+3b*=1*b, 2a'+3b'=1b. В 3a-цепи расклеим внешнее ребро и особую вершину склеим с крайней a-вершиной 2b-цепи, рис. 3.

Рис.3. Шаг 3.2 алгоритма 3.3. 2+3=1b. В 3-цепи расклеим внешнее a-ребро и особую вершину склеим с крайней особой вершиной 2-цепи, рис. 4.

Рис.4. Шаг 3.3 алгоритма 3.4. 1a+2b+3=2+3=1b, 1b+2a'+3=2+3=1b, 1b+2a*+3=2+3=1b. Сначала выполняем 1a+2b=2 (описание ниже, шаг 3.12), затем 2+3=1b.

3.5. 1b+3a+2=3+2=1b, 1a+3b'+2=3+2=1b, 1a+3b*+2=3+2=1b. Сначала 1b+3a=3 (описание ниже, шаг 3.13), затем 2+3=1b.

3.6. 1a+2=2a, 1b+2=2b. В 1a-цепи расклеим внешнее ребро и особую вершину склеим с крайней a-вершиной 2-цепи, рис. 5

Рис.5. Шаг 3.6 алгоритма 3.7. 1a+3=3a, 1b+3=3b. В 3-цепи расклеим крайнее b-ребро и особую вершину склеим с крайней b-вершиной 1a-цепи, рис. 6.

Рис.6. Шаг 3.7 алгоритма 3.8. 1a+1a+2b+3b'=2+3=1b, 1a+1a+2b+3b*=2+3=1b, 1b+1b+2a'+3a=2+3=1b, 1b+1b+2a*+3a=2+3=1b. Сначала выполняем 1a+2b=2 и 1a+3b'=3, затем 2+3=1b.

3.9. 1a+1a+2b=3a+2b=1a, 1b+1b+2a'=3b+2a=1b, 1b+1b+2a*=3b+2a=1b. Сначала 1a+1a=3a (описание ниже, пункт 3.11), затем 2b+3a=1a.

3.10. 1a+1a+3b'=1a+3=3a, 1a+1a+3b*=1a+3=3a, 1b+1b+3a=1b+3=3b. Сначала 1a+3b'=3, затем 1a+3=3a.

3.11. 1a+1a=3a, 1b+1b=3b. Склеим крайние b-вершины двух 1a-цепей, рис. 7.

Рис.7. Шаг 3.11 алгоритма 3.12. 1a+2b=2, 1b+2a'=2, 1b+2a*=2. В 1a-цепи расклеим внешнее ребро и особую вершину склеим с крайней особой a-вершиной 2b-цепи, рис. 8.

Рис.8. Шаг 3.12 алгоритма 3.13. 1b+3a=3, 1a+3b'=3, 1a+3b*=3. В 3a-цепи расклеим внешнее ребро и особую вершину склеим с крайней a-вершиной 1b-цепи, рис. 9.

Рис.9. Шаг 3.13 алгоритма 3.14. 2a'+2b+3+3=2+3=1b, 2a*+2b+3+3=2+3=1b. Сначала 2a'+2b+3=2 (описание ниже, шаг 3.18), затем 2+3=1b.

3.15. 3a+3b'+2+2=3+2=1b, 3a+3b*+2+2=3+2=1b. Сначала 3a+3b'+2=3 (описание ниже, шаг 3.19), затем 2+3=1b.

В описании шагов 3.16–3.18 используются вспомогательные взаимодействия 2a+3=1a и 3b+2=1b, которые сами по себе не присутствуют в алгоритме. Их описания ниже.

3.16. 3a+2+2=1a+2=2a, 3b'+2+2=1b+2=2b, 3b*+2+2=1b+2=2b. Сначала 3a+2=1a, затем 1a+2=2a.

3.17. 2a'+3+3=1a+3=3a, 2a*+3+3=1a+3=3a, 2b+3+3=1b+3=3b. Сначала 2a'+3=1a, затем 1a+3=3a.

3.18. 2a'+2b+3=2a'+1b=2, 2a*+2b+3=2a*+1b=2. Сначала 2a'+3=1a, затем 1a+2b=2. 3.19. 3a+3b'+2=3a+1b=3, 3a+3b*+2=3a+1b=3. Сначала 3b'+2=1b, затем 1b+3a=3.

Вспомогательное взаимодействие 2a+3=1a. В 3-цепи расклеить внешнее b-ребро и особую вершину склеить с крайней b-вершиной 2a-цепи, рис. 10.

Рис.10. Взаимодействие 2a+3=1a. Вспомогательное взаимодействие 3b+2=1b. В 3b-цепи расклеить внешнее ребро и особую вершину склеить с крайней b-вершиной 2-цепи, рис. 11.

Шаг 4. Здесь производятся взаимодействия, которые, в отличие от взаимодействий шага 3, не уменьшают общее число операций (точнее, сохраняют его), но позволяют заменить "дорогую" операцию удаления b-вершины на другую, более дешёвую операцию. Отметим: неценные компоненты во взаимодействиях на шаге 4 не участвуют, за исключением двух последних пунктов 4.23–4.24.

Алгоритм зависит от того, цена двоинои переклеики больше цены полуторнои или наоборот. В первом случае последовательно применяем пункты 4.1–4.24, во втором случае – пункты 4.1'–4.24' (в случае равенства цен можно выбрать любой из этих вариантов). Смысл этого разделения поясним на примере пунктов 4.2 и 4.2'. Если цепь типа 2a в пункте 4.2 имеет тип 2a*, применять взаимодействие пункта 4.2 необязательно (разве что при дешёвой полуторной переклейке), поскольку далее (на шаге 4.21) все (a,b)-цепи размера больше нуля замыкаются в (a,b)циклы, (a,b)-циклы сливаются друг с другом и получившийся (a,b)-цикл разбивается на циклы размера 2. Если же эта цепь имеет тип 2a', это взаимодействие (пункт 4.2') следует применить, чтобы «уничтожить» эту проблемную цепь.

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

4.1. «b-петля»+любой тип t с b-вершиной = тип t. Объединить b-вершину петли с b-вершиной компоненты типа t двойной переклейкой (если эта цепь не изолированная b-вершина, рис. 12a) или полуторной переклейкой (иначе, рис. 12b).

Рис.12. Шаг 4.1 алгоритма 4.1'. То же, что и 4.1.

4.2. 2a+2b*=2+1'a. Полуторная переклейка с отрезанием двух вершин 2b*-цепи (крайней aвершины и соседней обычной вершины) и склейкой образовавшегося края с крайней b-вершиной 2a-цепи, рис. 13.

Рис.13. Шаг 4.2 алгоритма 4.2'. 2a'+2b*=2+1'a.

4.3. 3a*+3b=3. В 3a*-цепи расклеить внешнее ребро и особую вершину склеить с крайней обычной вершиной 3b-цепи, рис. 14.

Рис.14. Шаг 4.3 алгоритма 4.3'. 3a*+3b'=3.

4.4. 2a+3=1a, 2b*+3=1b. В 3-цепи расклеить внешнее b-ребро и особую вершину склеить с крайней особой вершиной 2a-цепи, рис. 15.

Рис.15. Шаг 4.4 алгоритма 4.4'. 2a'+3=1a 4.5. 3a*+2=1a, 3b+2=1b. В 3a-цепи расклеить внешнее ребро и особую вершину склеить с крайней особой вершиной 2-цепи, рис. 16. 4.5'. 3b'+2=1b. 4.6. 2a+2a=2a, 2b*+2b*=2b*. Склеить крайние особые вершины двух цепей, рис. 17.

Рис.17. Шаг 4.6 алгоритма 4.6'. 2a'+2a=2a.

4.7. 3a*+3a*=3a*, 3b+3b=3b. Две крайние обычные вершины цепей соединить обычным ребром с последующим его вырезанием, рис. 18.

Рис.18. Шаг 4.7 алгоритма 4.7'. 3b'+3b=3b. 4.8. 1a+2a=1a, 1b+2b*=1b. Склеить крайние особые вершины двух цепей, рис. 19.

Рис.19. Шаг 4.8 алгоритма 4.8'. 1a+2a'=1a.

4.9. 1a+3a*=1a, 1b+3b=1b. Две крайние обычные вершины цепей соединить обычным ребром с последующим его вырезанием, рис. 20.

Рис.20. Шаг 4.9 алгоритма 4.9'. 1b+3b'=1b.

4.10. 2a+2=2, 2b*+2=2. Склеить крайние особые вершины двух цепей, рис. 21. 4.10'. 2a'+2=2.

Рис.21. Шаг 4.10 алгоритма Рис.22. Шаг 4.11 алгоритма 4.11. 3a*+3=3, 3b+3=3. Две крайние обычные вершины цепей соединить обычным ребром с последующим его вырезанием, рис. 22.

4.11'. 3b'+3=3.

4.12. 2+2=2+1'a. Полуторная переклейка с отрезанием двух вершин 2-цепи (крайней aвершины и соседней обычной вершины) и склейкой образовавшегося края с крайней b-вершиной другой 2-цепи, рис. 23.

Рис.23. Шаг 4.12 алгоритма 4.12'. Пустое действие.

4.13. 3+3=3. В 3-цепи расклеить внешнее a-ребро и образовавшийся край этой цепи склеить с b-краем другой 3-цепи, рис. 24.

Рис.24. Шаг 4.13 алгоритма 4.13'. Пустое действие.

4.14. 1*a+1*a=1*a, 1b+1b=1b. В 1a-цепи расклеить внешнее ребро и особую вершину склеить с крайней особой вершиной другой 1a-цепи, рис. 25.

Рис.25. Шаг 4.14 алгоритма 4.14'. 1'b+1b=1b.

4.15. 1a+1b=1a, 1b+1*a=1b. В 1b-цепи расклеить внешнее ребро и особую вершину склеить с крайней особой вершиной 1a-цепи, рис. 26.

Рис.26. Шаг 4.15 алгоритма 4.15'. 1a+1'b=1a.

4.16. 1a+1*a=1a, 1b+1b=1b. В 1a-цепи расклеить внешнее ребро и особую вершину склеить с крайней особой вершиной 1*a-цепи, рис. 27.

Рис.27. Шаг 4.16 алгоритма 4.16'. 1b+1'b=1b.

4.17. 2a+1b=2a, 2b*+1*a=2b*. В 1b-цепи расклеить внешнее ребро и особую вершину склеить с крайней особой вершиной 2a-цепи, рис. 28.

Рис.28. Шаг 4.17 алгоритма 4.17'. 2a'+1b=2a, 2a+1'b=2a. 4.18. 3a*+1*a=3a*, 3b+1b=3b. В 3a*-цепи расклеить внешнее ребро и особую вершину склеить с 4.18'. 3b'+1b=3b, 3b+1'b=3b.

4.19. 2+1*a=2, 2+1b=2. В 1*a-цепи расклеить внешнее ребро и особую вершину склеить с крайней особой вершиной 2-цепи, рис. 30.

Рис.30. Шаг 4.19 алгоритма 4.20'. 3+1'b=3. Шаги 4.21–4.24 одинаковы для обычного и «штрихованного» вариантов.

4.21. Замыкание цепей в циклы, кроме цепей типа 3b' (они ещё могут «пригодиться» на шаге 4.24), проблемных цепей и цепей типа 2' (они в цикл не замыкаются). Цепи, имеющие невисячее ребро, замыкаем в циклы склеикои (цепи типа 2a*, 2b*, 3a, 3b*), полуторнои переклеикои с отождествлением двух особых вершин (цепи типа 1*a, 1*b, 2*) или без отождествления (цепи типа 1a, 1b, 3). При замыкании цепи типа 2* выбираем вариант с отождествлением двух b-вершин, рис. 32. Из циклов, получившихся при замыкании цепеи типа 3a* или 3b*, вырезаем обычные рёбра.

Рис.32. Замыкание в цикл цепи типа 2 4.22. Пока возможно, осуществлять взаимодействие (a,b)-цикл+любой тип t с b-вершиной и a-вершиной = тип t. Вставить цикл (двойной переклейкой, отождествляющей две b-вершины) рядом с b-вершиной из компоненты типа t с той стороны, в которой находится a-вершина; образовавшееся обычное ребро вырезать, рис. 33. Впрочем, легко видеть, что фактически t может быть лишь (a,b)-циклом или цепью типа 2'.

Рис.33. Шаг 4.22 алгоритма, t=2' 4.23. Если возможно, выполнить взаимодействие (a,b)-цикл+2a'+2b'=2. Сначала полуторной

Рис.34. Первая часть шага 4.23 алгоритма

Рис.35. Первая часть шага 4.24 алгоритма Шаг 5. Оставшиеся цепи (типов 1'a, 1'b, 2', 2a', 2b', 3b') приводим к финальному виду по отдельности. Из циклов размера больше 2 вырезаем циклы размера 2 так, чтобы происходило отождествление двух b-вершин (соответственно, в вырезанныи цикл включается a-вершина), рис. 36. Из циклов размера 2 удаляем особые вершины.

Рис.35. Вырезание из (a,b)-цикла a-цикла Алгоритм описан. Пусть B' – число b-циклов в графе a+b. Напомним обозначения из [ 4 ]: B – число особых вершин в a+b; S – сумма целых частей половин длин максимальных отрезков в a+b, которые состоят из обычных рёбер (называем из сегментами), плюс число нечётных (т.е. нечётной длины) крайних сегментов минус число циклических сегментов (крайним называется сегмент, расположенный с краю цепи, включая и случай целой цепи), D – сумма дефектов компонент графа a+b (дефект цепеи типа 1a, 1b 3a, 3b и 3 равен 1, дефект цепеи других типов или цикла нулевои), P – разность величин D, вычисленных до и после применения шага 3 алгоритма, т.е. число операций, сэкономленных на шаге 3. Величина ε определена выше. Пусть C=B+S+D–P+ε(B'+1).

Теорема 1. Алгоритм строит последовательность операций, суммарная цена которой равна одному из трёх значений C–ε, C, C+ε. Минимально возможная суммарная цена последовательности операций, приводящей граф a+b к финальному виду, также равна одному из этих значений. Время работы алгоритма линеиное. Ключевои момент в доказательстве первого утверждения теоремы 1: после выполнения шага 4 остаётся не более двух ценных компонент. Если их остаётся две, то одна из них – (a,b)-цикл, вторая – проблемная цепь. Подробное доказательство теоремы 1 приведено в [ 4 ].

Следствие 1. Если после шага 4 остаётся не более однои ценнои компоненты, то алгоритм выдаёт абсолютно точное решение. Если остаётся две ценных компоненты, алгоритм выдаёт решение, цена которого может превышать цену оптимального решения не более, чем на ε.

Доказательство. Из доказательства теоремы 1 [ 4 ] вытекает, что если после шага 4 остаётся 0, 1 или 2 ценных компоненты, то цена построеннои алгоритмом последовательности равна, соответственно, С(G)–ε, С(G) или С(G)+ε. Поэтому достаточно доказать, что если цена построенной алгоритмом последовательности равна С(G)–ε или С(G), то такова же цена оптимальной последовательности, если же первая цена равна С(G)+ε, то цена оптимальнои последовательности не меньше С(G). Утверждение для С(G)–ε сразу следует из теоремы 1. Для двух других значений докажем его индукцией по минимальной суммарной цене M операций, приводящих общий граф G к финальному виду.

Базис индукции тривиален, опишем индуктивный шаг. Пусть o – первая операция в оптимальной последовательности операций, c(o) – её цена, o(G) – результат её применения к G. Из описания алгоритма следует, что если ценные компоненты присутствует в начальном общем графе, то хотя бы одна ценная компонента останется и после шага 4 алгоритма, а если в начальном графе нет ни одной ценной компоненты, то их не возникнет и после шага 4. Поэтому возможны лишь следующие случаи. 1) В графах G и o(G) имеется ценная компонента. По предположению индукции цена оптимальнои последовательности для G не меньше c(o)+C(o(G)). Учитывая установленное при доказательстве теоремы 1 неравенство c(o)≥C(G)–C(o(G)) [ 4 ], получаем, что эта цена не меньше C(G), откуда следует требуемое утверждение.

2) В графе G имеется ценная компонента, а в графе o(G) её нет. По предположению индукции цена оптимальнои последовательности для G равна c(o)+C(o(G))–ε. Легко видеть, что возможны лишь следующие два случая.

2.1. Операция o превращает ценную компоненту в b-цикл. В этом случае c(o)=1 и o увеличивает величину B' на 1. Тогда C(G)–C(o(G))≤1–ε. Отсюда c(o)+C(o(G))–ε≥С(G), что и требуется.

2.2. Операция o удаляет b-вершину из ценнои компоненты. В этом случае c(o)=1+ε и o не меняет величину B'. Тогда C(G)–C(o(G))≤1. Отсюда c(o)+C(o(G))–ε≥С(G), что и требуется.

Следствие 1 доказано. Следующее следствие формулирует достаточные условия абсолютнои точности алгоритма в терминах исходных структур a и b и графа a+b.

Следствие 2. Алгоритм выдаёт абсолютно точное решение в любом из следующих случаев: 1) Структура a не содержит особых генов; 2) Структура b не содержит особых генов; 3) Cреди компонент графа a+b нет проблемных цепеи (в частности, когда все хромосомы в a и b кольцевые).

Доказательство. В случаях 1 и 2 в общем графе не возникает (a,b)-циклов, поэтому после шага 4 остаётся не более однои ценнои компоненты. По следствию 1 выдаваемое алгоритмом решение абсолютно точное. В случае 3 из описания алгоритма следует, что в ходе него не возникнет проблемных цепеи и рассуждение аналогично. Следствие 2 доказано.

Работа выполнена за счёт гранта Российского научного фонда (проект № 14–50–00150).

References