{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T04:08:46Z","timestamp":1750910926640,"version":"3.41.0"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319679785"},{"type":"electronic","value":"9783319679792"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-67979-2_9","type":"book-chapter","created":{"date-parts":[[2017,9,14]],"date-time":"2017-09-14T04:31:23Z","timestamp":1505363483000},"page":"156-178","source":"Crossref","is-referenced-by-count":4,"title":["A Unified ILP Framework for Genome Median, Halving, and Aliquoting Problems Under DCJ"],"prefix":"10.1007","author":[{"given":"Pavel","family":"Avdeyev","sequence":"first","affiliation":[]},{"given":"Nikita","family":"Alexeev","sequence":"additional","affiliation":[]},{"given":"Yongwu","family":"Rong","sequence":"additional","affiliation":[]},{"given":"Max A.","family":"Alekseyev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,9,15]]},"reference":[{"issue":"1","key":"9_CR1","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1109\/TCBB.2007.1002","volume":"4","author":"MA Alekseyev","year":"2007","unstructured":"Alekseyev, M.A., Pevzner, P.A.: Colored de Bruijn graphs and the genome halving problem. IEEE\/ACM Trans. Comput. Biol. Bioinf. (TCBB) 4(1), 98\u2013107 (2007)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf. (TCBB)"},{"key":"9_CR2","unstructured":"Alekseyev, M.A., Pevzner, P.A.: Whole genome duplications, multi-break rearrangements, and genome halving problem. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 665\u2013679. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2007)"},{"issue":"2","key":"9_CR3","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.tcs.2008.01.013","volume":"395","author":"MA Alekseyev","year":"2008","unstructured":"Alekseyev, M.A., Pevzner, P.A.: Multi-break rearrangements and chromosomal evolution. Theoret. Comput. Sci. 395(2), 193\u2013202 (2008)","journal-title":"Theoret. Comput. Sci."},{"issue":"14","key":"9_CR4","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1186\/s12859-016-1263-7","volume":"17","author":"N Alexeev","year":"2016","unstructured":"Alexeev, N., Avdeyev, P., Alekseyev, M.A.: Comparative genomics meets topology: a novel view on genome median and halving problems. BMC Bioinf. 17(14), 418 (2016)","journal-title":"BMC Bioinf."},{"issue":"3","key":"9_CR5","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1089\/cmb.2015.0160","volume":"23","author":"P Avdeyev","year":"2016","unstructured":"Avdeyev, P., Jiang, S., Aganezov, S., Hu, F., Alekseyev, M.A.: Reconstruction of ancestral genomes in presence of gene gain and loss. J. Comput. Biol. 23(3), 150\u2013164 (2016)","journal-title":"J. Comput. Biol."},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/11851561_16","volume-title":"Algorithms in Bioinformatics","author":"A Bergeron","year":"2006","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: A unifying view of genome rearrangements. In: B\u00fccher, P., Moret, B.M.E. (eds.) WABI 2006. LNCS, vol. 4175, pp. 163\u2013173. Springer, Heidelberg (2006). doi: 10.1007\/11851561_16"},{"issue":"1","key":"9_CR7","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1287\/ijoc.15.1.93.15155","volume":"15","author":"A Caprara","year":"2003","unstructured":"Caprara, A.: The reversal median problem. INFORMS J. Comput. 15(1), 93\u2013113 (2003)","journal-title":"INFORMS J. Comput."},{"key":"9_CR8","unstructured":"Caprara, A., Lancia, G., Ng, S.K.: Fast practical solution of sorting by reversals. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 12\u201321. Society for Industrial and Applied Mathematics (2000)"},{"issue":"10","key":"9_CR9","doi-asserted-by":"crossref","first-page":"e314","DOI":"10.1371\/journal.pbio.0030314","volume":"3","author":"P Dehal","year":"2005","unstructured":"Dehal, P., Boore, J.L.: Two rounds of whole genome duplication in the ancestral vertebrate. PLoS Biol. 3(10), e314 (2005)","journal-title":"PLoS Biol."},{"key":"9_CR10","unstructured":"Dias, Z., de Souza, C.C.: Polynomial-sized ILP models for rearrangement distance problems. In: Brazilian Symposium On Bioinformatics, p. 74 (2007)"},{"issue":"3","key":"9_CR11","doi-asserted-by":"crossref","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. 32(3), 754\u2013792 (2003)","journal-title":"SIAM J. Comput."},{"issue":"Suppl 14","key":"9_CR12","doi-asserted-by":"crossref","first-page":"S3","DOI":"10.1186\/1471-2105-16-S14-S3","volume":"16","author":"P Feij\u00e3o","year":"2015","unstructured":"Feij\u00e3o, P.: Reconstruction of ancestral gene orders using intermediate genomes. BMC Bioinf. 16(Suppl 14), S3 (2015)","journal-title":"BMC Bioinf."},{"issue":"14","key":"9_CR13","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1186\/s12859-016-1261-9","volume":"17","author":"P Feij\u00e3o","year":"2016","unstructured":"Feij\u00e3o, P., Araujo, E.: Fast ancestral gene order reconstruction of genomes with unequal gene content. BMC Bioinf. 17(14), 413 (2016)","journal-title":"BMC Bioinf."},{"key":"9_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-16181-0_3","volume-title":"Comparative Genomics","author":"Y Gagnon","year":"2010","unstructured":"Gagnon, Y., Savard, O.T., Bertrand, D., El-Mabrouk, N.: Advances on genome duplication distances. In: Tannier, E. (ed.) RECOMB-CG 2010. LNCS, vol. 6398, pp. 25\u201338. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-16181-0_3"},{"issue":"5","key":"9_CR15","first-page":"1","volume":"8","author":"N Gao","year":"2013","unstructured":"Gao, N., Yang, N., Tang, J.: Ancestral genome inference using a genetic algorithm approach. PLoS ONE 8(5), 1\u20136 (2013)","journal-title":"PLoS ONE"},{"key":"9_CR16","first-page":"21","volume":"15","author":"H Gavranovi\u0107","year":"2010","unstructured":"Gavranovi\u0107, H., Tannier, E.: Guided genome halving: provably optimal solutions provide good insights into the preduplication ancestral genome of saccharomyces cerevisiae. Pac. Symp. Biocomput. 15, 21\u201330 (2010)","journal-title":"Pac. Symp. Biocomput."},{"key":"9_CR17","unstructured":"Gurobi Optimization Inc: Gurobi optimizer reference manual (2016). http:\/\/www.gurobi.com"},{"issue":"3","key":"9_CR18","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1139\/g04-016","volume":"47","author":"R Guyot","year":"2004","unstructured":"Guyot, R., Keller, B.: Ancestral genome duplication in rice. Genome 47(3), 610\u2013614 (2004)","journal-title":"Genome"},{"issue":"19","key":"9_CR19","first-page":"1","volume":"13","author":"M Haghighi","year":"2012","unstructured":"Haghighi, M., Sankoff, D.: Medians seek the corners, and other conjectures. BMC Bioinform. 13(19), 1 (2012)","journal-title":"BMC Bioinform."},{"key":"9_CR20","doi-asserted-by":"publisher","unstructured":"Hartmann, T., Wieseke, N., Sharan, R., Middendorf, M., Bernt, M.: Genome Rearrangement with ILP. IEEE\/ACM Trans. Comput. Biol. Bioinform. (2017, in press). doi: 10.1109\/TCBB.2017.2708121","DOI":"10.1109\/TCBB.2017.2708121"},{"issue":"6983","key":"9_CR21","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1038\/nature02424","volume":"428","author":"M Kellis","year":"2004","unstructured":"Kellis, M., Birren, B.W., Lander, E.S.: Proof and evolutionary analysis of ancient genome duplication in the yeast saccharomyces cerevisiae. Nature 428(6983), 617\u2013624 (2004)","journal-title":"Nature"},{"key":"9_CR22","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1090\/dimacs\/047\/10","volume":"47","author":"ACG Lancia","year":"1999","unstructured":"Lancia, A.C.G., Ng, S.K.: A column-generation based branch-and-bound algorithm for sorting by reversals. Math. Support Mol. Biol. 47, 213 (1999)","journal-title":"Math. Support Mol. Biol."},{"key":"9_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/978-3-319-16483-0_48","volume-title":"Bioinformatics and Biomedical Engineering","author":"G Lancia","year":"2015","unstructured":"Lancia, G., Rinaldi, F., Serafini, P.: A unified integer programming model for genome rearrangement problems. In: Ortu\u00f1o, F., Rojas, I. (eds.) IWBBIO 2015. LNCS, vol. 9043, pp. 491\u2013502. Springer, Cham (2015). doi: 10.1007\/978-3-319-16483-0_48"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Laohakiat, S., Lursinsap, C., Suksawatchon, J.: Duplicated genes reversal distance under gene deletion constraint by integer programming. In: 2008 2nd International Conference on Bioinformatics and Biomedical Engineering, pp. 527\u2013530, May 2008","DOI":"10.1109\/ICBBE.2008.128"},{"key":"9_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-540-69733-6_28","volume-title":"Computing and Combinatorics","author":"J Mixtacki","year":"2008","unstructured":"Mixtacki, J.: Genome halving under DCJ revisited. In: Hu, X., Wang, J. (eds.) COCOON 2008. LNCS, vol. 5092, pp. 276\u2013286. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-69733-6_28"},{"issue":"4","key":"9_CR26","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1038\/ng0498-345","volume":"18","author":"JH Postlethwait","year":"1998","unstructured":"Postlethwait, J.H., Yan, Y.L., Gates, M.A., Horne, S., Amores, A., Brownlie, A., Donovan, A., Egan, E.S., Force, A., Gong, Z., et al.: Vertebrate genome evolution and the zebrafish gene map. Nat. Genet. 18(4), 345\u2013349 (1998)","journal-title":"Nat. Genet."},{"issue":"1","key":"9_CR27","doi-asserted-by":"crossref","first-page":"S30","DOI":"10.1186\/1471-2105-11-S1-S30","volume":"11","author":"V Rajan","year":"2010","unstructured":"Rajan, V., Xu, A.W., Lin, Y., Swenson, K.M., Moret, B.M.: Heuristics for the inversion median problem. BMC Bioinf. 11(1), S30 (2010)","journal-title":"BMC Bioinf."},{"issue":"9","key":"9_CR28","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1089\/cmb.2011.0136","volume":"18","author":"OT Savard","year":"2011","unstructured":"Savard, O.T., Gagnon, Y., Bertrand, D., El-Mabrouk, N.: Genome halving and double distance with losses. J. Comput. Biol. 18(9), 1185\u20131199 (2011)","journal-title":"J. Comput. Biol."},{"issue":"5","key":"9_CR29","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1089\/cmb.2014.0096","volume":"22","author":"M Shao","year":"2015","unstructured":"Shao, M., Lin, Y., Moret, B.M.: An exact algorithm to compute the double-cut-and-join distance for genomes with duplicate genes. J. Comput. Biol. 22(5), 425\u2013435 (2015)","journal-title":"J. Comput. Biol."},{"issue":"12","key":"9_CR30","doi-asserted-by":"crossref","first-page":"i329","DOI":"10.1093\/bioinformatics\/btv229","volume":"31","author":"M Shao","year":"2015","unstructured":"Shao, M., Moret, B.M.: Comparing genomes with rearrangements and segmental duplications. Bioinformatics 31(12), i329 (2015)","journal-title":"Bioinformatics"},{"issue":"01","key":"9_CR31","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1142\/S0219720007002552","volume":"05","author":"J Suksawatchon","year":"2007","unstructured":"Suksawatchon, J., Lursinsap, C., Boden, M.: Computing the reversal distance between genomes in the presence of multi-gene families via binary integer programming. J. Bioinf. Comput. Biol. 05(01), 117\u2013133 (2007)","journal-title":"J. Bioinf. Comput. Biol."},{"issue":"1","key":"9_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-10-1","volume":"10","author":"KM Swenson","year":"2009","unstructured":"Swenson, K.M., Moret, B.M.: Inversion-based genomic signatures. BMC Bioinf. 10(1), 1 (2009)","journal-title":"BMC Bioinf."},{"issue":"1","key":"9_CR33","doi-asserted-by":"crossref","first-page":"1","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. 10(1), 1 (2009)","journal-title":"BMC Bioinf."},{"key":"9_CR34","unstructured":"The OEIS Foundation: The On-Line Encyclopedia of Integer Sequences. Published electronically at http:\/\/oeis.org (2017)"},{"issue":"1","key":"9_CR35","doi-asserted-by":"crossref","first-page":"S2","DOI":"10.1186\/1471-2105-10-35","volume":"10","author":"R Warren","year":"2009","unstructured":"Warren, R., Sankoff, D.: Genome aliquoting with double cut and join. BMC Bioinf. 10(1), S2 (2009)","journal-title":"BMC Bioinf."},{"issue":"02","key":"9_CR36","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1142\/S0219720009004102","volume":"7","author":"R Warren","year":"2009","unstructured":"Warren, R., Sankoff, D.: Genome halving with double cut and join. J. Bioinf. Comput. Biol. 7(02), 357\u2013371 (2009)","journal-title":"J. Bioinf. Comput. Biol."},{"issue":"10","key":"9_CR37","doi-asserted-by":"crossref","first-page":"1369","DOI":"10.1089\/cmb.2009.0087","volume":"16","author":"AW Xu","year":"2009","unstructured":"Xu, A.W.: A fast and exact algorithm for the median of three problem: A graph decomposition approach. J. Comput. Biol. 16(10), 1369\u20131381 (2009)","journal-title":"J. Comput. Biol."},{"issue":"16","key":"9_CR38","doi-asserted-by":"crossref","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 21(16), 3340\u20133346 (2005)","journal-title":"Bioinformatics"},{"key":"9_CR39","doi-asserted-by":"crossref","unstructured":"Zhang, M., Arndt, W., Tang, J.: An exact solver for the DCJ median problem. In: Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing, p. 138. NIH Public Access (2009)","DOI":"10.1142\/9789812836939_0014"},{"issue":"13","key":"9_CR40","doi-asserted-by":"crossref","first-page":"i96","DOI":"10.1093\/bioinformatics\/btn146","volume":"24","author":"C Zheng","year":"2008","unstructured":"Zheng, C., Zhu, Q., Adam, Z., Sankoff, D.: Guided genome halving: hardness, heuristics and the history of the hemiascomycetes. Bioinformatics 24(13), i96 (2008)","journal-title":"Bioinformatics"},{"key":"9_CR41","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1177\/117693430600200028","volume":"2","author":"C Zheng","year":"2006","unstructured":"Zheng, C., Zhu, Q., Sankoff, D.: Genome halving with an outgroup. Evol. Bioinf. 2, 295\u2013302 (2006)","journal-title":"Evol. Bioinf."}],"container-title":["Lecture Notes in Computer Science","Comparative Genomics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-67979-2_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T18:53:21Z","timestamp":1750877601000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-67979-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319679785","9783319679792"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-67979-2_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}