Further thoughts on the syntenic distance between genomes

Nadia Pisanti and Marie-France Sagot
Algorithmica, 34:157-180, 2002

• 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 2n-3 but 2n-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).