1
$\begingroup$

If I am not mistaken, a tree is any graph that does not contain cycles.

However, I am currently taking a bioinformatics course where we deal a lot with algorithms on phylogenetic trees. Usually you are given a phylogenetic tree with $n$ leafs, and then you run some algorithm that can do something trivial like simple traversing of the tree, and then you get a $O(n)$ time bound, without saying anything about the number of internal nodes.

However given a regular tree with $n$ leafs, the total number of internal nodes can be infinite.

For example the following is a tree with one leaf (two if you consider it to be rooted) and infinite number of internal nodes:

enter image description here

So what are phylogenetic trees that you can express the running time of various algorithms in terms of the number of leafs, even though your algorithm actually traverses the entire phylogenetic tree?

$\endgroup$
  • $\begingroup$ I don't know that there's a difference with a name, beyond that phylogenetic trees are rooted. The term comes from outside of CS and describes the semantics, mostly, not the class of trees. (afaik) $\endgroup$ – Raphael Nov 11 '15 at 14:20
  • $\begingroup$ but rooted trees with $n$ leafs can also have infinite amount of internal nodes right? So what exactly makes phylogenetic trees not have that problem? $\endgroup$ – ksm001 Nov 11 '15 at 14:27
  • 1
    $\begingroup$ No, they can not. Arbitrary, but not infinite. Anyway, you have not talked about the representation of the tree you use; it's easy to conceive such that enable you to traverse all the children without visiting the inner nodes. However, I guess that all inner nodes in a phylogenetic tree have at least two children (otherwise, there'd be no sense in having these nodes, right?) and then there are fewer inner nodes than leaves. $\endgroup$ – Raphael Nov 11 '15 at 15:06
  • $\begingroup$ Trees also have to be connected, by the way. $\endgroup$ – Yuval Filmus Nov 11 '15 at 17:42
3
$\begingroup$

Phylogenetic trees are usually "full binary trees", that is rooted trees in which every internal node has exactly two children. A full binary tree having $n$ leaves has exactly $2n-1$ nodes.

$\endgroup$
  • 1
    $\begingroup$ In a phylogenetic tree or evolutionary tree, the internal nodes are usually inferred ancestors, and therefore they have at least two children. That is the reason we can use the number of leaves as the problem size. $\endgroup$ – Bangye Nov 11 '15 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.