We present a new whole-genome based approach to infer large-scale phylogenies

that is alignment- and reference-free. In contrast to other methods, it does

not rely on pairwise comparisons to determine distances to infer edges in a

tree. Instead, a colored de-Bruijn graph is constructed, and information on

common subsequences is extracted to infer phylogenetic splits. Application to

different datasets confirms robustness of the approach. A comparison to other

state-of-the-art whole-genome based methods indicates comparable or higher

accuracy and efficiency.