Introduction

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 tree T(S)=(V, E, S) is a binary, leaf labeled tree with leafset $S = \{s_1, .., s_n\}$.

In our context, a tree T(S) associated with a set of sequences $S = \{s_1, .., s_n\}$ 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].