  The problem of comparing trees representing the evolutionary histories of
cancerous tumors has turned out to be crucial, since there is a variety of
different methods which typically infer multiple possible trees. A departure
from the widely studied setting of classical phylogenetics, where trees are
leaf-labelled, tumoral trees are fully labelled, i.e., \emph{every} vertex has
a label.
  In this paper we provide a rearrangement distance measure between two
fully-labelled trees. This notion originates from two operations: one which
modifies the topology of the tree, the other which permutes the labels of the
vertices, hence leaving the topology unaffected. While we show that the
distance between two trees in terms of each such operation alone can be decided
in polynomial time, the more general notion of distance when both operations
are allowed is NP-hard to decide. Despite this result, we show that it is
fixed-parameter tractable, and we give a 4-approximation algorithm when one of
the trees is binary.
