Abstract
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 \(\lceil d(A, B)/2 \rceil \). 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.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsReferences
Chindelevitch, L., Zanetti, J.P.P., Meidanis, J.: On the rank-distance median of 3 permutations. BMC Bioinform. 19(Suppl 6), 142 (2018). https://doi.org/10.1186/s12859-018-2131-4
Cunha, L.F.I., Feijão, P., dos Santos, V.F., Kowada, L.A., de Figueiredo, C.M.H.: On the computational complexity of closest genome problems. Discret. Appl. Math. 274, 26–34 (2020)
Feijão, P.: Reconstruction of ancestral gene orders using intermediate genomes. BMC Bioinform. 16(Suppl 14), S3 (2015). https://doi.org/10.1186/1471-2105-16-S14-S3
Feijão, P., Meidanis, J.: SCJ: a breakpoint-like distance that simplifies several rearrangement problems. Trans. Comput. Biol. Bioinform. 8, 1318–1329 (2011)
Gabidulin, E.M.: Theory of codes with maximum rank distance. Probl. Peredachi Inf. 21(1), 3–16 (1985)
Meidanis, J., Biller, P., Zanetti, J.P.P.: A matrix-based theory for genome rearrangements. Technical Report, IC-18-10. Institute of Computing, University of Campinas, August 2018
Popov, V.: Multiple genome rearrangement by swaps and by element duplications. Theor. Comput. Sci. 385(1–3), 115–126 (2007)
Tannier, E., Zheng, C., Sankoff, D.: Multichromosomal median and halving problems under different genomic distances. BMC Bioinform. 10(1), 120 (2009). https://doi.org/10.1186/1471-2105-10-120
Zanetti, J.P.P., Biller, P., Meidanis, J.: Median approximations for genomes modeled as matrices. Bull. Math. Biol. 78(4), 786–814 (2016). A preliminary version appeared on the Proceedings of the Workshop on Algorithms for Bioinformatics (WABI) 2013
Acknowledgements
We thank funding agency FAPESP (Brazil) for financial support (Grant numbers 2012/13865-7, 2012/14104-0, and 2018/00031-7). PB would also like to acknowledge the Canada 150 Research Chair program.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Biller, P., Zanetti, J.P.P., Meidanis, J. (2020). Center Genome with Respect to the Rank Distance. In: Setubal, J.C., Silva, W.M. (eds) Advances in Bioinformatics and Computational Biology. BSB 2020. Lecture Notes in Computer Science(), vol 12558. Springer, Cham. https://doi.org/10.1007/978-3-030-65775-8_13
Download citation
DOI: https://doi.org/10.1007/978-3-030-65775-8_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-65774-1
Online ISBN: 978-3-030-65775-8
eBook Packages: Computer ScienceComputer Science (R0)