This note describes the parallelization of a key biological applicatio
n, such as the construction of phylogenetic trees, using the DNAml pro
gram. A careful run-time analysis allowed us to propose an efficient p
arallelization that scaled very well to large problem sizes.