WikiDer > Метрика Робинсона – Фулдса

Эта статья был номинирован на проверку на предмет его нейтралитет. Обсуждение данной номинации можно найти на страница обсуждения. (Сентябрь 2020) (Узнайте, как и когда удалить этот шаблон сообщения)

В Робинсон – Фулдс или же симметричная разностная метрика, часто сокращенно RF расстояние, это простой способ рассчитать расстояние между филогенетические деревья.^[1] Он определяется как (А + B) куда А количество разделов данных, подразумеваемых первым деревом, но не вторым деревом и B) - количество разделов данных, подразумеваемых вторым деревом, но не первым деревом (хотя некоторые программные реализации делят метрику RF на 2^[2] и другие масштабируют расстояние RF, чтобы иметь максимальное значение 1). Разделы рассчитываются для каждого дерева путем удаления каждой ветви. Таким образом, количество подходящих разделов для каждого дерева равно количеству ветвей в этом дереве. Радиочастотные расстояния критиковались как предвзятые,^[3] но они представляют собой относительно интуитивную меру расстояний между филогенетическими деревьями и поэтому остаются широко используемыми (оригинальная статья 1981 г., описывающая расстояния Робинсона-Фулдса^[1] был процитирован более 200 раз в 2019 году на основе Google ученый). Тем не менее, смещения, присущие радиочастотным расстояниям, предполагают, что исследователям следует рассмотреть возможность использования «обобщенных» метрик Робинсона – Фулдса.^[4] это может иметь лучшие теоретические и практические характеристики и избежать предвзятости и вводящих в заблуждение атрибутов исходной метрики.

Объяснение

Учитывая два некорневых дерева узлов и набор меток (т.е. таксоны) для каждого узла (который может быть пустым, но только узлы со степенью больше или равной трем могут быть помечены пустым набором) метрика Робинсона – Фулдса находит количество ${displaystyle alpha}$ и ${displaystyle alpha ^ {- 1}}$ операции для преобразования одного в другое. Количество операций определяет их расстояние. Деревья с корнем можно исследовать, присвоив листу-узлу метку.

Авторы определяют два дерева как одинаковые, если они изоморфны и изоморфизм сохраняет разметку. Построение доказательства основано на функции, называемой ${displaystyle alpha}$, который сжимает ребро (объединяя узлы, создавая объединение их наборов). Наоборот, ${displaystyle alpha ^ {- 1}}$ расширяет край (деконтракция), при этом набор можно разделить любым способом.

В ${displaystyle alpha}$ функция удаляет все ребра из ${displaystyle T_ {1}}$ что не в ${displaystyle T_ {2}}$, создавая ${displaystyle T_ {1} клин T_ {2}}$, а потом ${displaystyle alpha ^ {- 1}}$ используется для добавления краев, обнаруженных только в ${displaystyle T_ {2}}$ к дереву ${displaystyle T_ {1} клин T_ {2}}$ строить ${displaystyle T_ {2}}$. Количество операций в каждой из этих процедур эквивалентно количеству ребер в ${displaystyle T_ {1}}$ что не в ${displaystyle T_ {2}}$ плюс количество ребер в ${displaystyle T_ {2}}$ что не в ${displaystyle T_ {1}}$. Сумма операций эквивалентна преобразованию из ${displaystyle T_ {1}}$ к ${displaystyle T_ {2}}$, или наоборот.

Характеристики

Радиочастотное расстояние соответствует эквивалентной метрике сходства, которая отражает разрешение строгого консенсуса двух деревьев, впервые использованного для сравнения деревьев в 1980 году.^[5]

В своей статье 1981 г.^[1] Робинсон и Фулдс доказали, что расстояние на самом деле метрика.

Алгоритмы вычисления метрики

В 1985 году Дэй дал алгоритм, основанный на идеальном хешировании, который вычисляет это расстояние, имеющее только линейную сложность в количестве узлов в деревьях. Было показано, что рандомизированный алгоритм, который использует хеш-таблицы, которые не обязательно идеальны, аппроксимирует расстояние Робинсона-Фулдса с ограниченной ошибкой в ​​сублинейном времени.

Конкретные приложения

В филогенетика, метрика часто используется для вычисления расстояния между двумя деревьями. Программа Treedist в ФИЛИП Suite предлагает эту функцию, как и RAxML_standard пакет, DendroPy Библиотека Python (под названием «метрика симметричной разности») и пакеты R TreeDist (Функция `RobinsonFoulds ()`) и фангорн (функция `treedist ()`). Для сравнения групп деревьев самые быстрые реализации включают HashRF и MrsRF.

Метрика Робинсона – Фулдса также была используется в количественной сравнительной лингвистике для вычисления расстояний между деревьями, которые представляют, как языки связаны друг с другом.

