Данная статья является очередной в серии статей авторов, в которых они продолжают исследовать задачу оптимального преобразования одной данной хромосомной структуры в другую. Излагается алгоритм уравнивания генных составов двух данных структур, позволяющий свести общий случай этой задачи к частному случаю, где обе структуры имеют равный генный состав. Решение задачи в этом частном случае, а также альтернативный алгоритм для общего случая описаны в предыдущих статьях авторов. Рассматриваемый здесь алгоритм существенно проще альтернативного, что позволяет применять его к структурам с десятками тысяч генов. Мы строго доказываем его корректность.
на случай, когда операции имеют неравные цены. В данной работе описывается более простой для случая неравного генного состава и равных цицйен. Эотпоетра алгоритм позволяет быстро обрабатывать структуры с большим числом генов, вплоть до нескольких десятков тысяч. Он пре описан в [4], однако строгое доказательство его корректности там отсутствует. Мы приводим доказательство.
Вкратце анпомним основные определенияХ.ромосомная структура определяется как ориентированный граф, состоящий из цепей и циклов, которые не пересекаются, включая (кольцевые хромосомы из одного гена); каждое ребро графа представляет ген, ребруимяприписывае этого гена (обычно именами служат натуральные числа). В этом смысле ребро с приписанным е называется далеегеном, а цепи и ц–икхлрыомосомами. Мы рассматриваем случай, когда имена в структуре не повторяются. Говорят, что две стaриукbтуирмыеют равный генный состав, если они содержат одно и то же множествГоен, импёрне.дставленныи своим имaениемb, навзове омбщим; ген, представленныи лишь в однои из– оссторбуыкмт:урсоответственно, имеютсяa- и b-особые гены. Кольцевую хромосому, состоуяющ целиком из особых генов, носаозбоовйе. м На рисункеa п1риведены две хромосомные структaуирыb с равным генным составом.
Рис. 1. a) Две хромосомные структуры a и b с равным генным составом; b) Общий граф a+b структур a и b, определяемый сразу после рис. 3 При преобразовании структуaрыв b разрешаются следующие операции.
(
(
(
В случае неравного состоапвраеделение общего графа a+b изменяется следующим образом. Он содержит обычные вершины – края общих генов с их имеонсаомбиы,е виершины – максимальные по включению связные участки a-иозсобых или иb-зособых генов (возможно, циклические). Особая вершина пмоечается как a- или b-вершина, ей такжпериписывается последовательность соответствующего участка генов. Общий граф содержит следующОибеычнроёберрае.бро соединяет две обычные вершины, если соответствующие им края отождествлены (сакилелеинbы;)осовбое ребро соединяет обычную вершину с особой, аесиллии bв край, соответствующий обычной вершине, отождествлён (склеен) с краем участка, соответствующего особой вершине. Такое ребро помечаетс a- или b-ребро. Петля в a+b соответствует особой хромосомсео,ответствующая особая вершина соединяется с собой. Как и прежде, общий граф неориентированный и состкомитпониензт с–вязных цепей и циклов.
На рис. 4a приведён пример двух структур с неравным генным составом, а на рисунке 4b показан их общий граф.
Рис. 4. Две хромосомные структуры с неравным генным составом (a) и их общий граф (b). Жирные точки
показывают особые вершины Алгоритм уравнивания генных составов
Основная идея алгорит–муаравнять генныи состав данных структур, адобсоабвыиве b-вгены, а bв – особые a-гены (кроме генов осиозбых хромосом). Все добавляемые гены раскладываются по нескольким кольцевым хромосомам, назове м эти хромосомы иновгыемниы(a-вновныимхи bи-новыми). Их конкретныи вид определяет следующее условие: послеособуыдахленхиряомосом полученные структуры a' и b' (с равным генным составом) должны преобразовываться одна в другую минимальн числом операции . Назовем особые гены, не лежащие в особыосхобехнрноыммосио.маОхч,евидно, граф a'+b' получается из граaф+аb удалением петель и особых вершин и добавлением вместо –них верш крае в особенных генов, –рсеклебеекр между этими краяaми b ви ре бер двух полных паросочетании : между краямиa-особенных генов и между крbа-оясмоибенных генов. Ре бра первого паросочетания соответствуют склеи кам крае в генов в новых aхриомопсооммеачхаютвся пометкbо.иРе бра второго паросочетания соответствуют склеи кам крае в генов в новыхb ихропмомосеочмаюахтсяв пометкaо.и Из ранее упомянутого результата [1] следует, чaт'+оb' дгроалфжен иметь максимально возможное качество. В [4] подробно описан алгоритм построения этих паросочетании , и мы лишь проиллюстриру примере структуaр и b, изображе нных на4. рис.
Изобразим графa+b с подробной«расшифровкой» содержания особых верширни,с. 5.
На рис. 5 синие отрезки изображаютa-гоесноыбы,е красные– особые b-гены (эти отрезки не являются ре брами графа). Рассматриваем максимальные пути из че рных ребер, оканчивающиеся с однои стороны краем особого гена (здесь их 4)ыеи криазоялиорсоовбаыннх генов (здесь их 4). Такие пути могут быть двусторонними (т.е. оканчиваться краями особых генов с обеих сторон, здес односторонними (здесь их 2), к последним также относим изолированные края особых генов всего их 6). Двуоснтноире пути бывают однородными (т.е. оканчиваются краями одного цвета) неоднородными (здесь оба пути неоднородные). Односторонние пути естественным образом делятс Рис. 5. Тот же граф, что на рис. 4b, c «расшифровкой» содержания особых вершин. Синие отрезки – особые a-гены, красные – особые b-гены 1) Добалвяем вM склеенные пары крае в особых генов (в рассматриваемом примере таких па поскольку все особые вершины содержали по одному гену).
2) Каждыи двустороннии однородныи путь замыкаем в Mцпиакрлу, дегообавклояняцов. 3) Пока существует пара ордовнуснтих неоднородных путеи , соединяем их в цикл,M двобеавляя в пары соответствующих концов (в этом п–рпиамреыре52, 62 и 72, 82).
4) Пока существует пара односторонних путеи одного цвета и разнои че тности, соединяе цепь, добавляя Mвпару их концов (в этом п–рпиамреыре51, 92 и 61, 91).
5) ДостраиваемM произвольным образом (в этом пр–ипмаерае 71, 81). На рис6. серые ре б–рпаары построенных паросочетании .
Рис. 6. Тот же граф, что на рис. 5, с добавленными серыми рёбрами построенных паросочетаний Качество q графа, составленного из че рных и серых ре бер (и изолированных черных вершин В следующем разделе мы покажеrм(a,,b)ч=тCо0+n–q, гдCе0 – суммарное количество особых хромосaом в и b (здесь их неnт–), число генов a'в(здесь их 9). Таким обрr(аaз,оbм)=,5. Доказательство корректности алгоритма со структуройp(o(a)) или получается из нее удалениемg. гПеноа предположению индукции r(p(o(a)),b))≥r(p'(o'(a)),b)). Отсюдrа(o(a),b)=r(p(o(a)),b))+1≥r(p'(o'(a)),b))+1=r(o'(a),b).
В случае, когда b вимеются особые хромосомы, aа ихв нет, рассуждение симметри–чно рассматривается переход bокт a обратными операциями. Лемма доказана.
Перейдём к доказательству теоремы. Докажеdм≤,d'+чCт0о. Обозначим череaз+ и b+ структуры a' и b' до удаления из нихыхосохбромосом. По лемме существует минимальная последоватSе'лоьпнероастцьии , преобразующая a+ в b+, начинающаяся удалением особых хромосaо+ми иззаканчивающаяся вставкой особых хромосом bи+з. Между этими удалениями и вставками сaт'рпуркетоубрраазуется в b'. Таким образом, S' содержит d'+C0 операции. Построим по ней последовательноS,стьпреобразующуюa в b, и имеющую не большую д.линНуачальнаяи конечная часть S (удаление и вставка особых хромосом) переносятся из S' без изменении.
Рассмотрим среднюючасть последовательностиS', обозначаем промежуточные структуры в неи через t. Начальным циклом в такой структуtрнеазовём кольцевую хромосому, состоящую целикaо-нмовыизх генов, которые и во всех структtутроажхе дпоринадлежат кольцевым хромосомасмт,оя щсоим целиком из a-новых геновК. онечным циклом в t назовём кольцевую хромосому, состоящую целикbо-мновыизх генов, которые и во всех структурахt топжоеслепринадлежат кольцевым хромосомам, состоящим целиком иbз-новых геновР.азделим все компонентыкажвдой t на три части: начальную, основную и конечную, где начальная ч–асвтсье начальные циклы, конечная –чвассеть конечные циклы и основная часть – всё остальное. В первой струaк'ткуорнеечная часть пустап.осВледней структуре b' начальная часть пуста. Перебирая от начала tвисе соответствующие операции, строим последовательSн,ость состоящую из основных частей стрtувкмтеусрте со следующими операциями. oП–утсеткьущая операция в S'. Если все хромосомы, к которым она применяется, лежатй вчасотсиновснторуктурt,ы а все хромосомы, получающиеся из них в результате приoм,енленжиаят в основной части стрoу(кt)т,уртыо операция o добавляется кS, её результ–атосновная часть структурoы(t). Если среди хром-осом аргументов операцииo есть хромосоамh из начальной части структtу, рыа все хромос-зонмаычения лежат в основной части струкo(тtу)р,ыто участок из всех новых генов, состhа,влвясютщавилхяется в основную часть структурtытак, что получается основная часть стрoу(кt)т.урыЭта операция аввксит добавляется кS. Аналогично, если среди хро-мзноасчоемний есть хромосомhаиз конечной части структуры o(t), а все хромос-аормгыументы лежат в основной части стрt,укттуорыучасток из всех новых генов, составляющихh, удаляется из основной часткитурсытрtутак, что получается основная часть структуры o(t). Эта операция удаления добавляеSт.ся Накконец, если все хром-оасрогмумыенты и хромосомы-значения не лежат основной части стрt,уктнуиркыакая операция не добавляSе(твспярочкем, этот случай приовторечит минимальностиS'). Очевидн,оникакие другие случаи невозможны.
Ясно, чтSо не длиннее, чSе'м. Неравенствdо≤d'+C0 доказано.
Докажем, чтdо'≤d–C0. Рассмотрим минимальную последовательносSтоьпераций, преобразующуюa в b, начинающуюся с удалевнсиеях особых хромосом a ииз заканчивающуюся вставкой всех особых хромосом изb (она существует по доказанной лемме). Построим по ней a'с,трbу' ктиуры последовательность S', преобразующуюa' в b' и имеющую длину по крайней Cм0емреньншае длиныS. Отбросим начальную и конечную Sч.астСитруктураa' получается изa добавлением новых хромосом, являющимися зацикливаниями участков генов, вставляемых операциями всSт.авкСитруикзтураb' получается иbздобавлением новых хромосом, являющимися зацикливанчиаясмтикову генов, удаляемых операциями удаления Sи.зПеребирая от начала структуры и операции в средSн, ейстрчоаисмти последовательность S'. В её структурах гены, как и раньше, делятся на три части: начальную, о конечную. Основная часть любойктусртрыу вS' совпадает с соответствующей структурSо.й Пвустьo – очередная операция S.в Если она стандартная, добавляеSм', еаё овчередная структура получается из предыдущей заменой основной части на результат применения к нoей. Еосплеиoра–цоипиерация удаления участка генов, то, очевидно, существует стандартная операция, вырезающая и зациклива этот участок (пустая, если он уже цикл). ДобавSл'явемместеё сок структуро–йрезультатом её применения, и помещаем новую кольцевую хромосому увю кчоансетчьн. Есoли– операция вставки участка генов, то составляющая его кольцевая хрhопмоосопмоастроению присутствует в начальной части текущей структурыS' и,в очевидно, существует стандартная операция, вставляющая этот участок в нужное место (пусетсаляи, h вставлялась целиком). Добавляем Sе'вёмексте с её результатом (при этом h удаляется из начальной ча.стОич)евидно, так построенная последовательSн' онсеть длиннее средней части S. Неравенствdо≤d'+C0, а вместе с ним и 1 тдеоокраезманаы.
После тгоо, как построены структaу',рbы' и минимальная последовательносSт',ь преобразующаaя' в b' (например, как описано в [1]), алгоритм строит минимальную последоSв,атперлеьонборсатзьующуюa в b, в соответствии с описванипеемрвой части доказательствраемтыео1.
Теорема 2. Общий графa'+b' построенных в алгоритме струaк'тиурb' имеет максимальное качество. Доказательство. Будем доказывать корректность алгоритма построения двух паросочетаний по шагам. Для каждого из ш–а4гов по1кажем, что если пара, ннваыябрана этом шаге не входят в объединение M паросочетаний, то можно так их перестроить, чтобы она входила в объединение паросочетаний, и новый граф имел качество не меньше, чем прежний. Используем термины, вв при рассмотрении алгоритма на ерперимв предыдущем разделе.
Склейку краёв особых генов, упоминаемую на шаге 1 алгоритма, можно рассматривать
двусторонний однородный путь, поэтому обоснования шагов 1 и 2 одинаковы. А именно, предп
что пара краeё1ви e2 такого пути не входMи.тТогвда эти края входят в некоторыeе1,e3п)ариыe2,e(4() из
M. Заменим их на eп1а,eр2ы) иe(3,e(
Обоснуем шаг 3. Предположим, что парыe1,eк2)раёивe3,e((
Обоснуем шаг 4. Предположим, что параe1,eк2)раоёдвнос(торонних путеи одного цвета и разнои
че тностние входит M.в Тогда эти края вхнодекяоттоврые парыe1,e(
Обоснуем шаг 5. После выполнения шага 4 может остаться не более одного двустор неоднородного пути, одностороннaи-пеути одной и той же чётности и одноbс-птуотрионноиденой и той же чётности. Очевидно, качество итогового общего графа не зависит еойтки спэотсиохба пусткелй друг с другом.
Теорема 2 и корректность алгоритма уравнивания доказаны. Заключение
В данной работе мы описали алгоритм уравнивания генных составов для построения миним последовательности операций, преобразующих одну данную хромосстормункутюуру в другую. Ран-ее [2 3] мы описали альтернативный алгоритм решения той же задачи, основанный на взаимодействия общего графа. Оба алгоритма имеют линейное время работы. Алгоритм уравнивания имеет короткое описание и более простуюзацриеюа л.и Это позволяет обобщить его на случай, когда в исход структурах имеются паралоги, т.е. гены с одинаковыми именами (статья сдана в печать). стороны, альтернативный алгоритм может быть обобщён на случай неравных цен операци Интересной темой будущего исследования может быть обобщение на этот случай и алгор уравнивания. Благодарности Работа выполнена за счёт гранта Российского научного фонда –(п5р0о–0ек0т150№). 14 References Об авторах: Горбунов Константин Юрьевич, кандидат физ и-мкаотематических наук, ведущий научный сотрудник лаборатории № , И6нститут проблем передачи информации им. А.А. Харкевича Российской академии наукg,orbunov@iitp.ru Любецкий Василий Александрович, доктор физи-мкаотематических наук, профессор, заведующий лабораторией № , И6нститут проблем передачи информации им. А.А. Харкевича Российской академии нау;к профессор мехнаико-математического факультета, Московский государственный унвиерситет иемни М.В. Ломоносов,аlyubetsk@iitp.ru Note on the authors: Gorbunov Konstantin Yu., Candidate of Science in physics and mathematics, leading research fellow, Institute for
Information Transmission Problems of the Russian Academy of Sciences, gorbunov@iitp.ru Lyubetsky Vassily A., Doctor of Science in physics and mathematics, professor, head of the laboratory, Institute for Information Transmission Problems of the Russian Academy of Sciences; professor, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, lyubetsk@iitp.ru