{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T16:24:05Z","timestamp":1775924645824,"version":"3.50.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,1,4]],"date-time":"2024-01-04T00:00:00Z","timestamp":1704326400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,4]],"date-time":"2024-01-04T00:00:00Z","timestamp":1704326400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005721","name":"Universit\u00e4t Bielefeld","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005721","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"Abstract<\/jats:title>\n Background<\/jats:title>\n Two genomes $$\\mathbb {A}$$<\/jats:tex-math>\n A<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$\\mathbb {B}$$<\/jats:tex-math>\n B<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> over the same set of gene families form a canonical<\/jats:italic> pair when each of them has exactly one gene from each family. Denote by $$n_*$$<\/jats:tex-math>\n \n n<\/mml:mi>\n \n \n \u2217<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> the number of common families of $$\\mathbb {A}$$<\/jats:tex-math>\n A<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$\\mathbb {B}$$<\/jats:tex-math>\n B<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Different distances of canonical genomes can be derived from a structure called breakpoint graph<\/jats:italic>, which represents the relation between the two given genomes as a collection of cycles of even length and paths. Let $$c_i$$<\/jats:tex-math>\n \n c<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$p_j$$<\/jats:tex-math>\n \n p<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be respectively the numbers of cycles of length i<\/jats:italic> and of paths of length j<\/jats:italic> in the breakpoint graph of genomes $$\\mathbb {A}$$<\/jats:tex-math>\n A<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$\\mathbb {B}$$<\/jats:tex-math>\n B<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Then, the breakpoint distance of $$\\mathbb {A}$$<\/jats:tex-math>\n A<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$\\mathbb {B}$$<\/jats:tex-math>\n B<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is equal to $$n_*-\\left( c_2+\\frac{p_0}{2}\\right)$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \n \n \u2217<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msub>\n -<\/mml:mo>\n \n \n c<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n +<\/mml:mo>\n \n \n p<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Similarly, when the considered rearrangements are those modeled by the double-cut-and-join<\/jats:italic> (DCJ) operation, the rearrangement distance of $$\\mathbb {A}$$<\/jats:tex-math>\n A<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$\\mathbb {B}$$<\/jats:tex-math>\n B<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is $$n_*-\\left( c+\\frac{p_e }{2}\\right)$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \n \n \u2217<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msub>\n -<\/mml:mo>\n \n c<\/mml:mi>\n +<\/mml:mo>\n \n \n p<\/mml:mi>\n e<\/mml:mi>\n <\/mml:msub>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where c<\/jats:italic> is the total number of cycles and $$p_e$$<\/jats:tex-math>\n \n p<\/mml:mi>\n e<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the total number of paths of even length.<\/jats:p>\n <\/jats:sec>\n Motivation<\/jats:title>\n The distance formulation is a basic unit for several other combinatorial problems related to genome evolution and ancestral reconstruction, such as median<\/jats:italic> or double distance<\/jats:italic>. Interestingly, both median and double distance problems can be solved in polynomial time for the breakpoint distance, while they are NP-hard for the rearrangement distance. One way of exploring the complexity space between these two extremes is to consider a $$\\sigma _k$$<\/jats:tex-math>\n \n \u03c3<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> distance, defined to be $$n_*-\\left( c_2+c_4+\\ldots +c_k+\\frac{p_0+p_2+\\ldots +p_{k-2}}{2}\\right)$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \n \n \u2217<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msub>\n -<\/mml:mo>\n \n \n c<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n +<\/mml:mo>\n \n c<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msub>\n +<\/mml:mo>\n \u2026<\/mml:mo>\n +<\/mml:mo>\n \n c<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n +<\/mml:mo>\n \n \n \n p<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n +<\/mml:mo>\n \n p<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n +<\/mml:mo>\n \u2026<\/mml:mo>\n +<\/mml:mo>\n \n p<\/mml:mi>\n \n k<\/mml:mi>\n -<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and increasingly investigate the complexities of median and double distance for the $$\\sigma _4$$<\/jats:tex-math>\n \n \u03c3<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> distance, then the\u00a0$$\\sigma _6$$<\/jats:tex-math>\n \n \u03c3<\/mml:mi>\n 6<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> distance, and so on.<\/jats:p>\n <\/jats:sec>\n Results<\/jats:title>\n While for the median much effort was done in our and in other research groups but no progress was obtained even for the $$\\sigma _4$$<\/jats:tex-math>\n \n \u03c3<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> distance, for solving the double distance under $$\\sigma _4$$<\/jats:tex-math>\n \n \u03c3<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$\\sigma _6$$<\/jats:tex-math>\n \n \u03c3<\/mml:mi>\n 6<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> distances we could devise linear time algorithms, which we present here.<\/jats:p>\n <\/jats:sec>","DOI":"10.1186\/s13015-023-00246-y","type":"journal-article","created":{"date-parts":[[2024,1,4]],"date-time":"2024-01-04T07:02:46Z","timestamp":1704351766000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Investigating the complexity of the double distance problems"],"prefix":"10.1186","volume":"19","author":[{"given":"Mar\u00edlia D. V.","family":"Braga","sequence":"first","affiliation":[]},{"given":"Leonie R.","family":"Brockmann","sequence":"additional","affiliation":[]},{"given":"Katharina","family":"Klerx","sequence":"additional","affiliation":[]},{"given":"Jens","family":"Stoye","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,1,4]]},"reference":[{"key":"246_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/3-540-56024-6_10","volume-title":"Proceedings of CPM 1992, LNCS","author":"D Sankoff","year":"1992","unstructured":"Sankoff D. Edit distance for genome comparison based on non-local operations. In: Manber U, editor. Proceedings of CPM 1992, LNCS, vol. 644. Berlin: Springer; 1992. p. 121\u201335. https:\/\/doi.org\/10.1007\/3-540-56024-6_10."},{"key":"246_CR2","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 Bioinformatics. 2009;10:120. https:\/\/doi.org\/10.1186\/1471-2105-10-120.","journal-title":"BMC Bioinformatics"},{"key":"246_CR3","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1109\/SFCS.1995.492588","volume-title":"Proceedings of FOCS 1995","author":"S Hannenhalli","year":"1995","unstructured":"Hannenhalli S, Pevzner PA. Transforming men into mice polynomial algorithm for genomic distance problem. In: Hannenhalli S, editor. Proceedings of FOCS 1995. Milwaukee: IEEE; 1995. p. 581\u201392. https:\/\/doi.org\/10.1109\/SFCS.1995.492588."},{"issue":"1","key":"246_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"S Hannenhalli","year":"1999","unstructured":"Hannenhalli S, Pevzner PA. Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J ACM. 1999;46(1):1\u201327. https:\/\/doi.org\/10.1145\/300515.300516.","journal-title":"J ACM"},{"issue":"16","key":"246_CR5","doi-asserted-by":"publisher","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","volume":"21","author":"S Yancopoulos","year":"2005","unstructured":"Yancopoulos S, Attie O, Friedberg R. Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics. 2005;21(16):3340\u20136. https:\/\/doi.org\/10.1093\/bioinformatics\/bti535.","journal-title":"Bioinformatics"},{"issue":"3","key":"246_CR6","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1137\/S0097539700377177","volume":"32","author":"N El-Mabrouk","year":"2003","unstructured":"El-Mabrouk N, Sankoff D. The reconstruction of doubled genomes. SIAM J Comput. 2003;32(3):754\u201392. https:\/\/doi.org\/10.1137\/S0097539700377177.","journal-title":"SIAM J Comput"},{"key":"246_CR7","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1109\/SFCS.1993.366872","volume-title":"Proceedings of FOCS 1993","author":"V Bafna","year":"1993","unstructured":"Bafna V, Pevzner PA. Genome rearrangements and sorting by reversals. In: Bafna V, editor. Proceedings of FOCS 1993. Palo Alto: IEEE; 1993. p. 148\u201357. https:\/\/doi.org\/10.1109\/SFCS.1993.366872."},{"key":"246_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/11851561_16","volume-title":"Proceedings of WABI 2006, LNBI","author":"A Bergeron","year":"2006","unstructured":"Bergeron A, Mixtacki J, Stoye J. A unifying view of genome rearrangements. In: Bucher P, Moret BM, editors. Proceedings of WABI 2006, LNBI, vol. 4175. Zurich: Springer; 2006. p. 163\u201373. https:\/\/doi.org\/10.1007\/11851561_16."},{"issue":"1","key":"246_CR9","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1109\/TCBB.2007.1002","volume":"4","author":"M Alekseyev","year":"2008","unstructured":"Alekseyev M, Pevzner PA. Colored de Bruijn graphs and the genome halving problem. IEEE\/ACM Trans Comput Biol Bioinform. 2008;4(1):98\u2013107. https:\/\/doi.org\/10.1109\/TCBB.2007.1002.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"246_CR10","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-540-69733-6_28","volume-title":"Proceedings of COCOON 2008, LNCS","author":"J Mixtacki","year":"2008","unstructured":"Mixtacki J. Genome halving under DCJ revisited. In: Hu X, Wang J, editors. Proceedings of COCOON 2008, LNCS, vol. 5092. Dalian: Springer; 2008. p. 276\u201386.\u00a0https:\/\/doi.org\/10.1007\/978-3-540-69733-6_28"},{"key":"246_CR11","unstructured":"Chauve C. Personal communication in Dagstuhl Seminar no. 18451\u2014genomics, pattern avoidance, and statistical mechanics. 2018."},{"issue":"13","key":"246_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4230\/LIPIcs.WABI.2022.13","volume":"242","author":"MDV Braga","year":"2022","unstructured":"Braga MDV, Brockmann LR, Klerx K, Stoye J. A linear time algorithm for an extended version of the breakpoint double distance. Proceedings of WABI 2022, LIPIcs 242(13). Dagstuhl Publishing; 2022. https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2022.13.","journal-title":"WABI LIPIcs"},{"key":"246_CR13","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-031-36911-7_3","volume-title":"Recomb-CG 2023, LNBI","author":"MDV Braga","year":"2023","unstructured":"Braga MDV, Brockmann LR, Klerx K, Stoye J. On the class of double distance problems. In: Jahn K, Vinai T, editors. Proceedings of Recomb-CG 2023, LNBI, vol. 13883. Istanbul: Springer; 2023. p. 35\u201350.\u00a0https:\/\/doi.org\/10.1007\/978-3-031-36911-7_3"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-023-00246-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-023-00246-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-023-00246-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,4]],"date-time":"2024-01-04T07:07:37Z","timestamp":1704352057000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-023-00246-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,4]]},"references-count":13,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["246"],"URL":"https:\/\/doi.org\/10.1186\/s13015-023-00246-y","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,4]]},"assertion":[{"value":"31 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"1"}}