The Helix research group
Research themes
Work in progress and results
Software and databases
News from Helix
Home page
Site map Mail to Helix
Further thoughts on the syntenic distance between genomes
Algorithmica, 34 :157-180, 2002
N. Pisanti, M.-F. Sagot

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 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).

    Top of page   Home page  Prepare to print