Center Genome with Respect to the Rank Distance

• Priscila Biller UNICAMP / Simon Fraser University, http://orcid.org/0000-0002-2937-5397
• João Paulo Pereira Zanetti Royal Netherlands Meteorological Institute http://orcid.org/0000-0002-9955-7751
• João Meidanis UNICAMP / Scylla Bioinformatics http://orcid.org/0000-0001-7878-4990

Resumo

The rank distance between matrices has been applied to genome evolution, specifically in the area of genome rearrangements. It corresponds to looking for the optimal way of transforming one genome into another by cuts and joins with weight 1 and double-swaps with weight 2. In this context, the genome median problem, which takes three genomes A, B, and C and aims to find a genome M such that d(A, M ) + d(B, M ) + d(C, M ) is minimized, is relevant. This problem can be stated for any genomic distance, not just the rank distance. In many cases, the genome median problem is NP-hard, but a number of approximate methods have been developed. Here we examine a related problem, the so-called center genome problem, where we aim to minimize the maximum (instead of the sum) of pairwise distances between the center genome and the inputs. We show that, for the rank distance, and for two genomic inputs A and B, it is not possible to always attain the well-known lower bound (cid:2)d(A, B)/2(cid:3). The issue arises when A and B are co-tailed genomes (i.e., genomes with the same telomeres) with d(A, B) equal to twice an odd number, when the optimal attainable score is 1 unit larger than the lower bound. In all other cases, we show that the lower bound is attained.

Palavras-chave: Genome rearrangements, Genome matrices