Further thoughts on the syntenic distance between genomes

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 [1] 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 In -3 but 2n -4 (an independent and different proof of this was provided by Kleinberg and Liben-Nowell in [2]). 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 [3] nested synteny, exact and linear (this last one is the case addressed in [3]). • 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 [3].