GATE 2023 BT – Question 51

Recombinant DNA Technology and Other Tools in Biotechnology · Computational tools: Bioinformatics resources, databases, sequence analysis, alignment and phylogeny · 2 marks · Numerical answer

If there are three unrooted trees for four protein sequences, the number of rooted trees for the same number of sequences is ___________.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 15

Explanation

**Counting trees.** For $n=4$ sequences:
- the number of unrooted binary trees is $(2n-5)!!=3$ (given in the question).

**Rooting a tree.** A root can be placed on any edge of an unrooted tree. An unrooted binary tree with $n$ leaves has $2n-3$ edges, so for $n=4$ it has $2(4)-3=5$ edges.

**Number of rooted trees:**
$$3\times5=\mathbf{15}.$$

(This agrees with the formula for rooted binary trees, $(2n-3)!!=5\times3\times1=15$.)