### Further thoughts on the syntenic
distance between genomes

####
**Nadia Pisanti and Marie-France Sagot**

*Algorithmica*, 34:157-180, 2002

The syntenic distance between two multi-chromosomal genomes is the
minimum number of fusion (union), fission (split) and translocation
(exchange) operations necessary to transform a genome into another.
Genomes are therefore seen as unlabeled bags of genes and the syntenic
distance as the number of moves needed to obtain the same bags. This
paper introduces the following new results concerning syntenic
distance:
- Using a direct proof, we solve a conjecture by Liben-Nowell
(1999) for the syntenic diameter size, that is, for the length of the
longest optimal move sequence for an instance of size
*n*,
showing that it is, in fact, not 2*n*-3 but 2*n*-4 (an
independent and different proof of this was provided by Kleinberg and
Liben-Nowell in (Kleinberg and Liben-Nowell, 2000). The structure of
the proof further enables us to characterize the minimum number of
translocations an optimal sequence of moves must have. This has
important consequences for algorithmical purposes. The result is then
generalized to what we call bidimensional syntenic diameter.
- When the initial instance has more than one component, we suggest
a way of performing inter-component moves, something that was not done
in previous algorithms. We show however that, even in simple cases
with more than two components involved, an optimal solution for a
general instance of the problem using such moves is NP-hard to obtain.
- We introduce, we believe, a simpler, more general and efficient
algorithm for obtaining a move sequence that is optimal for the cases
that Liben-Nowell and Kleinberg called in (Liben-Nowell, 2000) nested
synteny, exact and linear (this last one is the case addressed in
Liben-Nowell, 2000).
- We sketch an extension of the algorithm which we conjecture may
optimally solve the connected nested synteny (without requiring
linearity).
- We prove an inclusion theorem for the general synteny that is an
extension of the one shown for linear synteny in (Liben-Nowell, 2000).

**key words:** Genome rearrangement, genome distance, syntenic
distance, nested synteny, syntenic diameter, discrete algorithms,
computational biology

Paper in postscript format

Back to the *Publications* page