The construction of optimal evolutionary trees is a very
challenging problem, since most versions of the problem are NP
complete [1]. Even though the problem has been
studied extensively, evolutionary tree construction remains still
an open problem.

Definition 1.1
A treeT(S)=(V, E, S) is a binary, leaf labeled tree
with leafset
.

In our context, a treeT(S) associated with a set of sequences
is the tree
that corresponds to the evolutionary history of the sequences of
S. The internal nodes V represent (usually unknown) ancestor sequences. There are three major families of methods for
inferring phylogenies that basically use three different classes
of scoring functions: the parsimony and compatibility methods
[28,6,7,8], the distance
based methods [12,13,20,21,4],
and maximum likelihood methods
[9,11,30].