This paper examines some of the rich structure of the syntenic
distance model of evolutionary distance, introduced by Ferretti,
Nadeau, and Sankoff. The syntenic distance between two genomes is the
minimum number of fissions, fusions, and translocations required to
transform one into the other, ignoring gene order within chromosomes.
We prove that the previously unanalyzed algorithm given by Ferretti et
al. is a 2-approximation and no better, and that, further, it always
outperforms the algorithm presented by DasGupta, Jiang, Kannan, Li,
and Sweedyk. We also prove the same results for an improved version
of the Ferretti et al. algorithm.
We then prove a number of properties which give insight into the
structure of optimal move sequences. We give instances in which any
move sequence working solely within connected components is nearly
twice optimal, and a general lower bound based on the spread of genes
from each chromosome. We then prove a monotonicity property for the
syntenic distance, and bound the difficulty of the hardest instance of
any size. We discuss the results of implementing these algorithms and
testing them on real and simulated synteny data.