Biology Reference
In-Depth Information
given that the heuristics used have actually found the best tree.
6
Indeed,
consecutive runs of the same tree reconstruction program on the same
data may yield quite different results. Also, care must be taken regarding
the duality between model improvement and tree reconstruction: often,
exactly the same datasets are used in both steps, making model overfit-
ting a potential problem.
Popular ML methods include PHYML,
10
Tree-Puzzle,
11
and
RAxML.
12,13
The most common software implementing Bayesian methods
is MrBayes.
14
More elaborate programs exist that can, for instance, perform
phylogenetic reconstruction and sequence alignment simultaneously.
15
Due to the complexity of computing the likelihood function, proba-
bilistic methods are generally slow, even slower than CMP methods.
4.5. Searching for an Optimal Tree in a Large,
Populated Space
Phylogenetic methods form a complex domain of research and develop-
ment with numerous technical problems such as preprocessing and post-
processing of the data, inferrence of the soundness of results (statistical
significance), etc. The scope of this introductory chapter only allows us
to mention some of the more classical ones.
Of the methods mentioned above, only simple clustering methods
and NJ give a tree structure directly. The remaining methods primarily
score a given tree and use some form of search algorithm to find the tree
with the best score. Several approaches are possible. The conceptually
simplest approach is to perform a brute-force search in which every con-
ceivable tree topology is tested. Unfortunately, this rapidly becomes
unfeasible as the number of taxons increases.
4.5.1. The number of possible phylogenetic trees
The search space of possible trees grows very quickly with the number
of terminal nodes. The number
B
of strictly bifurcating unrooted tree
topologies for
s
leaves can be calculated according to a simple formula
16,17
:
s
'
25
(
s
-
)!
.
Bs
()
=
(1)
s
-
4
2
(
s
-
4
)
t
-
3
