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