document: Gossip is synteny : Incomplete gossip and the syntenic distance between genomes The syntenic distance between two genomes is given by the minimum number of fusions , fissions , and translocations required to transform one into the other , ignoring the order of genes within chromosomes . Computing this distance is NP-hard . In the present work , we give a tight connection between syntenic distance and the incomplete gossip problem , a novel generalization of the classical gossip problem . In this problem , there are n gossipers , each with a unique piece of initial information ; they communicate by phone calls in which the two participants exchange all their information . The goal is to minimize the total number of phone calls necessary to inform each gossiper of his set of relevant gossip which he desires to learn . As an application of the connection between syntenic distance and incomplete gossip , we derive an O -LRB- 2/sup O -LRB- n log n -RRB- / -RRB- algorithm to exactly compute the syntenic distance between two genomes with at most n chromosomes each . Our algorithm requires O -LRB- n/sup 2 / +2 / sup O -LRB- d log d -RRB- / -RRB- time when this distance is d , improving the O -LRB- n/sup 2 / +2 -LRB- O -LRB- d / / sup 2 / -RRB- -RRB- -RRB- running time of the best previous exact algorithm
doc_bio_tags: O O O O O O O O B I O B O B I O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O B I O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O B I O O B O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O