Квартет расстояние [1] представляет собой способ измерения расстояния между двумя филогенетических деревьев . Он определяется как количество подмножеств из четырех листьев, которые не связаны одной и той же топологией в обоих деревьях.
Расчет расстояния квартета
Самый простой расчет расстояния квартета потребует время, где количество листьев на деревьях.
Для бинарных деревьев были найдены лучшие алгоритмы для вычисления расстояния в
а также
- время [4]
Gerth Stølting Brodal et al. нашел алгоритм, который берет время вычислить квартетное расстояние между двумя многостворчатыми деревьями, когда это максимальная степень деревьев, [5] , который доступен в C, Perl, и R пакет квартет .
Рекомендации
- ^ Estabrook, Джордж Ф .; Макморрис, Франция; Мичем, Кристофер А. (1985). «Сравнение ненаправленных филогенетических деревьев на основе поддеревьев четырех эволюционных единиц». Систематическая зоология . 34 (2): 193–200. DOI : 10.2307 / 2413326 . JSTOR 2413326 .
- ^ Bryant, D .; Дж. Цанг; ЧП Кирни; М. Ли. (11 января 2000 г.). «Вычисление квартетного расстояния между эволюционными деревьями» . Материалы одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Нью-Йорк : ACM Press: 285–286.
- ^ Бродал, Герт Стёльтинг; Фагерберг, Рольф; Педерсен, Кристиан Н.С. (2001). "Вычисление квартета расстояния между эволюционными деревьями во времени..» Алгоритмы и вычислений . Лекции по информатике. 2223 С. 731-742... Дои : 10.1007 / 3-540-45678-3_62 . ISBN 978-3-540-42985-2.
- ^ Бродал, Герт Стёльтинг ; Рольф Фагерберг; Кристиан Нёргаард Сторм Педерсен (2003). "Вычисление квартета расстояния между эволюционными деревьями во времени.». Algorithmica . 38 (2): 377-395. DOI : 10.1007 / s00453-003-1065-у . S2CID 6911940 .
- ^ Бродал, Герт Стёльтинг ; Рольф Фагерберг; Т. Майлунд; Кристиан Нёргаард Сторм Педерсен; Песок (2013). «Эффективные алгоритмы вычисления триплетного и квартетного расстояния между деревьями произвольной степени» (PDF) . Материалы двадцать четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . SIAM: 1814–1832 гг. DOI : 10.1137 / 1.9781611973105.130 . ISBN 978-1-61197-251-1.