Обмен ближайшими соседями и относительные расстояния: различия между версиями

Еще одна мотивация для исследований в области вычисления расстояния переноса поддеревьев с линейной стоимостью заключается в следующем. Когда в процессе эволюции происходит [[рекомбинация ДНК]], две последовательности встречаются и генерируют новую последовательность, состоящую из генетического материала, взятого слева от точки рекомбинации первой последовательности и справа от точки рекомбинации второй последовательности [5, 6]. С филогенетической точки зрения перед рекомбинацией наследственный материал существующей последовательности был расположен на двух последовательностях – на одной он располагался слева от точки рекомбинации, на второй – справа от точки разрыва. В результате эволюционная история уже не может описываться одним деревом. Событие рекомбинации разбивает последовательности на две соседствующие области. История левой и правой областей может быть описана разными эволюционными деревьями.  Рекомбинация создает различие между эволюционными деревьями, описывающими соседние области. Однако два соседних дерева не могут различаться произвольным образом; одно должно получаться из другого при помощи операции переноса поддеревьев. Когда происходит более одной рекомбинации, описать эволюционную историю можно при помощи списка эволюционных деревьев, каждое из которых соответствует некоторой области последовательностей, и каждое из которых может быть получено из предшественника путем нескольких операций переноса поддеревьев [6]. Вычисление расстояния переноса поддеревьев с линейной стоимостью полезно при реконструкции такого списка деревьев на базе подхода с максимальной экономичностью [5,6].