Distance methods are well suited for constructing massive phylogenetic trees. However, the computational complexity for Rzhetsky and Neis minimum evolution (ME) approach, one of the earliest methods for constructing a phylogenetic tree from a distance matrix, remains open.