  Each gene has its own evolutionary history which can substantially differ
from the evolutionary histories of other genes. For example, some individual
genes or operons can be affected by specific horizontal gene transfer and
recombination events. Thus, the evolutionary history of each gene should be
represented by its own phylogenetic tree which may display different
evolutionary patterns from the species tree that accounts for the main patterns
of vertical descent. The output of traditional consensus tree or supertree
inference methods is a unique consensus tree or supertree. We describe a new
efficient method for inferring multiple alternative consensus trees and
supertrees to best represent the most important evolutionary patterns of a
given set of gene phylogenies. We show how an adapted version of the popular
k-means clustering algorithm, based on some interesting properties of the
Robinson and Foulds distance, can be used to partition a given set of trees
into one (for homogeneous data) or multiple (for heterogeneous data) cluster(s)
of trees. Moreover, we adapt the popular Cali\'nski-Harabasz, Silhouette, Ball
and Hall, and Gap cluster validity indices to tree clustering with k-means. A
special attention is given to the relevant but very challenging problem of
inferring alternative supertrees. The use of the Euclidean property of the
objective function of the method makes it faster than the existing tree
clustering techniques, and thus perfectly suitable for analyzing large
evolutionary datasets. We apply the new method to discover alternative
supertrees characterizing the main patterns of evolution of SARS-CoV-2 and
genetically related betacoronaviruses.
