A genome G1 can be modeled as follows: G1={S1,S2 ... Sm}, where each Si is a chromosome, that is a set of genes taken in the set {g1,g2 ... gN}.
The syntenic distance between two genomes G1 and G2 is defined as the minimum number of operations necessary to go from one genome to the other, where the 3 possible operations which are considered here are:
This model was defined by Ferretti, Nadeau and Sankoff in 1996.
It has been shown that the greatest distance existing between two genomes with (respectively) m and n chromosomes is equal to m+n-4.
In this talk, we follow this line of study by answering an open question from Kleinberg and Liben-Nowell: a full characterization of the genomes that lie at maximal syntenic distance (that is, m+n-4).
This result uses, among others, a property showing the equivalence between a translocation and another well-known problem coming from the interconnection networks area : the "gossiping" problem.
