Sampling Gene Adjacencies and Geodesic Points of Random Genomes

The breakpoint distance employed in comparative genomics is not a geodesic distance, which makes it difficult to study genomes (i.e. permutations) that are intermediate between two given genomes G and \(G'\) . An intermediate genome, also called a geodesic point, is a genome whose sum of breakpoint distances to G and \(G'\) is equal to the breakpoint distance of G and \(G'\) . To construct an intermediate genome M, it is necessary to find sets of gene adjacencies I and J selected from G and \(G'\) whose union forms M. This means that the set of adjacencies of M is \(I\cup J\) . Any given set of adjacencies I selected from G may put some constraints on some adjacencies of \(G'\) so that they cannot be used in J to construct M or if they can, they must be used in specific ways. For instance, a gene adjacency of \(G'\) whose gene extremities are used in the “middle” of segments of I cannot be used to construct M. Based on these constraints, we classify the set of all adjacencies of \(G'\) with respect to I into four distinct groups. For two unichromosomal random genomes of the same gene-content, namely \(\xi _1\) and \(\xi _2\) , as the number of genes tends to infinity, we study the limiting behaviour of the frequencies of adjacencies of each type in \(\xi _2\) with respect to a random or deterministic set of adjacencies selected from \(\xi _1\) . We use the limiting results to provide necessary conditions for the size and the shape of the set of adjacencies selected from the first genome for the purpose of constructing an intermediate genome between \(\xi _1\) and \(\xi _2\) . These results can help to shed light on how to construct “accessible breakpoint medians” far from the input genomes (corners).