{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T04:24:47Z","timestamp":1772166287520,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T00:00:00Z","timestamp":1588550400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T00:00:00Z","timestamp":1588550400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Natural Science and Engineering Research Council of Canada Discovery Grant","award":["RGPIN-2017-03986"],"award-info":[{"award-number":["RGPIN-2017-03986"]}]},{"name":"CIHR\/Genome Canada Bioinformatics and Computational Biology","award":["B\/CB 11106"],"award-info":[{"award-number":["B\/CB 11106"]}]},{"name":"CIHR\/Genome Canada Bioinformatics and Computational Biology","award":["B\/CB 11106"],"award-info":[{"award-number":["B\/CB 11106"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background.<\/jats:title>\n                    <jats:p>In the field of genome rearrangement algorithms, models accounting for gene duplication lead often to hard problems. For example, while computing the pairwise distance is tractable in most duplication-free models, the problem\u00a0is NP-complete for most extensions of these models accounting for duplicated genes. Moreover, problems involving more than two genomes, such as the genome median and the Small Parsimony problem, are intractable for most duplication-free models, with some exceptions, for example the Single-Cut-or-Join (SCJ) model.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results.<\/jats:title>\n                    <jats:p>We introduce a variant of the SCJ distance that accounts for duplicated genes, in the context of directed evolution from an ancestral genome to a descendant genome where orthology relations between ancestral genes and their descendant are known. Our model includes two duplication mechanisms: single-gene tandem duplication and the creation of single-gene circular chromosomes. We prove that in this model, computing the directed distance and a parsimonious evolutionary scenario in terms of SCJ and single-gene duplication events can be done in linear time. We also show that the directed median problem is tractable for this distance, while the rooted median problem, where we assume that one of the given genomes is ancestral to the median, is NP-complete. We also describe an Integer Linear Program for solving this problem. We evaluate the directed distance and rooted median algorithms on simulated data.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusion.<\/jats:title>\n                    <jats:p>Our results provide a simple genome rearrangement model, extending the SCJ model to account for single-gene duplications, for which we prove a mix of tractability and hardness results. For the NP-complete rooted median problem, we design a simple Integer Linear Program. Our publicly available implementation of these algorithms for the directed distance and median problems allow to solve efficiently these problems on large instances.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s13015-020-00169-y","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T02:02:19Z","timestamp":1588557739000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The distance and median problems in the single-cut-or-join model with single-gene duplications"],"prefix":"10.1186","volume":"15","author":[{"given":"Aniket C.","family":"Mane","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Lafond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pedro C.","family":"Feijao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cedric","family":"Chauve","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,5,4]]},"reference":[{"issue":"6217","key":"169_CR1","doi-asserted-by":"publisher","first-page":"1258522","DOI":"10.1126\/science.1258522","volume":"347","author":"D Neafsey","year":"2015","unstructured":"Neafsey D, Waterhouse R, Abai M, et al. Highly evolvable malaria vectors: the genomes of 16 Anopheles mosquitoes. Science. 2015;347(6217):1258522. https:\/\/doi.org\/10.1126\/science.1258522.","journal-title":"Science"},{"issue":"12","key":"169_CR2","doi-asserted-by":"publisher","first-page":"1435","DOI":"10.1038\/ng.3435","volume":"47","author":"R Ming","year":"2015","unstructured":"Ming R, VanBuren R, Wai CM, et al. The pineapple genome and the evolution of CAM photosynthesis. Nat Genet. 2015;47(12):1435\u201342. https:\/\/doi.org\/10.1038\/ng.3435.","journal-title":"Nat Genet"},{"key":"169_CR3","doi-asserted-by":"publisher","first-page":"207","DOI":"10.7551\/mitpress\/9780262062824.001.0001","volume-title":"Combinatorics of genome rearrangements. Computational molecular biology","author":"G Fertin","year":"2009","unstructured":"Fertin G, Labarre A, Rusu I, Tannier E, Vialette S. Combinatorics of genome rearrangements. Computational molecular biology. Cambridge: MIT Press; 2009. p. 207\u201320."},{"issue":"1","key":"169_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0129054196000026","volume":"7","author":"D Sankoff","year":"1996","unstructured":"Sankoff D, Sundaram G, Kececioglu JD. Steiner points in the space of genome rearrangements. Int J Found Comput Sci. 1996;7(1):1\u20139. https:\/\/doi.org\/10.1142\/S0129054196000026.","journal-title":"Int J Found Comput Sci"},{"key":"169_CR5","first-page":"25","volume":"8","author":"M Blanchette","year":"1997","unstructured":"Blanchette M, Bourque G, Sankoff D. Breakpoint phylogenies. Genome Inf. 1997;8:25\u201334.","journal-title":"Genome Inf"},{"key":"169_CR6","unstructured":"Pe\u2019er I, Shamir R. The median problems for breakpoints are np-complete. Technical Report TR98-071, electronic colloquium on computational complexity (ECCC) 1998. http:\/\/eccc.hpi-web.de\/eccc-reports\/1998\/TR98-071"},{"issue":"2","key":"169_CR7","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S1570-8667(03)00077-7","volume":"2","author":"D Bryant","year":"2004","unstructured":"Bryant D. A lower bound for the breakpoint phylogeny problem. J Discr Algorith. 2004;2(2):229\u201355. https:\/\/doi.org\/10.1016\/S1570-8667(03)00077-7.","journal-title":"J Discr Algorith"},{"key":"169_CR8","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1186\/1471-2105-10-120","volume":"10","author":"E Tannier","year":"2009","unstructured":"Tannier E, Zheng C, Sankoff D. Multichromosomal median and halving problems under different genomic distances. BMC Bioinf. 2009;10:120. https:\/\/doi.org\/10.1186\/1471-2105-10-120.","journal-title":"BMC Bioinf"},{"issue":"1","key":"169_CR9","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1137\/120866439","volume":"27","author":"SC Boyd","year":"2013","unstructured":"Boyd SC, Haghighi M. Mixed and circular multichromosomal genomic median problem. SIAM J Discrete Math. 2013;27(1):63\u201374. https:\/\/doi.org\/10.1137\/120866439.","journal-title":"SIAM J Discrete Math"},{"issue":"1","key":"169_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1089\/cmb.2013.0004","volume":"21","author":"J Kov\u00e1c","year":"2014","unstructured":"Kov\u00e1c J. On the complexity of rearrangement problems under the breakpoint distance. J Comput Biol. 2014;21(1):1\u201315. https:\/\/doi.org\/10.1089\/cmb.2013.0004.","journal-title":"J Comput Biol"},{"issue":"1","key":"169_CR11","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1186\/s13015-017-0106-z","volume":"12","author":"D Doerr","year":"2017","unstructured":"Doerr D, Balaban M, Feij\u00e3o P, Chauve C. The gene family-free median of three. Algorith Mol Biol. 2017;12(1):14. https:\/\/doi.org\/10.1186\/s13015-017-0106-z.","journal-title":"Algorith Mol Biol"},{"issue":"5","key":"169_CR12","doi-asserted-by":"publisher","first-page":"1318","DOI":"10.1109\/TCBB.2011.34","volume":"8","author":"P Feij\u00e3o","year":"2011","unstructured":"Feij\u00e3o P, Meidanis J. SCJ: A breakpoint-like distance that simplifies several rearrangement problems. IEEE\/ACM Trans Comput Biol Bioinf. 2011;8(5):1318\u201329. https:\/\/doi.org\/10.1109\/TCBB.2011.34.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"1","key":"169_CR13","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1186\/1745-6150-6-11","volume":"6","author":"A Levasseur","year":"2011","unstructured":"Levasseur A, Pontarotti P. The role of duplications in the evolution of genomes highlights the need for evolutionary-based approaches in comparative genomics. Biol Direct. 2011;6(1):11. https:\/\/doi.org\/10.1186\/1745-6150-6-11.","journal-title":"Biol Direct"},{"issue":"1749","key":"169_CR14","doi-asserted-by":"publisher","first-page":"5048","DOI":"10.1098\/rspb.2012.1108","volume":"279","author":"FA Kondrashov","year":"2012","unstructured":"Kondrashov FA. Gene duplication as a mechanism of genomic adaptation to a changing environment. Proc R Soc Lond B. 2012;279(1749):5048\u201357. https:\/\/doi.org\/10.1098\/rspb.2012.1108.","journal-title":"Proc R Soc Lond B"},{"issue":"5","key":"169_CR15","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1089\/cmb.2014.0096","volume":"22","author":"M Shao","year":"2015","unstructured":"Shao M, Lin Y, Moret BME. An exact algorithm to compute the double-cut-and-join distance for genomes with duplicate genes. J Comput Biol. 2015;22(5):425\u201335. https:\/\/doi.org\/10.1089\/cmb.2014.0096.","journal-title":"J Comput Biol"},{"issue":"6","key":"169_CR16","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1109\/TCBB.2012.144","volume":"10","author":"L Bulteau","year":"2013","unstructured":"Bulteau L, Jiang M. Inapproximability of (1,2)-exemplar distance. IEEE\/ACM Trans Comput Biol Bioinf. 2013;10(6):1384\u201390. https:\/\/doi.org\/10.1109\/TCBB.2012.144.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"1","key":"169_CR17","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/s13015-017-0095-y","volume":"12","author":"DP Rubert","year":"2017","unstructured":"Rubert DP, Feij\u00e3o P, Braga MDV, Stoye J, Martinez FHV. Approximating the DCJ distance of balanced genomes in linear time. Algorith Mol Biol. 2017;12(1):3. https:\/\/doi.org\/10.1186\/s13015-017-0095-y.","journal-title":"Algorith Mol Biol"},{"key":"169_CR18","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-94-011-4309-7_19","volume-title":"Comparative genomics: empirical and analytical approaches to gene order dynamics, map alignment and the evolution of gene families","author":"D Bryant","year":"2000","unstructured":"Bryant D. The complexity of calculating exemplar distances. In: Sankoff D, Nadeau JH, editors. Comparative genomics: empirical and analytical approaches to gene order dynamics, map alignment and the evolution of gene families. Dordrecht: Springer; 2000. p. 207\u201311. https:\/\/doi.org\/10.1007\/978-94-011-4309-7_19."},{"issue":"1","key":"169_CR19","doi-asserted-by":"publisher","first-page":"19","DOI":"10.7155\/jgaa.00175","volume":"13","author":"S Angibaud","year":"2009","unstructured":"Angibaud S, Fertin G, Rusu I, Th\u00e9venin A, Vialette S. On the approximability of comparing genomes with duplicates. J Graph Algorith Appl. 2009;13(1):19\u201353.","journal-title":"J Graph Algorith Appl"},{"issue":"2","key":"169_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1089\/cmb.2016.0045","volume":"24","author":"R Zeira","year":"2017","unstructured":"Zeira R, Shamir R. Sorting by cuts, joins, and whole chromosome duplications. J Comput Biol. 2017;24(2):127\u201337. https:\/\/doi.org\/10.1089\/cmb.2016.0045.","journal-title":"J Comput Biol"},{"key":"169_CR21","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/978-94-011-4309-7_46","volume-title":"Comparative genomics: empirical and analytical approaches to gene order dynamics, map alignment and the evolution of gene families","author":"D Sankoff","year":"2000","unstructured":"Sankoff D, El-Mabrouk N. Duplication, rearrangement, and reconciliation. In: Sankoff D, Nadeau JH, editors. Comparative genomics: empirical and analytical approaches to gene order dynamics, map alignment and the evolution of gene families. Dordrecht: Springer; 2000. p. 537\u201350. https:\/\/doi.org\/10.1007\/978-94-011-4309-7_46."},{"key":"169_CR22","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-1-4471-5298-9_4","volume-title":"Duplication, rearrangement and reconciliation: a follow-up 13 years later","author":"C Chauve","year":"2013","unstructured":"Chauve C, El-Mabrouk N, Gu\u00e9guen L, Semeria M, Tannier E. Models and algorithms for genome evolution. In: Chauve C, El-Mabrouk N, Tannier E, editors. Duplication, rearrangement and reconciliation: a follow-up 13 years later. London: Springer; 2013. p. 47\u201362. https:\/\/doi.org\/10.1007\/978-1-4471-5298-9_4."},{"issue":"5","key":"169_CR23","doi-asserted-by":"publisher","first-page":"1312","DOI":"10.1093\/gbe\/evx069","volume":"9","author":"W Duchemin","year":"2017","unstructured":"Duchemin W, Anselmetti Y, Patterson M, Ponty Y, B\u00e9rard S, Chauve C, Scornavacca C, Daubin V, Tannier E. Decostar: Reconstructing the ancestral organization of genes or genomes using reconciled phylogenies. Genome Biol Evol. 2017;9(5):1312\u20139. https:\/\/doi.org\/10.1093\/gbe\/evx069.","journal-title":"Genome Biol Evol"},{"key":"169_CR24","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1186\/1748-7188-8-6","volume":"8","author":"PEC Compeau","year":"2013","unstructured":"Compeau PEC. DCJ-Indel sorting revisited. Algorith Mol Biol. 2013;8:6. https:\/\/doi.org\/10.1186\/1748-7188-8-6.","journal-title":"Algorith Mol Biol"},{"key":"169_CR25","doi-asserted-by":"publisher","unstructured":"Galil Z, Micali S, Gabow HN. Priority queues with variable priority and an O(EV log V) algorithm for finding a maximal weighted matching in general graphs. In: 23rd Annual Symposium on Foundations of Computer Science, 1982;255\u2013261. https:\/\/doi.org\/10.1109\/SFCS.1982.36","DOI":"10.1109\/SFCS.1982.36"},{"key":"169_CR26","unstructured":"Berman P, Karpinski M, Scott A.D. Approximation hardness of short symmetric instances of MAX-3SAT. Technical Report TR03-049, electronic colloquium on computational complexity (ECCC) 2003. http:\/\/eccc.hpi-web.de\/eccc-reports\/2003\/TR03-049\/index.html"},{"key":"169_CR27","doi-asserted-by":"publisher","unstructured":"Davin AA, Tricou T, Tannier E, de Vienne DM, Szollosi GJ. Zombi: A simulator of species, genes and genomes that accounts for extinct lineages. bioRxiv 2018. https:\/\/doi.org\/10.1101\/339473","DOI":"10.1101\/339473"},{"issue":"S2","key":"169_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s12864-018-4466-7","volume":"19","author":"Y Anselmetti","year":"2018","unstructured":"Anselmetti Y, Duchemin W, Tannier E, Chauve C, B\u00e9rard S. Phylogenetic signal from rearrangements in 18 Anopheles species by joint scaffolding extant and ancestral genomes. BMC Genom. 2018;19(S2):1\u201315. https:\/\/doi.org\/10.1186\/s12864-018-4466-7.","journal-title":"BMC Genom"},{"key":"169_CR29","unstructured":"Blin G, Fertin G, Chauve C. The breakpoint distance for signed sequences. 1st conference on algorithms and computational methods for biochemical and evolutionary networks (CompBioNets\u201904), vol. 3. Texts in Algorithms London: King\u2019s College London publications; 2004. p. 3\u201316."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-00169-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-020-00169-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-00169-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T19:17:56Z","timestamp":1620069476000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-020-00169-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,4]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["169"],"URL":"https:\/\/doi.org\/10.1186\/s13015-020-00169-y","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.2.23403\/v1","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,4]]},"assertion":[{"value":"10 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"8"}}