{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T07:08:27Z","timestamp":1743059307138,"version":"3.40.3"},"publisher-location":"London","reference-count":71,"publisher":"Springer London","isbn-type":[{"type":"print","value":"9781447152972"},{"type":"electronic","value":"9781447152989"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-1-4471-5298-9_9","type":"book-chapter","created":{"date-parts":[[2013,9,17]],"date-time":"2013-09-17T09:20:12Z","timestamp":1379409612000},"page":"183-206","source":"Crossref","is-referenced-by-count":3,"title":["A Retrospective on Genomic Preprocessing for Comparative Genomics"],"prefix":"10.1007","author":[{"given":"Binhai","family":"Zhu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1089\/cmb.2008.0061","volume":"15","author":"S. Angibaud","year":"2008","unstructured":"Angibaud, S., Fertin, G., Rusu, I., Th\u00e9venin, A., Vialette, S.: Efficient tools for computing the number of breakpoints and the number of adjacencies between two genomes with duplicate genes. J. Comput. Biol. 15, 1093\u20131115 (2008)","journal-title":"J. Comput. Biol."},{"issue":"1","key":"9_CR2","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., Thevenin, A., Vialette, S.: On the approximability of comparing genomes with duplicates. J. Graph Algorithms Appl. 13(1), 19\u201353 (2009)","journal-title":"J. Graph Algorithms Appl."},{"issue":"5","key":"9_CR3","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1089\/106652701753216503","volume":"8","author":"D. Bader","year":"2001","unstructured":"Bader, D., Moret, B., Yan, M.: A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. J. Comput. Biol. 8(5), 483\u2013491 (2001)","journal-title":"J. Comput. Biol."},{"key":"9_CR4","first-page":"239","volume":"12","author":"V. Bafna","year":"1995","unstructured":"Bafna, V., Pevzner, P.: Sorting by reversals: genome rearrangements in plant organelles and evolutionary history of X chromosome. Mol. Biol. Evol. 12, 239\u2013246 (1995)","journal-title":"Mol. Biol. Evol."},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539703437843","volume":"36","author":"R. Bar-Yehuda","year":"2006","unstructured":"Bar-Yehuda, R., Halld\u00f3rsson, M.M., Naor, J.(S.), Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM J. Comput. 36, 1\u201315 (2006)","journal-title":"SIAM J. Comput."},{"key":"9_CR6","series-title":"LNCS","first-page":"630","volume-title":"Proc. 8th Latin American Theoretical Informatics Symposium","author":"S. Bereg","year":"2008","unstructured":"Bereg, S., Jiang, M., Wang, W., Yang, B., Zhu, B.: Simplifying 3D polygonal chains under the discrete Fr\u00e9chet distance. In: Proc. 8th Latin American Theoretical Informatics Symposium (LATIN\u201908), April 7\u201311, 2008. LNCS, vol. 4957, pp. 630\u2013641 (2008)"},{"issue":"2","key":"9_CR7","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1089\/cmb.2006.13.567","volume":"13","author":"A. Bergeron","year":"2006","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: On sorting by translocations. J. Comput. Biol. 13(2), 567\u2013578 (2006)","journal-title":"J. Comput. Biol."},{"key":"9_CR8","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/3-540-45071-8_9","volume-title":"Proc. 9th Intl. Ann. Comput. and Combinatorics","author":"A. Bergeron","year":"2003","unstructured":"Bergeron, A., Stoye, J.: On the similarity of sets of permutations and its applications to genome comparison. In: Proc. 9th Intl. Ann. Comput. and Combinatorics (COCOON\u201903). LNCS, vol.\u00a02697, pp. 68\u201379 (2003)"},{"key":"9_CR9","first-page":"200","volume-title":"Proceedings of the 10th Annual European Symposium on Algorithms","author":"P. Berman","year":"2002","unstructured":"Berman, P., Hannenhalli, S., Karpinski, M.: 1.375-approximation algorithm for sorting by reversals. In: Proceedings of the 10th Annual European Symposium on Algorithms (ESA\u201902), pp. 200\u2013210 (2002)"},{"issue":"10","key":"9_CR10","doi-asserted-by":"publisher","first-page":"1475","DOI":"10.1089\/cmb.2009.0094","volume":"16","author":"D. Bertrand","year":"2009","unstructured":"Bertrand, D., Blanchette, M., El-Mabrouk, N.: Genetic map refinement using a comparative genomic approach. J. Comput. Biol. 16(10), 1475\u20131486 (2009)","journal-title":"J. Comput. Biol."},{"key":"9_CR11","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/11533719_5","volume-title":"Proc. 11th Intl. Ann. Comput. and Combinatorics","author":"G. Blin","year":"2005","unstructured":"Blin, G., Rizzi, R.: Conserved interval distance computation between non-trivial genomes. In:\u00a0Proc. 11th Intl. Ann. Comput. and Combinatorics (COCOON\u201905). LNCS, vol. 3595, pp.\u00a022\u201331 (2005)"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1109\/TCBB.2007.1069","volume":"4","author":"G. Blin","year":"2007","unstructured":"Blin, G., Chauve, C., Fertin, G., Rizzi, R., Vialette, S.: Comparing genomes with duplicates: a computational complexity point of view. IEEE\/ACM Trans. Comput. Biol. Bioinform. 4, 523\u2013534 (2007)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"9_CR13","series-title":"LNCS","first-page":"357","volume-title":"Proc. 3nd Workshop on Algorithm and Computation","author":"G. Blin","year":"2009","unstructured":"Blin, G., Fertin, G., Sikora, F., Vialette, S.: The exemplar breakpoint distance for non-trivial genomes cannot be approximated. In: Proc. 3nd Workshop on Algorithm and Computation (WALCOM\u201909). LNCS, vol. 5431, pp. 357\u2013368 (2009)"},{"key":"9_CR14","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, J. (eds.) Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment, and the Evolution of Gene Families, pp. 207\u2013212. Kluwer Academic, Dordrecht (2000)"},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.tcs.2012.04.034","volume":"440\u2013441","author":"L. Bulteau","year":"2012","unstructured":"Bulteau, L., Fertin, G., Jiang, M., Rusu, I.: Tractability and approximability of maximal strip recovery. Theor. Comput. Sci. 440\u2013441, 14\u201328 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9_CR16","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/110851390","volume":"26","author":"L. Bulteau","year":"2012","unstructured":"Bulteau, L., Fertin, G., Rusu, I.: Sorting by transpositions is difficult. SIAM J. Discrete Math. 26(3), 1148\u20131180 (2012)","journal-title":"SIAM J. Discrete Math."},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S089548019731994X","volume":"12","author":"A. Caprara","year":"1999","unstructured":"Caprara, A.: Sorting permutations by reversals and Eulerian cycle decompositions. SIAM J. Discrete Math. 12, 91\u2013110 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"9_CR18","first-page":"212","volume-title":"Proceedings of the 36th ACM Symposium on Theory of Computing","author":"J. Chen","year":"2004","unstructured":"Chen, J., Huang, X., Kanj, I., Xia, G.: Linear FPT reductions and computational lower bounds. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC\u201904), pp. 212\u2013221 (2004)"},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/978-3-642-14031-0_47","volume-title":"Proc. of the 16th International Conf. on Computing and Combinatorics","author":"X. Chen","year":"2010","unstructured":"Chen, X.: On sorting permutations by double-cut-and-joins. In: Proc. of the 16th International Conf. on Computing and Combinatorics (COCOON\u201910), pp. 439\u2013448 (2010)"},{"issue":"Suppl. 9","key":"9_CR20","doi-asserted-by":"publisher","first-page":"S17","DOI":"10.1186\/1471-2105-12-S9-S17","volume":"12","author":"X. Chen","year":"2011","unstructured":"Chen, X., Sun, R., Yu, J.: Approximating the double-cut-and-join distance between unsigned genomes. BMC Bioinform. 12(Suppl. 9), S17 (2011)","journal-title":"BMC Bioinform."},{"key":"9_CR21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/11775096_27","volume-title":"Proc. 2nd Intl. Conf. on Algorithmic Aspects in Information and Management","author":"Z. Chen","year":"2006","unstructured":"Chen, Z., Fu, B., Zhu, B.: The approximability of the exemplar breakpoint distance problem. In: Proc. 2nd Intl. Conf. on Algorithmic Aspects in Information and Management (AAIM\u201906). LNCS, vol. 4041, pp. 291\u2013302 (2006)"},{"key":"9_CR22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/11809678_27","volume-title":"Proc. 12th Intl. Ann. Comput. and Combinatorics","author":"Z. Chen","year":"2006","unstructured":"Chen, Z., Fu, B., Fowler, R., Zhu, B.: Lower bounds on the approximation of the exemplar conserved interval distance problem of genomes. In: Proc. 12th Intl. Ann. Comput. and Combinatorics (COCOON\u201906). LNCS, vol. 4112, pp. 245\u2013254 (2006)"},{"key":"9_CR23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-540-73437-6_14","volume-title":"Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching","author":"Z. Chen","year":"2007","unstructured":"Chen, Z., Fu, B., Yang, B., Xu, J., Zhao, Z., Zhu, B.: Non-breaking similarity of genomes with gene repetitions. In: Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM\u201907). LNCS, vol. 4580, pp. 119\u2013130 (2007)"},{"issue":"2","key":"9_CR24","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s10878-007-9077-1","volume":"15","author":"Z. Chen","year":"2008","unstructured":"Chen, Z., Fu, B., Fowler, R., Zhu, B.: On the inapproximability of the exemplar conserved interval distance problem of genomes. J. Comb. Optim. 15(2), 201\u2013221 (2008)","journal-title":"J. Comb. Optim."},{"key":"9_CR25","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10878-009-9233-x","volume":"18","author":"Z. Chen","year":"2009","unstructured":"Chen, Z., Fu, B., Jiang, M., Zhu, B.: On recovering syntenic blocks from comparative maps. J. Comb. Optim. 18, 307\u2013318 (2009)","journal-title":"J. Comb. Optim."},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"Chen, Z., Fu, B., Goebel, R., Lin, G., Tong, W., Xu, J., Yang, B., Zhao, Z., Zhu, B.: On the approximability of the exemplar non-breakpoint similarity problem of genomes with gene repetitions. Theor. Comput. Sci. (2013, to appear)","DOI":"10.1016\/j.tcs.2014.07.011"},{"key":"9_CR27","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/978-3-540-74126-8_26","volume-title":"Proc. of the 7th International Workshop on Algorithms in Bioinformatics","author":"V. Choi","year":"2007","unstructured":"Choi, V., Zheng, C., Zhu, Q., Sankoff, D.: Algorithms for the extraction of synteny blocks from comparative maps. In: Proc. of the 7th International Workshop on Algorithms in Bioinformatics (WABI\u201907), pp. 277\u2013288 (2007)"},{"key":"9_CR28","first-page":"244","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"D. Christie","year":"1998","unstructured":"Christie, D.: A 3\/2-approximation algorithm for sorting by reversals. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998), pp. 244\u2013252 (1998)"},{"key":"9_CR29","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"9_CR30","first-page":"667","volume-title":"Proc. 13th ACM-SIAM Symp. on Discrete Algorithms","author":"G. Cormode","year":"2002","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. In: Proc. 13th ACM-SIAM Symp. on Discrete Algorithms (SODA\u201902), pp. 667\u2013676 (2002)"},{"issue":"1","key":"9_CR31","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1109\/TCBB.2007.70216","volume":"5","author":"Y. Cui","year":"2008","unstructured":"Cui, Y., Wang, L., Zhu, D., Liu, X.: A (1.5+\u03f5)-approximation algorithm for unsigned translocation distance. IEEE\/ACM Trans. Comput. Biol. Bioinform. 5(1), 56\u201366 (2008)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"9_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"9_CR33","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1109\/TCBB.2006.44","volume":"3","author":"I. Elias","year":"2006","unstructured":"Elias, I., Hartman, T.: A 1.375-approximation algorithm for sorting by transpositions. IEEE\/ACM Trans. Comput. Biol. Bioinform. 3, 369\u2013379 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"9_CR34","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"volume-title":"Mathematics of Evolution and Phylogeny","year":"2004","key":"9_CR35","unstructured":"Gascuel, O. (ed.): Mathematics of Evolution and Phylogeny. Oxford University Press, Oxford (2004)"},{"key":"9_CR36","series-title":"LNCS","first-page":"473","volume-title":"Proc.15th Intl. Symposium on Algorithms and Computation","author":"A. Goldstein","year":"2011","unstructured":"Goldstein, A., Kolman, P., Zheng, J.: Minimum common string partitioning problem: hardness and approximations. In: Proc.15th Intl. Symposium on Algorithms and Computation (ISAAC\u201904). LNCS, vol. 3341, pp. 473\u2013484 (2011). Also in: Electron. J. Comb. 12, paper R50 (2005)"},{"issue":"1\u20133","key":"9_CR37","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 Appl. Math. 71(1\u20133), 137\u2013151 (1996)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"S. Hannenhalli","year":"1999","unstructured":"Hannenhalli, S., Pevzner, P.: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. ACM 46(1), 1\u201327 (1999)","journal-title":"J. ACM"},{"key":"9_CR39","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e4stad","year":"1999","unstructured":"H\u00e4stad, J.: Clique is hard to approximate within n\n                           1\u2212\u03f5\n                           . Acta Math. 182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"9_CR40","series-title":"LNBI","first-page":"83","volume-title":"Proc. of the 2010 International RECOMB-CG Workshop","author":"H. Jiang","year":"2010","unstructured":"Jiang, H., Zheng, C., Sankoff, D., Zhu, B.: Scaffold filling under the breakpoint distance. In: Proc. of the 2010 International RECOMB-CG Workshop (RECOMB-CG\u201910). LNBI, vol.\u00a06398, pp. 83\u201392 (2010)"},{"key":"9_CR41","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-21458-5_7","volume-title":"Proc. 22nd Annual Symposium on Combinatorial Pattern Matching","author":"H. Jiang","year":"2011","unstructured":"Jiang, H., Zhong, F., Zhu, B.: Filling scaffolds with gene repetitions: maximizing the number of adjacencies. In: Proc. 22nd Annual Symposium on Combinatorial Pattern Matching (CPM\u201911). LNCS, vol. 6661, pp. 55\u201364 (2011)"},{"issue":"3","key":"9_CR42","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1093\/bioinformatics\/btq674","volume":"27","author":"H. Jiang","year":"2011","unstructured":"Jiang, H., Zhu, B., Zhu, D.: Algorithms for sorting unsigned linear genomes by the DCJ operations. Bioinformatics 27(3), 311\u2013316 (2011)","journal-title":"Bioinformatics"},{"issue":"4","key":"9_CR43","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s10878-010-9366-y","volume":"23","author":"H. Jiang","year":"2012","unstructured":"Jiang, H., Li, Z., Lin, G., Wang, L., Zhu, B.: Exact and approximation algorithms for the complementary maximal strip recovery problem. J. Comb. Optim. 23(4), 493\u2013506 (2012)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"9_CR44","doi-asserted-by":"publisher","first-page":"1220","DOI":"10.1109\/TCBB.2012.57","volume":"9","author":"H. Jiang","year":"2012","unstructured":"Jiang, H., Zheng, C., Sankoff, D., Zhu, B.: Scaffold filling under the breakpoint and related distances. IEEE\/ACM Trans. Bioinform. Comput. Biol. 9(4), 1220\u20131229 (2012)","journal-title":"IEEE\/ACM Trans. Bioinform. Comput. Biol."},{"key":"9_CR45","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/978-3-642-31265-6_28","volume-title":"Proc. 23rd Annual Combinatorial Pattern Matching Symposium","author":"H. Jiang","year":"2012","unstructured":"Jiang, H., Zhu, B.: A linear kernel for the complementary maximal strip recovery problem. In: Proc. 23rd Annual Combinatorial Pattern Matching Symposium (CPM\u201912). LNCS, vol. 7354, pp. 349\u2013359 (2012)"},{"key":"9_CR46","doi-asserted-by":"crossref","unstructured":"Jiang, H., Wang, L., Zhu, B., Zhu, D.: A (1.408+\u03f5)-approximation algorithm for sorting unsigned genomes by reciprocal translocations. In: RECOMB\u201913, poster (2013)","DOI":"10.1007\/978-3-319-08016-1_12"},{"key":"9_CR47","series-title":"LNBI","first-page":"74","volume-title":"Proc. of the 2010 International RECOMB-CG Workshop","author":"M. Jiang","year":"2010","unstructured":"Jiang, M.: The zero exemplar distance problem. In: Proc. of the 2010 International RECOMB-CG Workshop (RECOMB-CG\u201910). LNBI, vol. 6398, pp. 74\u201382 (2010)"},{"key":"9_CR48","doi-asserted-by":"publisher","first-page":"880","DOI":"10.1137\/S0097539798334207","volume":"29","author":"H. Kaplan","year":"1999","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.: A faster and simpler algorithm for sorting signed permutations by reversals. SIAM J. Comput. 29, 880\u2013892 (1999)","journal-title":"SIAM J. Comput."},{"key":"9_CR49","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-540-27801-6_24","volume-title":"Proc. of the 15th Annual Symposium on Combinatorial Pattern Matching","author":"G. Li","year":"2004","unstructured":"Li, G., Qin, X., Wang, X., Zhu, B.: A linear-time algorithm for computing translocation distance between signed genomes. In: Proc. of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM\u201904), pp. 323\u2013332 (2004)"},{"issue":"3","key":"9_CR50","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1016\/j.jcss.2011.10.014","volume":"78","author":"G. Lin","year":"2012","unstructured":"Lin, G., Goebel, R., Li, Z., Wang, L.: An improved approximation algorithm for the complementary maximal strip recovery problem. J. Comput. Syst. Sci. 78(3), 720\u2013730 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR51","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/978-3-642-38768-5_36","volume-title":"Proc. of the 19th Intl. Conf. on Computing and Combinatorics","author":"N. Liu","year":"2013","unstructured":"Liu, N., Jiang, H., Zhu, D., Zhu, B.: An improved approximation algorithm for scaffold filling to maximize the common adjacencies. In: Proc. of the 19th Intl. Conf. on Computing and Combinatorics (COCOON\u201913). LNCS, vol. 7936, pp. 397\u2013408 (2013)"},{"key":"9_CR52","first-page":"1474","volume":"8","author":"C. Makaroff","year":"1988","unstructured":"Makaroff, C., Palmer, J.: Mitochondrial DNA rearrangements and transcriptional alternatives in the male sterile cytoplasm of Ogura radish. Mol. Cell. Biol. 8, 1474\u20131480 (1988)","journal-title":"Mol. Cell. Biol."},{"issue":"3","key":"9_CR53","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.tcs.2004.02.039","volume":"325","author":"M. Marron","year":"2004","unstructured":"Marron, M., Swenson, K., Moret, B.: Genomic distances under deletions and insertions. Theor. Comput. Sci. 325(3), 347\u2013360 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR54","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1186\/1471-2105-11-304","volume":"11","author":"A. Mu\u00f1oz","year":"2010","unstructured":"Mu\u00f1oz, A., Zheng, C., Zhu, Q., Albert, V., Rounsley, S., Sankoff, D.: Scaffold filling, contig fusion and gene order comparison. BMC Bioinform. 11, 304 (2010)","journal-title":"BMC Bioinform."},{"issue":"10","key":"9_CR55","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 21(10), 2171\u20132176 (2005)","journal-title":"Bioinformatics"},{"issue":"4","key":"9_CR56","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1016\/j.jda.2011.04.003","volume":"9","author":"M. Ozery-Flato","year":"2011","unstructured":"Ozery-Flato, M., Shamir, R.: An $O(n^{\\frac{3}{2}}\\sqrt{\\log n})$ algorithm for sorting by reciprocal translocations. J. Discrete Algorithms 9(4), 344\u2013357 (2011)","journal-title":"J. Discrete Algorithms"},{"key":"9_CR57","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/BF02143500","volume":"27","author":"J. Palmer","year":"1988","unstructured":"Palmer, J., Herbon, L.: Plant mitochondrial DNA evolves rapidly in structure, but slowly in sequence. J. Mol. Evol. 27, 87\u201397 (1988)","journal-title":"J. Mol. Evol."},{"key":"9_CR58","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1007\/978-3-642-38768-5_61","volume-title":"Proc. of the 19th Intl. Conf. on Computing and Combinatorics","author":"C. Peng","year":"2013","unstructured":"Peng, C., Zhou, J., Zhu, B., Zhu, H.: The program download problem: complexity and algorithms. In: Proc. of the 19th Intl. Conf. on Computing and Combinatorics (COCOON\u201913). LNCS, vol. 7936, pp. 688\u2013695 (2013)"},{"issue":"11","key":"9_CR59","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1093\/bioinformatics\/15.11.909","volume":"16","author":"D. Sankoff","year":"1999","unstructured":"Sankoff, D.: Genome rearrangement with gene families. Bioinformatics 16(11), 909\u2013917 (1999)","journal-title":"Bioinformatics"},{"key":"9_CR60","first-page":"216","volume-title":"Proceedings of the 10th ACM Symposium on Theory of Computing","author":"T. Schaefer","year":"1978","unstructured":"Schaefer, T.: The complexity of satisfiability problem. In: Proceedings of the 10th ACM Symposium on Theory of Computing (STOC\u201978), pp. 216\u2013226 (1978)"},{"key":"9_CR61","first-page":"697","volume":"46","author":"A. Sturtevant","year":"1926","unstructured":"Sturtevant, A.: A crossover reducer in Drosophila melanogaster due to inversion of a section of the third chromosome. Biol. Zent.bl. 46, 697\u2013702 (1926)","journal-title":"Biol. Zent.bl."},{"key":"9_CR62","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1073\/pnas.22.7.448","volume":"22","author":"A. Sturtevant","year":"1936","unstructured":"Sturtevant, A., Dobzhansky, T.: Inversions in the third chromosome of wild races of drosophila pseudoobscura, and their use in the study of the history of the species. Proc. Natl. Acad. Sci. USA 22, 448\u2013450 (1936)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"3","key":"9_CR63","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1089\/cmb.2009.0184","volume":"17","author":"K. Swenson","year":"2010","unstructured":"Swenson, K., Rajan, V., Lin, Y., Moret, B.: Sorting signed permutations by inversions in O(nlogn) time. J. Comput. Biol. 17(3), 489\u2013501 (2010)","journal-title":"J. Comput. Biol."},{"key":"9_CR64","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-27801-6_1","volume-title":"Proc. of 15th Symp. Combinatorial Pattern Matching","author":"E. Tannier","year":"2004","unstructured":"Tannier, E., Sagot, M.-F.: Sorting by reversals in subquadratic time. In: Proc. of 15th Symp. Combinatorial Pattern Matching (CPM\u201904), pp. 1\u201313 (2004)"},{"issue":"7","key":"9_CR65","doi-asserted-by":"publisher","first-page":"907","DOI":"10.1089\/cmb.2009.0084","volume":"17","author":"L. Wang","year":"2010","unstructured":"Wang, L., Zhu, B.: On the tractability of maximal strip recovery. J. Comput. Biol. 17(7), 907\u2013914 (2010). (Correction, 18(1) (Jan. 2011))","journal-title":"J. Comput. Biol."},{"key":"9_CR66","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0022-5193(82)90384-8","volume":"99","author":"G. Watterson","year":"1982","unstructured":"Watterson, G., Ewens, W., Hall, T., Morgan, A.: The chromosome inversion problem. J. Theor. Biol. 99, 1\u20137 (1982)","journal-title":"J. Theor. Biol."},{"key":"9_CR67","author":"T. Wylie","year":"2013","unstructured":"Wylie, T., Zhu, B.: Protein chain pair simplification under the discrete Frechet distance. IEEE\/ACM Trans. Comput. Biol. Bioinform. 2013). doi:167B699B-E22D-471A-8EE7-01F51E8230D4. Special Issue of ISBRA\u201912","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"9_CR68","doi-asserted-by":"crossref","first-page":"2235","DOI":"10.1093\/genetics\/165.4.2235","volume":"165","author":"I. Yap","year":"2003","unstructured":"Yap, I., Schneider, D., Kleinberg, J., et al.: A graph-theoretic approach to comparing and integrating genetic, physical and sequence-based maps. Genetics 165, 2235\u20132247 (2003)","journal-title":"Genetics"},{"key":"9_CR69","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 21, 3340\u20133346 (2005)","journal-title":"Bioinformatics"},{"key":"9_CR70","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1109\/TCBB.2007.1075","volume":"4","author":"C. Zheng","year":"2007","unstructured":"Zheng, C., Zhu, Q., Sankoff, D.: Removing noise and ambiguities from comparative maps in rearrangement analysis. IEEE\/ACM Trans. Comput. Biol. Bioinform. 4, 515\u2013522 (2007)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"1\u20133","key":"9_CR71","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.tcs.2005.09.078","volume":"352","author":"D. Zhu","year":"2006","unstructured":"Zhu, D., Wang, L.: On the complexity of unsigned translocation distance. Theor. Comput. Sci. 352(1\u20133), 322\u2013328 (2006)","journal-title":"Theor. Comput. Sci."}],"container-title":["Computational Biology","Models and Algorithms for Genome Evolution"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4471-5298-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T03:59:07Z","timestamp":1675223947000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-1-4471-5298-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9781447152972","9781447152989"],"references-count":71,"URL":"https:\/\/doi.org\/10.1007\/978-1-4471-5298-9_9","relation":{},"ISSN":["1568-2684"],"issn-type":[{"type":"print","value":"1568-2684"}],"subject":[],"published":{"date-parts":[[2013]]}}}