Метрика Робинсона – Фулдса - Robinson–Foulds metric

В Робинсон – Фулдс или же симметричная разностная метрика, часто сокращенно 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]

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

Язык / Программа	Функция	Примечания
р	`dist.dendlist (список dendlist (x, y))` от dendextend	Видеть [1]
р	`Робинзон Фулдс (x, y)` из TreeDist	Быстрее, чем реализация phangorn; видеть [2]
Python	`tree_1.robinson_foulds (tree_2)` из ete3	Видеть [3]

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

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.

[:0-1] а ^б ^c Робинсон, Д.Ф .; Фулдс, Л. (Февраль 1981 г.). «Сравнение филогенетических деревьев». Математические биологические науки. 53 (1–2): 131–147. Дои:10.1016/0025-5564(81)90043-2.

[2] Kuhner, Мэри К .; Ямато, Джон (01.03.2015). «Практическая эффективность показателей сравнения деревьев». Систематическая биология. 64 (2): 205–214. Дои:10.1093 / sysbio / syu085. ISSN 1076-836X.

[3] Ю. Лин, В. Раджан, Б.М. MoretA метрика для филогенетических деревьев, основанная на сопоставлении IEEE / ACM Trans. Comput. Биол. Биоинформ., 9 (4) (2012), стр. 1014-1022

[:1-4] а ^б * Бёкер С., Канзар С., Клау Г.В. 2013. Обобщенная метрика Робинсона-Фулдса. В: Дарлинг А., Стоу Дж., Редакторы. Алгоритмы в биоинформатике. WABI 2013. Конспект лекций по информатике, том 8126. Берлин, Гейдельберг: Springer. п. 156–169.
Богданович Д., Джаро К. 2012. Соответствие расщепленного расстояния для неукорененных бинарных филогенетических деревьев. IEEE / ACM Trans. Comput. Биол. Биоинформа. 9: 150–160.
Богданович Д., Джаро К. 2013. О соответствии расстояния между корневыми филогенетическими деревьями. Int. J. Appl. Математика. Comput. Sci. 23: 669–684.
Най Т.М.В., Лио П., Гилкс В.Р. 2006. Новый алгоритм и веб-инструмент для сравнения двух альтернативных филогенетических деревьев. Биоинформатика. 22: 117–119.

[5] Богданович Д., Джаро К. 2012. Соответствие расщепленного расстояния для неукорененных бинарных филогенетических деревьев. IEEE / ACM Trans. Comput. Биол. Биоинформа. 9: 150–160.

[6] Богданович Д., Джаро К. 2013. О соответствии расстояния между корневыми филогенетическими деревьями. Int. J. Appl. Математика. Comput. Sci. 23: 669–684.

[7] Най Т.М.В., Лио П., Гилкс В.Р. 2006. Новый алгоритм и веб-инструмент для сравнения двух альтернативных филогенетических деревьев. Биоинформатика. 22: 117–119.

[5] Schuh, R. T. и Polhemus, J. T. (1980). «Анализ таксономического соответствия между наборами морфологических, экологических и биогеографических данных для Leptopodomorpha (Hemiptera)». Систематическая биология. 29 (1): 1–26. Дои:10.1093 / sysbio / 29.1.1. ISSN 1063-5157.

[Smith2019-6] а ^б ^c ^d ^е ^ж Смит, Мартин Р. (2019). «Байесовский и экономичный подходы позволяют реконструировать информационные деревья из смоделированных наборов морфологических данных» (PDF). Письма о биологии. 15 (2). 20180632. Дои:10.1098 / rsbl.2018.0632. ЧВК 6405459. PMID 30958126.

[Smith2020-7] а ^б ^c ^d ^е Смит, Мартин Р. (2020). «Теоретико-информационные обобщенные метрики Робинсона-Фулдса для сравнения филогенетических деревьев». Биоинформатика. Дои:10.1093 / биоинформатика / btaa614.

[1]

[2]

[3]

[4]

[5]

[6]

[7]