{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:56:49Z","timestamp":1725796609281},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319087825"},{"type":"electronic","value":"9783319087832"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08783-2_20","type":"book-chapter","created":{"date-parts":[[2014,7,5]],"date-time":"2014-07-05T14:04:30Z","timestamp":1404569070000},"page":"227-238","source":"Crossref","is-referenced-by-count":0,"title":["A Lin-Kernighan Heuristic for the DCJ Median Problem of Genomes with Unequal Contents"],"prefix":"10.1007","author":[{"given":"Zhaoming","family":"Yin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jijun","family":"Tang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen W.","family":"Schaeffer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David A.","family":"Bader","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"20_CR1","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 Algorithms Appl.\u00a013(1), 19\u201353 (2009)","journal-title":"J. Graph Algorithms Appl."},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1089\/106652701753216503","volume":"8","author":"D.A. Bader","year":"2001","unstructured":"Bader, D.A., Moret, B.M.E., Yan, M.: A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. Journal of Computational Biology\u00a08, 483\u2013491 (2001)","journal-title":"Journal of Computational Biology"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: On sorting by translocations. Journal of Computational Biology, 615\u2013629 (2005)","DOI":"10.1007\/11415770_47"},{"key":"20_CR4","unstructured":"Blin, G., Chauve, C., Fertin, G.: The breakpoint distance for signed sequences. In: Proc. CompBioNets 2004. Text in Algorithms, vol.\u00a03, pp. 3\u201316. King\u2019s College, London (2004)"},{"issue":"1","key":"20_CR5","first-page":"26","volume":"12","author":"G. Bourque","year":"2002","unstructured":"Bourque, G., Pevzner, P.A.: Genome-Scale Evolution: Reconstructing Gene Orders in the Ancestral Species. Genome Res.\u00a012(1), 26\u201336 (2002)","journal-title":"Genome Res."},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-15294-8_8","volume-title":"Algorithms in Bioinformatics","author":"M.D.V. Braga","year":"2010","unstructured":"Braga, M.D.V., Willing, E., Stoye, J.: Genomic distance with DCJ and indels. In: Moulton, V., Singh, M. (eds.) WABI 2010. LNCS, vol.\u00a06293, pp. 90\u2013101. Springer, Heidelberg (2010)"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Bryant, D.: The complexity of calculating exemplar distances. In: Sankoff, D., Nadeau, J. (eds.) Comparative Genomics. Kluwer (2001)","DOI":"10.1007\/978-94-011-4309-7_19"},{"issue":"1","key":"20_CR8","doi-asserted-by":"publisher","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 Journal on Computing\u00a015(1), 93\u2013113 (2003)","journal-title":"INFORMS Journal on Computing"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Chauve, C., Fertin, G., Rizzi, R., Vialette, S.: Genomes containing duplicates are hard to compare. In: Alexandrov, V.N., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds.) ICCS 2006. Part II. LNCS, vol.\u00a03992, pp. 783\u2013790. Springer, Heidelberg (2006)","DOI":"10.1007\/11758525_105"},{"issue":"4","key":"20_CR10","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1109\/TCBB.2005.48","volume":"2","author":"X. Chen","year":"2005","unstructured":"Chen, X., Zheng, J., Fu, Z., Nan, P., Zhong, Y., Lonardi, S., Jiang, T.: Assignment of orthologous genes via genome rearrangement. IEEE\/ACM Trans. Comput. Biology Bioinform.\u00a02(4), 302\u2013315 (2005)","journal-title":"IEEE\/ACM Trans. Comput. Biology Bioinform."},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Chen, Z., Fu, B., Zhu, B.: Erratum: The approximability of the exemplar breakpoint distance problem. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) FAW-AAIM 2012. LNCS, vol.\u00a07285, p. 368. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-29700-7_34"},{"key":"20_CR12","series-title":"LNBI","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/978-3-642-33122-0_29","volume-title":"Algorithms in Bioinformatics","author":"P.E.C. Compeau","year":"2012","unstructured":"Compeau, P.E.C.: A simplified view of dcj-indel distance. In: Raphael, B., Tang, J. (eds.) WABI 2012. LNCS (LNBI), vol.\u00a07534, pp. 365\u2013377. Springer, Heidelberg (2012)"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Fertin, G., Labarre, A., Rusu, I., Tannier, E., Vialette, S.: Combinatorics of Genome Rearrangements, 1st edn. The MIT Press (2009)","DOI":"10.7551\/mitpress\/9780262062824.003.0001"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Gao, N., Yang, N., Tang, J.: Ancestral genome inference using a genetic algorithm approach. PLoS One\u00a08(5) (2013)","DOI":"10.1371\/journal.pone.0062156"},{"issue":"1-3","key":"20_CR15","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0166-218X(96)00061-3","volume":"71","author":"S. Hannenhalli","year":"1996","unstructured":"Hannenhalli, S.: Polynomial-time algorithm for computing translocation distance between genomes. Discrete Applied Mathematics\u00a071(1-3), 137\u2013151 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"20_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-540-78604-7_23","volume-title":"Evolutionary Computation in Combinatorial Optimization","author":"R. Lenne","year":"2008","unstructured":"Lenne, R., Solnon, C., St\u00fctzle, T., Tannier, E., Birattari, M.: Reactive Stochastic Local Search Algorithms for the Genomic Median Problem. In: van Hemert, J., Cotta, C. (eds.) EvoCOP 2008. LNCS, vol.\u00a04972, pp. 266\u2013276. Springer, Heidelberg (2008)"},{"key":"20_CR17","first-page":"285","volume-title":"Proc. 18th Pacific Symp. on Biocomputing, PSB 2013","author":"Y. Lin","year":"2013","unstructured":"Lin, Y., Hu, F., Tang, J., Moret, B.M.: Maximum likelihood phylogenetic reconstruction from high-resolution whole-genome data and a tree of 68 eukaryotes. In: Proc. 18th Pacific Symp. on Biocomputing, PSB 2013, pp. 285\u2013296. IEEE Computer Society, Washington, DC (2013)"},{"key":"20_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/3-540-45071-8_54","volume-title":"Computing and Combinatorics","author":"M. Marron","year":"2003","unstructured":"Marron, M., Swenson, K.M., Moret, B.M.E.: Genomic distances under deletions and insertions. In: Warnow, T., Zhu, B. (eds.) COCOON 2003. LNCS, vol.\u00a02697, pp. 537\u2013547. Springer, Heidelberg (2003)"},{"key":"20_CR19","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1016\/S0022-0000(02)00007-7","volume":"65","author":"B.M.E. Moret","year":"2002","unstructured":"Moret, B.M.E., Tang, J., San Wang, L., Warnow, Y.: Steps toward accurate reconstructions of phylogenies from gene-order data. J. Comput. Syst. Sci\u00a065, 508\u2013525 (2002)","journal-title":"J. Comput. Syst. Sci"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Moret, B.M.E., Wang, L.S., Warnow, T., Wyman, S.K.: New approaches for reconstructing phylogenies from gene order data. In: ISMB (Supplement of Bioinformatics), pp. 165\u2013173 (2001)","DOI":"10.1093\/bioinformatics\/17.suppl_1.S165"},{"issue":"10","key":"20_CR21","doi-asserted-by":"publisher","first-page":"2171","DOI":"10.1093\/bioinformatics\/bti327","volume":"21","author":"C.T. Nguyen","year":"2005","unstructured":"Nguyen, C.T., Tay, Y.C., Zhang, L.: Divide-and-conquer approach for the exemplar breakpoint distance. Bioinformatics\u00a021(10), 2171\u20132176 (2005)","journal-title":"Bioinformatics"},{"key":"20_CR22","unstructured":"Pe\u2019er, I., Shamir, R.: The median problems for breakpoints are np-complete. Elec. Colloq. on Comput. Complexity\u00a071 (1998)"},{"key":"20_CR23","doi-asserted-by":"crossref","unstructured":"Pevzner, P.A.: Computational Molecular Biology: An Algorithmic Approach, 1st edn. Computational Molecular Biology. A Bradford Book (August 2000)","DOI":"10.7551\/mitpress\/2022.001.0001"},{"issue":"S-1","key":"20_CR24","doi-asserted-by":"publisher","first-page":"30","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.E.: Heuristics for the inversion median problem. BMC Bioinformatics\u00a011(S-1), 30 (2010)","journal-title":"BMC Bioinformatics"},{"issue":"11","key":"20_CR25","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1093\/bioinformatics\/15.11.909","volume":"15","author":"D. Sankoff","year":"1999","unstructured":"Sankoff, D.: Genome rearrangement with gene families. Bioinformatics\u00a015(11), 909\u2013917 (1999)","journal-title":"Bioinformatics"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Shao, M., Lin, Y.: Approximating the edit distance for genomes with duplicate genes under dcj, insertion and deletion. BMC Bioinformatics\u00a013(S-19), S13 (2012)","DOI":"10.1186\/1471-2105-13-S19-S13"},{"key":"20_CR27","series-title":"LNBI","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-319-05269-4_22","volume-title":"Research in Computational Molecular Biology","author":"M. Shao","year":"2014","unstructured":"Shao, M., Lin, Y., Moret, B.: An exact algorithm to compute the DCJ distance for genomes with duplicate genes. In: Sharan, R. (ed.) RECOMB 2014. LNCS (LNBI), vol.\u00a08394, pp. 280\u2013292. Springer, Heidelberg (2014)"},{"key":"20_CR28","unstructured":"Swenson, K.M., Marron, M., Earnest-DeYoung, J.V., Moret, B.M.E.: Approximating the true evolutionary distance between two genomes. In: Demetrescu, C., Sedgewick, R., Tamassia, R. (eds.) ALENEX\/ANALCO, pp. 121\u2013129. SIAM (2005)"},{"key":"20_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-540-45078-8_4","volume-title":"Algorithms and Data Structures","author":"J. Tang","year":"2003","unstructured":"Tang, J., Moret, B.M.E.: Phylogenetic reconstruction from gene-rearrangement data with unequal gene content. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 37\u201346. Springer, Heidelberg (2003)"},{"key":"20_CR30","series-title":"LNBI","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/978-3-642-04744-2_7","volume-title":"Comparative Genomics","author":"A.W. Xu","year":"2009","unstructured":"Xu, A.W.: DCJ median problems on linear multichromosomal genomes: Graph representation and fast exact solutions. In: Ciccarelli, F.D., Mikl\u00f3s, I. (eds.) RECOMB-CG 2009. LNCS (LNBI), vol.\u00a05817, pp. 70\u201383. Springer, Heidelberg (2009)"},{"issue":"10","key":"20_CR31","doi-asserted-by":"publisher","first-page":"1369","DOI":"10.1089\/cmb.2009.0087","volume":"16","author":"A.W. Xu","year":"2009","unstructured":"Xu, A.W.: A fast and exact algorithm for the median of three problem: A graph decomposition approach. Journal of Computational Biology\u00a016(10), 1369\u20131381 (2009)","journal-title":"Journal of Computational Biology"},{"key":"20_CR32","series-title":"LNBI","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-642-23038-7_29","volume-title":"Algorithms in Bioinformatics","author":"A.W. Xu","year":"2011","unstructured":"Xu, A.W., Moret, B.M.E.: Gasts: Parsimony scoring under rearrangements. In: Przytycka, T.M., Sagot, M.-F. (eds.) WABI 2011. LNCS (LNBI), vol.\u00a06833, pp. 351\u2013363. Springer, Heidelberg (2011)"},{"key":"20_CR33","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-540-87361-7_3","volume-title":"Algorithms in Bioinformatics","author":"A.W. Xu","year":"2008","unstructured":"Xu, A.W., Sankoff, D.: Decompositions of multiple breakpoint graphs and rapid exact solutions to the median problem. In: Crandall, K.A., Lagergren, J. (eds.) WABI 2008. LNCS (LNBI), vol.\u00a05251, pp. 25\u201337. Springer, Heidelberg (2008)"},{"issue":"16","key":"20_CR34","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\u00a021(16), 3340\u20133346 (2005)","journal-title":"Bioinformatics"},{"key":"20_CR35","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-540-87989-3_13","volume-title":"Comparative Genomics","author":"S. Yancopoulos","year":"2008","unstructured":"Yancopoulos, S., Friedberg, R.: Sorting genomes with insertions, deletions and duplications by DCJ. In: Nelson, C.E., Vialette, S. (eds.) RECOMB-CG 2008. LNCS (LNBI), vol.\u00a05267, pp. 170\u2013183. Springer, Heidelberg (2008)"},{"key":"20_CR36","doi-asserted-by":"crossref","unstructured":"Yin, Z., Tang, J., Schaeffer, S.W., Bader, D.A.: Streaming breakpoint graph analytics for accelerating and parallelizing the computation of dcj median of three genomes. In: ICCS, pp. 561\u2013570 (2013)","DOI":"10.1016\/j.procs.2013.05.220"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08783-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T06:38:03Z","timestamp":1558939083000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08783-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319087825","9783319087832"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08783-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}