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

Здесь рассматриваются результаты, касающиеся связанных с преобразованиями расстояний для эволюционных деревьев. Такие деревья могут быть корневыми, если известно эволюционное происхождение, а также взвешенными, если известна продолжительность эволюции по каждому ребру. Реконструкция корректного эволюционного дерева для множества видов является одной из фундаментальных, и при этом весьма сложных, проблем эволюционной генетики. За последние десятилетия было разработано несколько подходов к реконструкции эволюционных деревьев, основанных на таких критериях, как максимальные экономичность, совместимость, расстояние и правдоподобие. Результаты применения этих подходов обычно зависят от объема данных и вычислительных ресурсов, использовавшихся в расчетах. В результате на практике из одних и тех же множеств видов нередко получаются разные эволюционные деревья [ ]. Таким образом, представляет интерес возможность сравнения эволюционных деревьев, полученных при помощи разных методов либо при помощи одного и того же метода, но на разных данных.

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