Модель структуры хромосомы описана как конечное набор путей и кругов с направленными краями включая петли. Такой набор можно рассмотреть как направленный упомянутый граф как структура хромосомы. Край графа представляет ген; отдельный путь графа или круг представляют a хромосома. Каждый ген обозначен по имени, обычно номер i, который может быть повторен (для парарегистраций) и принимает форму i.j. Как обычно, эта модель игнорирует длины генов и межгенных регионов, а также их содержание. Направление края указывает на берег на который ген расположен. Узел графа соединяет смежные гены независимо от их ориентации, т.е., это определяет (или клеи вместе) две оконечности смежных генов. Обычные структуры включайте много путей и кругов, который приводит к своего рода взаимодействие между ними. Именно поэтому случаи со многими хромосомы в их структуре находятся на отмеченном контрасте с теми с единственной хромосомой. Модель включает операции по хромосоме структура; сначала четыре из них поданный [18, 20] будут отнесены к как стандарт. Давайте вспомним их определения. Дважды вырезанный и вставленный сокращает две пары смежных генные оконечности и вырезание и вставка четырех оконечностей, который дает начало новой структуре. Sesqui вырезан и вставлен сокращает две смежных оконечности и присоединяется к одной оконечности к несвязанной оконечности так, чтобы другая оконечность остается свободным. Сокращение-и-соединение сокращает две смежных оконечности приведение к двум свободным оконечностям или, наоборот, присоединяясь две свободных оконечности. Нам дают структуры хромосомы a и b; ген это принадлежит обеим структурам, назван общим геном, в то время как ген, который принадлежит одной структуре только, является специальным предложением один; a-gene принадлежит структуре a; и b-gene, к структуре b. Давайте введем две дополнительных операции то преобразование в b: удаление (самый длинный непрерывный) область специального a-genes и вставка региона из специального b-genes. Если удаленный регион был строго в пути или кругу, получающиеся свободные оконечности общих генов присоединился; если регион закончил путь, общее генная оконечность становится свободной; если регион был отдельным хромосома, это естественно удалено. Если (непрерывный) регион вставлен строго в пути или кругу, вставкепункт сокращен, который не является отдельной операцией; вставка может произойти в конец пути или как новая хромосома. Этолегкий доказать, что удаления (непрерывных) несамых длинных области специального a-genes не уменьшают расстояние между структурами. Точно так же сокращая в специальном предложении регионы, вставка специального b-genes в специальное предложение регион, и дважды - и sesqui вырезает и вставляет получающиеся операции в сокращении области специального a-genes и его циркулярной рассылки писем может также быть исключен из первых трех операций. Такой “неестественные” операционные варианты не позволены. Таким образом шесть операций даны, и каждый из них присваивал положительный рациональный номер, называемый вес. Включение весов является ключевым пунктом модель. Цель состоит в том, чтобы найти самую короткую последовательность эти операции, которые преобразовывают структуру в структуру b. Естественно, у самой короткой последовательности есть минимальное общее количество вес всех его действий. Каждая операция в последовательности рассмотрен вместе с хромосомой структура, к которой это применено. Сокращение проблемы парарегистраций к линейномупрограммирование Для краткости давайте обозначим структуры с парарегистрациями как “parstructures” и структуры без парарегистраций как “структуры”. Расстояние между двумя структурами паритета определено как минимальное расстояние между получающимися структурамиот взаимно однозначного соответствия между парарегистрациями каждого существующего гена в обеих начальных структурах паритета. Определенно, ген i от у обеих структур паритета a и b может быть различное число из парарегистраций, которые принадлежат наборам Ра (i) и Рb (i), соответственно. Позвольте fi быть взаимно однозначным соответствием между частями наборов Ра (i) и Рb (i); индексы i.j найдены для всех, паразагружает Ра (i) и Рb (i), для какой fi является функцией идентичности; все парарегистрации, не включенные в функции у fi область и диапазон есть различные индексы. Конечно, у частей нет повторяющихся индексов. Нумерация имеет естественную интерпретацию: если y = fi (x), y “унаследован” от x; другие парарегистрации от Ра (i) и Рb (i) независимы взаимно различные гены, и таким образом у них есть различный j индексы. Парарегистрации, которые не принадлежат области и диапазон fi рассматривают, как потеряно и появились, соответственно (на краю, соединяющемся a и b на филогенетическом дереве). Теперь расстояние между a и b определено как минимальное расстояние между’ и b’, которые получены от a и b для всех указанных индексов парарегистраций от структур паритета a и b. Вычисление расстояния между структурами паритета первоначально уменьшен до целого числа линейного программирования (ILP), который, как известно, дает точное решение с близко к линейное время и сложность памяти для случайных данных [2–4]. Эта специальная собственность линейных, целого числа, и Булев программирование сформулировано как почти линейный алгоритм; это рассматривают в многочисленных публикациях и не обсуждают здесь. Таким образом решение, найденное ILP, определяет a набор взаимно однозначных соответствий {fi |i} между парарегистрациями. Тогда произвольные индексы из парарегистраций, соответствующих под этими взаимно однозначными соответствиями, отобранный; результат не зависит от выбора индекса. Наконец, алгоритм описан в Секции “Определение из общего графа и его конечной формы” относится вычислите расстояние между полученными структурами ’ и b’. Сокращение к ILP описано в Секции “Вычисление контрольной точки и биологический расстояния для структур с парарегистрациями” и “Вычислением биологическое расстояние с существующими путями”. Так как алгоритм, представленный ниже, линеен, вычисление из расстояния между структурами паритета становится почти линейный. Точность все еще наблюдается. Таким образом, один может предположить, что отсутствие паразагружает остаток от Часть “Точный линейный алгоритм, вычисляющий расстояние между структуры хромосомы”.Определение общего графа и его конечной формы В общем графе a+b двух структур a и b,узлы являются оконечностями общих генов, а также всех самые длинные непрерывные области специальных генов; каждая оконечностьвзят однажды. В более формальных терминах, генных оконечностях назначены название гена с индексами 1 и 2 в течение его начала и конца, соответственно. Узлы первые и вторые типы упоминаются как обычные и особенный, соответственно. Край соединяет два обычных узлы, если оконечности смежны в одном из структуры, т.е., граничат друг с другом на хромосоме. Край соединяет обычные и специальные узлы если оконечность общего гена смежна с крайним ген в области специальных генов. Края в первом и вторые случаи называют обычными и особенными, соответственно. Крайний край со специальным концом в a путь от a+b упоминается как вывешивание. Края обозначены a или b в зависимости от структуры, где присоединение произошел; узлы могут быть связаны двойными краями. Специальные узлы обозначены a-или b-узлы в зависимости от исходная структура. Граф может содержать изолированный узлы – области специальных генов. Если такой регион является кругом в начальной структуре петля назвала особенным, добавлен к узлу. Это приводит к ненаправленному упомянутому графу как a+b. Аналоги пяти операций по структурам могут быть применены к общему графу a+b следующим образом (см. числа в Разделе № 1 Дополнительных материалов). (1) Удаляют два края неинцидента с тем же самым индексом и соединяются четыре получающихся конца двумя новыми краями неинцидента с тот же самый индекс. (2) Удаляют край (например, aedge) и соедините один из его концов с обычным неинцидент узла к край или со специальным анодом больше чем без одного инцидента край. (3) Удаляют любой край. (4) Использование край (например, край) к соедините узлы, каждый из которых является обычным и неинцидентом к край или специальное предложение край без больше чем один инцидент край. Если операция приводит к два инцидент специальные узлы, они слиты (который является частью из операции); получающемуся узлу дают имя объединение тех из начальных узлов. (5) Удаляют специальное предложение узел или специальная петля. Если у этого узла было два обычных инцидент узлов к нему, они связаны с краем. Аналог шестой операции, вставки, легко определить; однако, оказывается, что это может быть опущено без потеря общности. Это - не тривиальное заявление; посмотрите начало Секции “Вычисление расстояния между структурами”. Конечная форма общего графа a+b определена как общий граф, состоящий из обычных изолированных узлы и заключительные 2 круга. Последний определен как граф из двух обычных узлов, связанных обычным края, один от a и один от b. Легко показать это начальная цель эквивалентна преобразованию графа a+b в конечную форму с определенными ограничениями на операцию веса, в частности когда операции кроме у вставки и удаления есть тот же самый вес.Вычисление расстояния между структурами Давайте вспомним, что эта секция принимает отсутствие парарегистрации, но все операции, различное генное содержание, и любые операционные веса позволены. Общий граф a+b тривиально построен из начальных структур a и b. Цель алгоритма состоит в том, чтобы преобразовать a+b в конечная форма. Давайте обозначим длину пути или круг количеством внутренних специальных узлов плюс количество обычных краев. Например, 2-круг является кругом длины 2. Имея ту же самую структуру, алгоритм зависит от пропорции между операционными весами, которые являются фиксированный заранее. Алгоритм является следующим.