{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T16:18:36Z","timestamp":1742401116806},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540290087"},{"type":"electronic","value":"9783540318125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11557067_19","type":"book-chapter","created":{"date-parts":[[2005,10,20]],"date-time":"2005-10-20T14:02:33Z","timestamp":1129816953000},"page":"228-238","source":"Crossref","is-referenced-by-count":3,"title":["Perfect Sorting by Reversals Is Not Always Difficult"],"prefix":"10.1007","author":[{"given":"S\u00e8verine","family":"B\u00e9rard","sequence":"first","affiliation":[]},{"given":"Anne","family":"Bergeron","sequence":"additional","affiliation":[]},{"given":"Cedric","family":"Chauve","sequence":"additional","affiliation":[]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"19_CR1","doi-asserted-by":"crossref","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. J.\u00a0Comp.\u00a0Biol.\u00a08(5), 483\u2013491 (2001)","journal-title":"J.\u00a0Comp.\u00a0Biol."},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"B\u00e9rard, S., Bergeron, A., Chauve, C.: Conserved structures in evolution scenarios. In: RCG 2004. LNCS (LNBI), vol.\u00a03388, pp. 1\u201315 (2004)","DOI":"10.1007\/978-3-540-32290-0_1"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"B\u00e9rard, S., Bergeron, A., Chauve, C., Paul, C.: Perfect sorting by reversals is not always difficult. Technical Report LIRMM RR-05042, Montpellier, France (2005)","DOI":"10.1007\/11557067_19"},{"key":"19_CR4","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-540-30219-3_2","volume-title":"Algorithms in Bioinformatics","author":"A. Bergeron","year":"2004","unstructured":"Bergeron, A., Blanchette, M., Chateau, A., Chauve, C.: Reconstructing ancestral gene orders using conserved intervals. In: Jonassen, I., Kim, J. (eds.) WABI 2004. LNCS (LNBI), vol.\u00a03240, pp. 14\u201325. Springer, Heidelberg (2004)"},{"key":"19_CR5","unstructured":"Bergeron, A., Chauve, C., Hartman, T., St-Onge, K.: On the properties of sequences of reversals that sort a signed permutation. In: JOBIM 2002, pp. 99\u2013108 (2002)"},{"key":"19_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1007\/11561071_69","volume-title":"Algorithms \u2013 ESA 2005","author":"A. Bergeron","year":"2005","unstructured":"Bergeron, A., Chauve, C., de Montgolfier, F., Raffinot, M.: Computing common intervals of K permutations, with applications to modular decomposition of graphs. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 779\u2013790. Springer, Heidelberg (2005)"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/978-3-540-27801-6_29","volume-title":"Combinatorial Pattern Matching","author":"A. Bergeron","year":"2004","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: Reversal distance without hurdles and fortresses. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 388\u2013399. Springer, Heidelberg (2004)"},{"issue":"1","key":"19_CR8","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."},{"issue":"4","key":"19_CR9","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1101\/gr.1975204","volume":"14","author":"G. Bourque","year":"2004","unstructured":"Bourque, G., Pevzner, P.A., Tesler, G.: Reconstructing the genomic architecture of ancestral mammals: Lessons from human, mouse, and rat genomes. Genome Res.\u00a014(4), 507\u2013516 (2004)","journal-title":"Genome Res."},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/299432.299461","volume-title":"RECOMB 1999","author":"A. Caprara","year":"1999","unstructured":"Caprara, A.: Formulations and hardness of multiple sorting by reversals. In: RECOMB 1999, pp. 84\u201394. ACM Press, New York (1999)"},{"issue":"1","key":"19_CR11","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0012-365X(81)90138-2","volume":"37","author":"M. Chein","year":"1981","unstructured":"Chein, M., Habib, M., Maurer, M.C.: Partitive hypergraphs. Discrete Math.\u00a037(1), 35\u201350 (1981)","journal-title":"Discrete Math."},{"key":"19_CR12","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-540-39763-2_2","volume-title":"Algorithms in Bioinformatics","author":"G. Didier","year":"2003","unstructured":"Didier, G.: Common intervals of two sequences. In: Benson, G., Page, R.D.M. (eds.) WABI 2003. LNCS (LNBI), vol.\u00a02812, pp. 17\u201324. Springer, Heidelberg (2003)"},{"key":"19_CR13","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-540-30219-3_3","volume-title":"Algorithms in Bioinformatics","author":"M. Figeac","year":"2004","unstructured":"Figeac, M., Varr\u00e9, J.-S.: Sorting by reversals with common intervals. In: Jonassen, I., Kim, J. (eds.) WABI 2004. LNCS (LNBI), vol.\u00a03240, pp. 26\u201337. Springer, Heidelberg (2004)"},{"issue":"6982","key":"19_CR14","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1038\/nature02426","volume":"428","author":"R.A. Gibbs","year":"2004","unstructured":"Gibbs, R.A., et al.: Genome sequence of the brown norway rat yields insights into mammalian evolution. Nature\u00a0428(6982), 493\u2013521 (2004)","journal-title":"Nature"},{"key":"19_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/3-540-48194-X_19","volume-title":"Combinatorial Pattern Matching","author":"S. Heber","year":"2001","unstructured":"Heber, S., Stoye, J.: Finding all common intervals of k permutations. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.\u00a02089, pp. 207\u2013218. Springer, Heidelberg (2001)"},{"key":"19_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/11496656_12","volume-title":"Combinatorial Pattern Matching","author":"G.M. Landau","year":"2005","unstructured":"Landau, G.M., Parida, L., Weimann, O.: Using PQ trees for comparative genomics. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol.\u00a03537, pp. 128\u2013143. Springer, Heidelberg (2005)"},{"key":"19_CR17","unstructured":"de Montgolfier, F.: D\u00e9composition modulaire des graphes.\u00a0Th\u00e9orie, extensions et algorithmes. Ph.D. thesis, Universit\u00e9 Montpellier II, France (2003)"},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/11533719_7","volume-title":"Computing and Combinatorics","author":"M.-F. Sagot","year":"2005","unstructured":"Sagot, M.-F., Tannier, E.: Perfect sorting by reversals. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 42\u201352. Springer, Heidelberg (2005)"},{"key":"19_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/3-540-56024-6_10","volume-title":"Combinatorial Pattern Matching","author":"D. Sankoff","year":"1992","unstructured":"Sankoff, D.: Edit distance for genome comparison based on non-local operations. In: Apostolico, A., Galil, Z., Manber, U., Crochemore, M. (eds.) CPM 1992. LNCS, vol.\u00a0644, pp. 121\u2013135. Springer, Heidelberg (1992)"},{"key":"19_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/978-3-540-27801-6_26","volume-title":"3109","author":"T. Schmidt","year":"2004","unstructured":"Schmidt, T., Stoye, J.: Quadratic time algorithms for finding common intervals in two and more sequences. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 347\u2013358. Springer, Heidelberg (2004)"},{"key":"19_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-27801-6_1","volume-title":"Combinatorial Pattern Matching","author":"E. Tannier","year":"2004","unstructured":"Tannier, E., Sagot, M.-F.: Sorting by reversals in subquadratic time. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 1\u201313. Springer, Heidelberg (2004)"},{"issue":"2","key":"19_CR22","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/s004539910014","volume":"26","author":"T. Uno","year":"2000","unstructured":"Uno, T., Yagiura, M.: Fast algorithms to enumerate all common intervals of two permutations. Algorithmica\u00a026(2), 290\u2013309 (2000)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11557067_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:48:12Z","timestamp":1605642492000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11557067_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540290087","9783540318125"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11557067_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}