{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,24]],"date-time":"2025-03-24T06:54:49Z","timestamp":1742799289948},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424239"},{"type":"electronic","value":"9783540446347"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44634-6_34","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T06:20:48Z","timestamp":1186726848000},"page":"365-376","source":"Crossref","is-referenced-by-count":21,"title":["A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study"],"prefix":"10.1007","author":[{"given":"David A.","family":"Bader","sequence":"first","affiliation":[]},{"given":"Bernard M. E.","family":"Moret","sequence":"additional","affiliation":[]},{"given":"Mi","family":"Yan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"34_CR1","unstructured":"V. Bafna and P. Pevzner. Sorting permutations by transpositions. In Proceedings of the 6th Annual Symposium on Discrete Algorithms, pages 614\u2013623, New York, January 1995. ACM Press."},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"V. Bafna and P. A. Pevzner. Genome rearrangements and sorting by reversals. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS93), pages 148\u2013157. IEEE Press, 1993.","DOI":"10.1109\/SFCS.1993.366872"},{"key":"34_CR3","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"V. Bafna","year":"1996","unstructured":"V. Bafna and P. A. Pevzner. Genome rearrangements and sorting by reversals. SIAM Journal on Computing, 25:272\u2013289, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"34_CR4","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V. Bafna","year":"1998","unstructured":"V. Bafna and P. A. Pevzner. Sorting by transpositions. SIAM Journal on Discrete Mathematics, 11:224\u2013240, 1998.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"34_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-61258-0_14","volume-title":"Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching","author":"P. Berman","year":"1996","unstructured":"P. Berman and S. Hannenhalli. Fast Sorting by Reversal. In D.S. Hirschberg and E.W. Myers, editors, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, pages 168\u2013185, Laguna Beach, CA, June 1996. Lecture Notes in Computer Science, 1075, Springer-Verlag."},{"key":"34_CR6","first-page":"25","volume-title":"Genome Informatics","author":"M. Blanchette","year":"1997","unstructured":"M. Blanchette, G. Bourque, and D. Sankoff. Breakpoint phylogenies. In S. Miyano and T. Takagi, editors, Genome Informatics, pages 25\u201334. University Academy Press, Tokyo, Japan, 1997."},{"key":"34_CR7","doi-asserted-by":"crossref","unstructured":"A. Caprara. Sorting by reversals is difficult. In Proceedings of the 1st Conference on Computational Molecular Biology (RECOMB97), pages 75\u201383, Santa Fe, NM, 1997. ACM Press.","DOI":"10.1145\/267521.267531"},{"issue":"1","key":"34_CR8","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S089548019731994X","volume":"12","author":"A. Caprara","year":"1999","unstructured":"A. Caprara. Sorting permutations by reversals and Eulerian cycle decompositions. SIAM J. Discrete Math., 12(1):91\u2013110, 1999.","journal-title":"SIAM J. Discrete Math."},{"key":"34_CR9","unstructured":"M.E. Cosner, R.K. Jansen, B.M.E. Moret, L.A. Raubeson, L.-S. Wang, T. Warnow, and S. Wyman. A new fast heuristic for computing the breakpoint phylogeny and experimental phylogenetic analyses of real and synthetic data. In Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology (ISMB00), pages 104\u2013115, San Diego, CA, 2000."},{"key":"34_CR10","unstructured":"S. Hannenhalli. Software for computing inversion distances between signed gene orders. Department of Mathematics, University of Southern California, URL. http:\/\/www-hto.usc.edu\/plain\/people\/Hannenhalli.html ."},{"key":"34_CR11","doi-asserted-by":"crossref","unstructured":"S. Hannenhalli and P.A. Pevzner. Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). In Proceedings of the 27th Annual Symposium on Theory of Computing (STOC95), pages 178\u2013189, Las Vegas, NV, 1995. ACM Press.","DOI":"10.1145\/225058.225112"},{"issue":"3","key":"34_CR12","doi-asserted-by":"publisher","first-page":"880","DOI":"10.1137\/S0097539798334207","volume":"29","author":"H. Kaplan","year":"1999","unstructured":"H. Kaplan, R. Shamir, and R.E. Tarjan. A faster and simpler algorithm for sorting signed permutations by reversals. SIAM Journal of Computing, 29(3):880\u2013892, 1999. First appeared in Proceedings of the 8th Annual Symposium on Discrete Algorithms (SODA97), 344-351, New Orleans, LA. ACM Press.","journal-title":"SIAM Journal of Computing"},{"key":"34_CR13","unstructured":"I. Mantin and R. Shamir. Genome Rearrangement Algorithm Applet: An algorithm for sorting signed permutations by reversals. http:\/\/www.math.tau.ac.il\/~rshamir\/GR\/ , 1999."},{"key":"34_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/ijoc.8.1.1","volume":"8","author":"C.C. McGeoch","year":"1996","unstructured":"C.C. McGeoch. Toward an experimental method for algorithm simulation. INFORMS Journal of Computing, 8:1\u201315, 1996.","journal-title":"INFORMS Journal of Computing"},{"key":"34_CR15","doi-asserted-by":"crossref","unstructured":"B. M.E. Moret, S. Wyman, D.A. Bader, T. Warnow, and M. Yan. A new implementation and detailed study of breakpoint analysis. In Proceedings of the 6th Pacific Symposium on Biocomputing (PSB2001), pages 583\u2013594, Big Island, HI, January 2001.","DOI":"10.1142\/9789814447362_0056"},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"B.M.E. Moret. Towards a discipline of experimental algorithmics.In DIMACS Monographs in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 2001.To appear. Available at http:\/\/www.cs.unm.edu\/~moret\/dimacs.ps .","DOI":"10.1090\/dimacs\/059\/10"},{"key":"34_CR17","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1073\/pnas.81.3.814","volume":"81","author":"J.H. Nadeau","year":"1984","unstructured":"J.H. Nadeau and B.A. Taylor. Lengths of chromosome segments conserved since divergence of man and mouse. In Proceedings of the National Academy of Sciences, volume 81, pages 814\u2013818, 1984.","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"34_CR18","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.2307\/2445483","volume":"81","author":"R.G. Olmstead","year":"1994","unstructured":"R.G. Olmstead and J.D. Palmer. Chloroplast DNA systematics: a review of methods and data analysis. American Journal of Botany, 81:1205\u20131224, 1994.","journal-title":"American Journal of Botany"},{"key":"34_CR19","doi-asserted-by":"crossref","unstructured":"J.D. Palmer. Chloroplast and mitochondrial genome evolution in land plants. In R. Herrmann, editor, Cell Organelles, pages 99\u2013133. Springer Verlag, 1992.","DOI":"10.1007\/978-3-7091-9138-5_3"},{"key":"34_CR20","doi-asserted-by":"publisher","first-page":"1697","DOI":"10.1126\/science.255.5052.1697","volume":"255","author":"L.A. Raubeson","year":"1992","unstructured":"L.A. Raubeson and R.K. Jansen. Chloroplast DNA evidence on the ancient evolutionary split in vascular land plants. Science, 255:1697\u20131699, 1992.","journal-title":"Science"},{"key":"34_CR21","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1089\/cmb.1998.5.555","volume":"5","author":"D. Sankoff","year":"1998","unstructured":"D. Sankoff and M. Blanchette. Multiple genome rearrangement and breakpoint phylogeny. Journal of Computational Biology, 5:555\u2013570, 1998.","journal-title":"Journal of Computational Biology"},{"key":"34_CR22","volume-title":"Introduction to Computational Molecular Biology","author":"J.C. Setubal","year":"1997","unstructured":"J.C. Setubal and J. Meidanis. Introduction to Computational Molecular Biology. PWS, Boston, MA, 1997."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44634-6_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T18:12:10Z","timestamp":1556734330000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44634-6_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424239","9783540446347"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44634-6_34","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}