Hi friends!
I'm studying about phylogenetic tree shapes. Most precisely about calculate all possible rooted bifurcatingtree shapes (not labeled). A book of Felsenstein named "Inferring Phylogenies" gives an algorithm to calculate that, but I don't understand how to.
The book provides a calculation as follows:
But my calculations does not match with following values table showed on the book.
can anybody help me with a step by step example??
•
written
by
tractnet •
1 answer
An R implementation would be as follows:
S <- NULL
for (n in 1:19) {
if (n == 1) {
S <- 1
} else if (n%%2 == 0) {
S <- c(S,
sum(S[seq_len((n/2)-1)] * S[(n-1):(n-((n/2)-1))]) +
S[n/2] * (S[(n/2)]+1)/2)
} else {
S <- c(S,
sum(S[seq_len((n-1)/2-1)] * S[(n-1):(n-((n-1)/2-1))]) +
S[(n-1)/2] * S[(n+1)/2])
}
}
print(S)
yielding
> print(results)
[1] 1 1 1 2 3 6 11 23 46 98 207 451 983 2179 4850 10905
[17] 24631 56011 127912
The key is that the summation Sn = S(1)*S(n-1) + S(2)*S(n-2) only continues to the ((n-1)/2 - 1)th term, after which the final term S((n-1)/2)*S((n+1)/2) is added (odd case). For instance, if n = 9, the
((n-1)/2 - 1)th term is S(3), and the summation would be S(1)*S(n-1) + S(2)*S(n-2) + S(3)*S(n-3) + S(4)*S((n+1)/2)
Log in to answer this question.
