Maximum parsimony (MP) methods aim to reconstruct the phylogeny of extant species by finding the most parsimonious
evolutionary scenario using the species' genome data. MP methods are considered to be accurate, but they are also
computationally expensive especially for a large number of species. Several disk-covering methods (DCMs), which
decompose the input species to multiple overlapping subgroups (or disks), have been proposed to solve the problem in a
divide-and-conquer way. We design a new DCM based on the spectral method and also develop the COGNAC (Comparing
Orders of Genes using Novel Algorithms and high-performance Computers) software package. COGNAC uses the new DCM
to reduce the phylogenetic tree search space and selects an output tree from the reduced search space based on the MP
principle. We test the new DCM using gene order data and inversion distance. The new DCM not only reduces the number
of candidate tree topologies but also excludes erroneous tree topologies which can be selected by original MP methods.
Initial labeling of internal genomes affects the accuracy of MP methods using gene order data, and the new DCM enables
more accurate initial labeling as well. COGNAC demonstrates superior accuracy as a consequence. We compare COGNAC
with FastME and the combination of the state of the art DCM (Rec-I-DCM3) and GRAPPA . COGNAC clearly outperforms
FastME in accuracy. COGNAC –using the new DCM–also reconstructs a much more accurate tree in significantly shorter time
than GRAPPA with Rec-I-DCM3.