Подсчет топологий филогенетических деревьев в R

Маленькие деревья

Для небольших деревьев (‹ ~20 листьев) можно использовать пакет TreeTools для преобразования каждого топология дерева к уникальному целому числу:

library('TreeTools')
library('phytools')
m <- do.call(c, lapply(1:1000, function(x) multi2di(starTree(c('a','b','c','d')))))

# Tabulate unique topologies
table(vapply64(m, as.TreeNumber, 1))

Вы можете построить каждую пронумерованную топологию, используя

topologyToPlot <- 2
plot(as.phylo(topologyToPlot, nTip = 4))

Большие деревья

Для более крупных деревьев вы можете убедиться, что деревья с эквивалентной топологией одинаково представлены в R:

• (при необходимости) обеспечение согласованности внутреннего представления подсказок деревьев с помощью m <- RenumberTips(m, m[[1]]).

• переупорядочивание внутренних ребер деревьев и нумерация узлов с использованием m <- Preorder(m).

Затем деревья можно сравнивать с помощью краевых матриц, как это предлагает user12728748.

Я не эксперт по этим деревьям, но здесь, возможно, вы могли бы отсортировать матрицы ребер, а затем подсчитать уникальные. Это работает в определенной степени для этого примера, но три симметричных случая, когда вы можете перевернуть дерево, по-прежнему учитываются отдельно (например, 8-й и 9-й, где ab и cd против cd и ab являются дочерними элементами одного узла). В приведенной ниже таблице результатов N будет количеством, а first будет первым вхождением этой топологии в m. Вы можете построить уникальные деревья с помощью for(i in res$first) plot(m[[i]]) и проверить эти симметричные случаи.

library(ape)
library(phytools)
#> Loading required package: maps
library(data.table)
set.seed(123)
m <- do.call(c, lapply(1:1000, function(x) multi2di(starTree(c('a','b','c','d')))))
edges <- data.table(do.call(rbind, lapply(m, function(x) unlist(data.table(x$edge, key=c("V1", "V2"))))))
res <- edges[,.(.N, first=head(.I, 1)), by = names(edges)]
res
#>     V11 V12 V13 V14 V15 V16 V21 V22 V23 V24 V25 V26  N first
#>  1:   5   5   6   6   7   7   2   6   1   7   3   4 53     1
#>  2:   5   5   6   6   7   7   4   6   2   7   1   3 65     2
#>  3:   5   5   6   6   7   7   4   6   3   7   1   2 60     3
#>  4:   5   5   6   6   7   7   2   6   4   7   1   3 56     4
#>  5:   5   5   6   6   7   7   6   7   1   4   2   3 63     5
#>  6:   5   5   6   6   7   7   6   7   2   3   1   4 55     6
#>  7:   5   5   6   6   7   7   1   6   3   7   2   4 66     7
#>  8:   5   5   6   6   7   7   6   7   3   4   1   2 55     8
#>  9:   5   5   6   6   7   7   6   7   1   2   3   4 40    15
#> 10:   5   5   6   6   7   7   6   7   1   3   2   4 66    16
#> 11:   5   5   6   6   7   7   3   6   2   7   1   4 52    20
#> 12:   5   5   6   6   7   7   1   6   4   7   2   3 46    24
#> 13:   5   5   6   6   7   7   3   6   1   7   2   4 44    27
#> 14:   5   5   6   6   7   7   1   6   2   7   3   4 54    28
#> 15:   5   5   6   6   7   7   2   6   3   7   1   4 60    29
#> 16:   5   5   6   6   7   7   4   6   1   7   2   3 53    32
#> 17:   5   5   6   6   7   7   6   7   2   4   1   3 63    39
#> 18:   5   5   6   6   7   7   3   6   4   7   1   2 49    43

^{Создана 26 июня 2020 г. с помощью пакета reprex (v0.3.0)}