Квартетная дистанция

Квартетная дистанция ^{[ 1 ]} это способ измерения расстояния между двумя филогенетическими деревьями . Оно определяется как количество подмножеств из четырех листьев, которые не связаны одной и той же топологией в обоих деревьях.

Вычисление квартетного расстояния

Самый простой расчет квартетного расстояния потребует $O(N^{4})$ время, где $N$ это количество листьев на деревьях.

Для бинарных деревьев были найдены лучшие алгоритмы вычисления расстояния в

$O(N^{2})$ время ^{[ 2 ]}
$O(N\log ^{2}N)$ время ^{[ 3 ]}

и

$O(N\log N)$ время ^{[ 4 ]}

Герт Столтинг Бродал и др. нашел алгоритм, который принимает $O(DN\log N)$ время вычислить квартетное расстояние между двумя разветвляющимися деревьями, когда $D$ - максимальная степень деревьев, ^{[ 5 ]} который доступен в C, Perl и R пакете Quartet .

Ссылки

^ Эстабрук, Джордж Ф.; МакМоррис, Франция; Мичем, Кристофер А. (1985). «Сравнение ненаправленных филогенетических деревьев на основе поддеревьев четырех эволюционных единиц». Систематическая зоология . 34 (2): 193–200. дои : 10.2307/2413326 . JSTOR 2413326 .
^ Брайант, Д.; Дж. Цанг; Ч.Е. Кирни; М. Ли. (11 января 2000 г.). «Вычисление квартетного расстояния между эволюционными деревьями» . Материалы одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Нью-Йорк : ACM Press: 285–286.
^ Бродал, Герт Стоелтинг; Фагерберг, Рольф; Педерсен, Кристиан Н.С. (2001). «Вычисление квартетного расстояния между эволюционными деревьями во времени» $O(n\log ^{2}n)$ ". Алгоритмы и вычисления . Конспекты лекций по информатике. Том 2223. С. 731–742. doi : 10.1007/3-540-45678-3_62 . ISBN 978-3-540-42985-2 .
^ Бродал, Герт Столтинг ; Рольф Фагерберг; Кристиан Норгаард Сторм Педерсен (2003). «Вычисление квартетного расстояния между эволюционными деревьями во времени» $O(n\log n)$ ". Algorithmica . 38 (2): 377–395. doi : 10.1007/s00453-003-1065-y . S2CID 6911940 .
^ Бродал, Герт Столтинг ; Рольф Фагерберг; Т. Майлунд; Кристиан Норгаард Сторм Педерсен; Песок (2013). «Эффективные алгоритмы вычисления тройного и квартетного расстояния между деревьями произвольной степени» (PDF) . Материалы двадцать четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . СИАМ: 1814–1832 гг. дои : 10.1137/1.9781611973105.130 . ISBN 978-1-61197-251-1 .

[eastbrook1985-1] Эстабрук, Джордж Ф.; МакМоррис, Франция; Мичем, Кристофер А. (1985). «Сравнение ненаправленных филогенетических деревьев на основе поддеревьев четырех эволюционных единиц». Систематическая зоология . 34 (2): 193–200. дои : 10.2307/2413326 . JSTOR 2413326 .

[2] Брайант, Д.; Дж. Цанг; Ч.Е. Кирни; М. Ли. (11 января 2000 г.). «Вычисление квартетного расстояния между эволюционными деревьями» . Материалы одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Нью-Йорк : ACM Press: 285–286.

[3] Бродал, Герт Стоелтинг; Фагерберг, Рольф; Педерсен, Кристиан Н.С. (2001). «Вычисление квартетного расстояния между эволюционными деревьями во времени» $O(n\log ^{2}n)$ ". Алгоритмы и вычисления . Конспекты лекций по информатике. Том 2223. С. 731–742. doi : 10.1007/3-540-45678-3_62 . ISBN 978-3-540-42985-2 .

[4] Бродал, Герт Столтинг ; Рольф Фагерберг; Кристиан Норгаард Сторм Педерсен (2003). «Вычисление квартетного расстояния между эволюционными деревьями во времени» $O(n\log n)$ ". Algorithmica . 38 (2): 377–395. doi : 10.1007/s00453-003-1065-y . S2CID 6911940 .

[5] Бродал, Герт Столтинг ; Рольф Фагерберг; Т. Майлунд; Кристиан Норгаард Сторм Педерсен; Песок (2013). «Эффективные алгоритмы вычисления тройного и квартетного расстояния между деревьями произвольной степени» (PDF) . Материалы двадцать четвертого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . СИАМ: 1814–1832 гг. дои : 10.1137/1.9781611973105.130 . ISBN 978-1-61197-251-1 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]