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

Метрика Робинсона -Фоулдса или метрика симметричной разницы , часто сокращенно называемая RF-расстоянием , представляет собой простой способ расчета расстояния между филогенетическими деревьями . ^{[ 1 ]}

Оно определяется как ( A + B ), где A — количество разделов данных, подразумеваемых первым деревом, но не вторым деревом, а B — количество разделов данных, подразумеваемых вторым деревом, но не первым деревом (хотя некоторые программные реализации делят метрику RF на 2 ^{[ 2 ]} и другие масштабируют РЧ-расстояние так, чтобы оно имело максимальное значение 1). Разделы рассчитываются для каждого дерева путем удаления каждой ветки. Таким образом, количество подходящих разделов для каждого дерева равно количеству ветвей в этом дереве.

РЧ-расстояния подвергались критике как предвзятые, ^{[ 3 ]} но они представляют собой относительно интуитивную меру расстояний между филогенетическими деревьями и поэтому по-прежнему широко используются (оригинальная статья 1981 года, описывающая расстояния Робинсона-Фулдса). ^{[ 1 ]} к 2023 году цитировалось более 2700 раз по данным Google Scholar, ). Тем не менее, предвзятости, присущие радиочастотным расстояниям, позволяют предположить, что исследователям следует рассмотреть возможность использования «обобщенных» метрик Робинсона – Фулдса. ^{[ 4 ]} это может иметь лучшие теоретические и практические характеристики и избежать предвзятости и вводящих в заблуждение атрибутов исходной метрики.

Объяснение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализации программного обеспечения

Язык/Программа	Функция	Примечания
Р	`dist.dendlist(dendlist(x,y))` из дендекстенда	См . [1]
Р	`RobinsonFoulds(x, y)` из TreeDist	Быстрее, чем реализация фангорна; см . [2]
Питон	`tree_1.robinson_foulds(tree_2)` от ете3	См . [3]
Юлия	`hardwiredClusterDistance(tree1, tree2, true)` от PhyloNetworks	См . [4]

Ссылки

^ Перейти обратно: ^а ^б ^с Робинсон, DF; Фулдс, Л.Р. (февраль 1981 г.). «Сравнение филогенетических деревьев» . Математические биологические науки . 53 (1–2): 131–147. дои : 10.1016/0025-5564(81)90043-2 .
^ Кунер, Мэри К.; Ямато, Джон (01 марта 2015 г.). «Практическая эффективность показателей сравнения деревьев» . Систематическая биология . 64 (2): 205–214. дои : 10.1093/sysbio/syu085 . ISSN 1076-836X . ПМИД 25378436 .
^ Ю. Лин, В. Раджан, Б. М. Морет Метрика для филогенетических деревьев, основанная на сопоставлении IEEE/ACM Trans. Вычислить. Биол. Биоинформ., 9 (4) (2012), стр. 1014-1022.
^ Перейти обратно: ^а ^б
*Бёккер С., Канзар С., Клау Г.В. 2013. Обобщенная метрика Робинсона-Фулдса. В: Дарлинг А., Стой Дж., редакторы. Алгоритмы в биоинформатике. WABI 2013. Конспекты лекций по информатике, том 8126. Берлин, Гейдельберг: Springer. п. 156–169.
- Богданович Д., Джаро К. 2012. Сопоставление расстояния разделения для некорневых бинарных филогенетических деревьев. IEEE/ACM Транс. Вычислить. Биол. Биоинформа. 9:150–160.
- Богданович Д., Джаро К. 2013. О расстоянии совпадения между корневыми филогенетическими деревьями. Межд. Дж. Прил. Математика. Вычислить. наук. 23:669–684.
- Най ТМВ, Лио П., Гилкс В.Р. 2006. Новый алгоритм и веб-инструмент для сравнения двух альтернативных филогенетических деревьев. Биоинформатика. 22:117–119.
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Смит, Мартин Р. (2020). «Теоретико-информационные обобщенные метрики Робинсона-Фулдса для сравнения филогенетических деревьев» (PDF) . Биоинформатика . 36 (20): 5007–5013. doi : 10.1093/биоинформатика/btaa614 . ПМИД 32619004 .
^ Шух, RT и Полхемус, JT (1980). «Анализ таксономического соответствия наборов морфологических, экологических и биогеографических данных Leptopodomorpha (Hemiptera)». Систематическая биология . 29 (1): 1–26. дои : 10.1093/sysbio/29.1.1 . ISSN 1063-5157 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Смит, Мартин Р. (2019). «Байесовский подход и подход экономии восстанавливают информативные деревья на основе смоделированных наборов морфологических данных» (PDF) . Письма по биологии . 15 (2). 20180632. дои : 10.1098/rsbl.2018.0632 . ПМК 6405459 . ПМИД 30958126 .

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

М. Бурк, Деревья и сети Штейнера, в которых отдельные вершины имеют переменное расположение. Докторская диссертация, Монреальский университет, Монреаль, Квебек, 1978 г. http://www.worldcat.org/title/arbres-de-steiner-et-reseaux-dont-certains-sommets-sont-a-localization-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, «Mary Ann Liebert, Inc.».
Паттенгейл, Николас Д.; Готлиб, Эрик Дж.; Море, Бернар М.Е. (2007). «Эффективное вычисление метрики Робинсона – Фолдса». Журнал вычислительной биологии . 14 (6): 724–735. CiteSeerX 10.1.1.75.3338 . дои : 10.1089/cmb.2007.R012 . ПМИД 17691890 .
Сукумаран, Дж.; Холдер, Марк Т. (2010). «DendroPy: библиотека Python для филогенетических вычислений» . Биоинформатика . 26 (12): 1569–1571. doi : 10.1093/биоинформатика/btq228 . ПМИД 20421198 .

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

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

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

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

Богданович Д., Джаро К. 2013. О расстоянии совпадения между корневыми филогенетическими деревьями. Межд. Дж. Прил. Математика. Вычислить. наук. 23:669–684.

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

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

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

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

[Smith2020-5] Перейти обратно: ^а ^б ^с ^д ^и ^ж Смит, Мартин Р. (2020). «Теоретико-информационные обобщенные метрики Робинсона-Фулдса для сравнения филогенетических деревьев» (PDF) . Биоинформатика . 36 (20): 5007–5013. doi : 10.1093/биоинформатика/btaa614 . ПМИД 32619004 .

[6] Шух, RT и Полхемус, JT (1980). «Анализ таксономического соответствия наборов морфологических, экологических и биогеографических данных Leptopodomorpha (Hemiptera)». Систематическая биология . 29 (1): 1–26. дои : 10.1093/sysbio/29.1.1 . ISSN 1063-5157 .

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]