{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:25Z","timestamp":1759638025540},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,5,30]],"date-time":"2007-05-30T00:00:00Z","timestamp":1180483200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2008,2]]},"DOI":"10.1007\/s10878-007-9077-1","type":"journal-article","created":{"date-parts":[[2007,5,29]],"date-time":"2007-05-29T20:21:34Z","timestamp":1180470094000},"page":"201-221","source":"Crossref","is-referenced-by-count":22,"title":["On the inapproximability of the exemplar conserved interval distance problem of genomes"],"prefix":"10.1007","volume":"15","author":[{"given":"Zhixiang","family":"Chen","sequence":"first","affiliation":[]},{"given":"Richard H.","family":"Fowler","sequence":"additional","affiliation":[]},{"given":"Bin","family":"Fu","sequence":"additional","affiliation":[]},{"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,5,30]]},"reference":[{"key":"9077_CR1","first-page":"239","volume":"12","author":"V Bafna","year":"1995","unstructured":"Bafna V, Pevzner P (1995) Sorting by reversals: genome rearrangements in plant organelles and evolutionary history of X chromosome. Mol Biol Evol 12:239\u2013246","journal-title":"Mol Biol Evol"},{"key":"9077_CR2","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/11533719_6","volume-title":"Proceedings of the 11th international annual confrerence on computers and combinatorics (COCOON\u201905)","author":"S Bereg","year":"2005","unstructured":"Bereg S, Zhu B (2005) RNA multiple structural alignment with longest common subsequences. In: Proceedings of the 11th international annual confrerence on computers and combinatorics (COCOON\u201905). Lecture notes in computer science, vol\u00a03595. Springer, Berlin, pp\u00a032\u201341"},{"key":"9077_CR3","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/3-540-45071-8_9","volume-title":"Proceedings of the 9th international annual confrerence on computers and combinatorics (COCOON\u201903)","author":"A Bergeron","year":"2003","unstructured":"Bergeron A, Stoye J (2003) On the similarity of sets of permutations and its applications to genome comparison. In: Proceedings of the 9th international annual confrerence on computers and combinatorics (COCOON\u201903). Lecture notes in computer science, vol\u00a02697. Springer, Berlin, pp\u00a068\u201379"},{"key":"9077_CR4","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1007\/11533719_5","volume-title":"Proceedings of the 11th international annual confrerence on computers and combinatorics (COCOON\u201905)","author":"G Blin","year":"2005","unstructured":"Blin G, Rizzi R (2005) Conserved interval distance computation between non-trivial genomes. In: Proceedings of the 11th international annual confrerence on computers and combinatorics (COCOON\u201905). Lecture notes in computer science, vol\u00a03595. Springer, Berlin, pp\u00a022\u201331"},{"key":"9077_CR5","doi-asserted-by":"crossref","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 (2000) 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. Kluwer Academic, Dordrecht, pp\u00a0207\u2013212"},{"key":"9077_CR6","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/11809678_27","volume-title":"Proceedings of the 12th international annual confrerence on computers and combinatorics (COCOON\u201906)","author":"Z Chen","year":"2006","unstructured":"Chen Z, Fowler RH, Fu B, Zhu B (2006a) Lowers bounds on the approximation of the conserved interval distance problem of genomes. In: Proceedings of the 12th international annual confrerence on computers and combinatorics (COCOON\u201906). Lecture notes in computer science, vol\u00a04112. Springer, Berlin, pp\u00a0245\u2013254"},{"key":"9077_CR7","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/11775096_27","volume-title":"Proceedings of the second international conference on algorithmic aspects in information and management (AAIM\u201906)","author":"Z Chen","year":"2006","unstructured":"Chen Z, Fu B, Zhu B (2006b) The approximability of the exemplar breakpoint distance problem. In: Proceedings of the second international conference on algorithmic aspects in information and management (AAIM\u201906). Lecture notes in computer science, vol.\u00a04041. Springer, Berlin, pp\u00a0291\u2013302"},{"key":"9077_CR8","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/978-3-540-73437-6_14","volume-title":"Proceedings of the 18th international symposium on combinatorial pattern matching (CPM\u201907)","author":"Z Chen","year":"2007","unstructured":"Chen Z, Fu B, Xu J, Yang B, Zhao Z, Zhu B (2007) Non-breaking similarity of genomes with gene repetitions, submitted for publication. In: Proceedings of the 18th international symposium on combinatorial pattern matching (CPM\u201907). Lecture notes in computer science, vol\u00a04580. Springer, Berlin, pp\u00a0119\u2013130"},{"key":"9077_CR9","volume-title":"Introduction to algorithms","author":"T Cormen","year":"2002","unstructured":"Cormen T, Leiserson C, Rivest R, Stein C (2002) Introduction to algorithms, 2nd edn. McGraw\u2013Hill, Cambridge","edition":"2"},{"key":"9077_CR10","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco"},{"key":"9077_CR11","volume-title":"Mathematics of evolution and phylogeny","year":"2004","unstructured":"Gascuel O (ed) (2004) Mathematics of evolution and phylogeny. Oxford University Press, Oxford"},{"issue":"1","key":"9077_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"S Hannenhalli","year":"1999","unstructured":"Hannenhalli S, Pevzner P (1999) Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J ACM 46(1):1\u201327","journal-title":"J ACM"},{"issue":"5","key":"9077_CR13","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1109\/TSMCC.2005.855522","volume":"36","author":"Z Li","year":"2006","unstructured":"Li Z, Wang L, Zhang K (2006) Algorithmic approaches for genome rearrangement: a review. IEEE Trans Sys Man Cybern Part C: Appl Rev 36(5):636\u2013648","journal-title":"IEEE Trans Sys Man Cybern Part C: Appl Rev"},{"key":"9077_CR14","doi-asserted-by":"crossref","first-page":"1474","DOI":"10.1128\/MCB.8.4.1474","volume":"8","author":"C Makaroff","year":"1988","unstructured":"Makaroff C, Palmer J (1988) Mitochondrial DNA rearrangements and transcriptional alternatives in the male sterile cytoplasm of Ogura radish. Mol Cell Biol 8:1474\u20131480","journal-title":"Mol Cell Biol"},{"issue":"3","key":"9077_CR15","doi-asserted-by":"crossref","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 (2004) Genomic distances under deletions and insertions. Theor Comput Sci 325(3):347\u2013360","journal-title":"Theor Comput Sci"},{"key":"9077_CR16","unstructured":"Nguyen CT (2005) Algorithms for calculating exemplar distances. Honors thesis, School of Computing, National University of Singapore"},{"issue":"10","key":"9077_CR17","doi-asserted-by":"crossref","first-page":"2171","DOI":"10.1093\/bioinformatics\/bti327","volume":"21","author":"CT Nguyen","year":"2005","unstructured":"Nguyen CT, Tay YC, Zhang L (2005) Divide-and-conquer approach for the exemplar breakpoint distance. Bioinformatics 21(10):2171\u20132176","journal-title":"Bioinformatics"},{"key":"9077_CR18","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF02143500","volume":"27","author":"J Palmer","year":"1988","unstructured":"Palmer J, Herbon L (1988) Plant mitochondrial DNA evolves rapidly in structure, but slowly in sequence. J Mol Evol 27:87\u201397","journal-title":"J Mol Evol"},{"issue":"11","key":"9077_CR19","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1093\/bioinformatics\/15.11.909","volume":"16","author":"D Sankoff","year":"1999","unstructured":"Sankoff D (1999) Genome rearrangement with gene families. Bioinformatics 16(11):909\u2013917","journal-title":"Bioinformatics"},{"key":"9077_CR20","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1073\/pnas.22.7.448","volume":"22","author":"A Sturtevant","year":"1936","unstructured":"Sturtevant A, Dobzhansky T (1936) 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","journal-title":"Proc Natl Acad Sci USA"},{"key":"9077_CR21","doi-asserted-by":"crossref","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 (1982) The chromosome inversion problem. J Theor Biol 99:1\u20137","journal-title":"J Theor Biol"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9077-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-007-9077-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9077-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:11Z","timestamp":1559276291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-007-9077-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5,30]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["9077"],"URL":"https:\/\/doi.org\/10.1007\/s10878-007-9077-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,5,30]]}}}