Сильные и слабые стороны

Показатель RF по-прежнему широко используется, поскольку идея использования количества разделений, которые различаются между парой деревьев, является относительно интуитивным способом оценки различий между деревьями для многих систематиков. Это основная сила радиочастотного расстояния и причина его постоянного использования в филогенетике. Конечно, количество расщеплений, которые различаются между парой деревьев, зависит от количества таксонов в деревьях, поэтому можно утверждать, что эта единица не имеет смысла. Однако нормировать радиочастотные расстояния несложно, поэтому они находятся в диапазоне от нуля до единицы.

Однако метрика RF также страдает рядом теоретических и практических недостатков:^[6][7]

• По сравнению с другими показателями не имеет чувствительности и, следовательно, неточен; он может принимать на два различных значения меньше, чем таксонов в дереве.^[6][7]
• Быстро насыщается; очень похожим деревьям может быть присвоено максимальное значение расстояния.^[6]
• Его значение может показаться нелогичным. Одним из примеров является то, что перемещение наконечника и его соседа в определенную точку на дереве создает ниже значение разницы, чем если бы только один из двух наконечников был перемещен в то же место.^[6]
• Его диапазон значений может зависеть от формы дерева: деревья, содержащие много неровных разделов, будут иметь относительно меньшие расстояния в среднем, чем деревья с большим количеством четных разделов.^[6]
• На практике он работает хуже, чем многие альтернативные меры, основанные на моделировании деревьев.^[7]

Еще одна проблема, которую следует учитывать при использовании радиочастотных расстояний, заключается в том, что различия в одной кладе могут быть тривиальными (возможно, если клада по-разному разделяет три вида в пределах рода) или могут быть фундаментальными (если клада находится глубоко в дереве и определяет две фундаментальные подгруппы, например как млекопитающие и птицы). Однако эта проблема не является проблемой радиочастотных расстояний как таковых, это более общая критика расстояний между деревьями. Независимо от поведения любого конкретного расстояния между деревьями, практикующий биолог-эволюционист может рассматривать некоторые перестановки деревьев как «важные», а другие перестановки как «тривиальные». Расстояние между деревьями - это инструменты; они наиболее полезны в контексте другой информации об организмах на деревьях.

Эти проблемы можно решить, используя менее консервативные показатели. «Обобщенные радиочастотные расстояния» распознают сходство между похожими, но неидентичными разбиениями; исходное расстояние Робинсона-Фулдса не заботит, насколько похожи две группы, если они не идентичны, они отбрасываются.^[4]

Наиболее эффективные обобщенные расстояния Робинсона-Фулдса имеют основу в теории информации и измеряют расстояние между деревьями с точки зрения количества информации, которую разделяют деревья (измеряется в битах).^[7] Информационное расстояние кластеризации (реализовано в пакете R TreeDist) рекомендуется как наиболее подходящая альтернатива расстоянию Робинсона-Фулдса.^[7]

Альтернативный подход к вычислению расстояния между деревьями - использование квартетов, а не разбиений, в качестве основы для сравнения деревьев.^[6]

Программные реализации

Рекомендации

дальнейшее чтение

• M. Bourque, Arbres de Steiner et Reseaux не уверены, что это переменная локализации. Докторская диссертация, Монреальский университет, Монреаль, Квебек, 1978 г. http://www.worldcat.org/title/arbres-de-steiner-et-reseaux-dont-certains-sommets-sont-a-localisation-variable/oclc/053538946
• Робинсон, Д. Р .; Фулдс, Л. Р. (1981). «Сравнение филогенетических деревьев». Математические биологические науки. 53 (1–2): 131–147. Дои:10.1016/0025-5564(81)90043-2.
• Уильям Х. Э. Дэй, "Оптимальные алгоритмы сравнения деревьев с помеченными листьями", Журнал классификации, Номер 1, декабрь 1985 г. Дои:10.1007 / BF01908061
• Макаренков В. и Леклерк Б. Сравнение аддитивных деревьев с использованием круговых порядков, Журнал вычислительной биологии, 7,5,731-744,2000, "Мэри Энн Либерт, Inc."
• Pattengale, Nicholas D .; Готтлиб, Эрик Дж .; Морет, Бернард М.Э. (2007). «Эффективное вычисление метрики Робинсона – Фулдса». Журнал вычислительной биологии. 14 (6): 724–735. CiteSeerX 10.1.1.75.3338. Дои:10.1089 / cmb.2007.R012. PMID 17691890.
• Sukumaran, J .; Холдер, Марк Т. (2010). «DendroPy: библиотека Python для филогенетических вычислений». Биоинформатика. 26 (12): 1569–1571. Дои:10.1093 / биоинформатика / btq228. PMID 20421198.