An Introduction to Phylogenetics and Its Molecular Aspects - Bioinformatics: A Swiss Perspective - page 314

From a topological point of view, the root of the tree can be
regarded as an additional leaf. Thus, the number of rooted tree topolo-
gies B r is given by

s + 1

'

Bs () = ( 25 t - )

r

t = 3

s

'

= (( 215 t + ) - )

t = 2

s

( 23 s - )!

'

.

= (( 23 t - ) =

s - 2

2 ( s - 2 )!

(2)

t = 2

This is the same as the simple multiplication of odd numbers shown
in Table 1. It is quite clear that performing an exhaustive search of all
possible tree topologies for a dataset containing more than 12 to 13
leaves is not a realistic approach, even with modern computers.

4.5.2. The branch-and-bound algorithm

A clever algorithm called branch-and-bound is able to reduce the search
space and still guarantee that the globally best tree will be found. This is
done simply by abandoning any tree-building avenue where the current

Table 1. Multiplication of odd numbers.

s B ( s )|| B r ( t ) t

31 = 12

41 × 3 = 33

51 × 3 × 5 = 15 4

61 × 3 × 5 × 7 = 105 5

71 × 3 × 5 × 7 × 9 = 945 6

81 × 3 × 5 × 7 × 9 × 11 = 10 395 7

91 × 3 × 5 × 7 × 9 × 11 × 13 = 135 135 8

10 1 × 3 × 5 × 7 × 9 × 11 × 13 × 15 = 2 027 025 9

11 1 × 3 × 5 × 7 × 9 × 11 × 13 × 15 × 17 = 34 459 425 10

12 1 × 3 × 5 × 7 × 9 × 11 × 13 × 15 × 17 × 19 = 654 729 075 11

13 1 × 3 × 5 × 7 × 9 × 11 × 13 × 15 × 17 × 19 × 21 = 13 749 310 575 12

…… = ……