{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T06:25:57Z","timestamp":1789626357395,"version":"build-2803163510"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642230370","type":"print"},{"value":"9783642230387","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23038-7_15","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:06:43Z","timestamp":1314709603000},"page":"163-174","source":"Crossref","is-referenced-by-count":8,"title":["A Practical Algorithm for Ancestral Rearrangement Reconstruction"],"prefix":"10.1007","author":[{"given":"Jakub","family":"Kov\u00e1\u010d","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bro\u0148a","family":"Brejov\u00e1","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom\u00e1\u0161","family":"Vina\u0159","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"1856","DOI":"10.1111\/j.0014-3820.2004.tb00469.x","volume":"58","author":"K. Brown","year":"2004","unstructured":"Brown, K., Burk, L., Henagan, L., Noor, M.: A test of the chromosomal rearrangement model of speciation in Drosophila pseudoobscura. Evolution\u00a058, 1856\u20131860 (2004)","journal-title":"Evolution"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/s00239-005-0216-y","volume":"63","author":"L. Wang","year":"2006","unstructured":"Wang, L., Warnow, T., Moret, B., Jansen, R., Raubeson, L.: Distance-based genome rearrangement phylogeny. Journal of Molecular Evolution\u00a063, 473\u2013483 (2006)","journal-title":"Journal of Molecular Evolution"},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"2412","DOI":"10.1101\/gr.2800104","volume":"14","author":"M. Blanchette","year":"2004","unstructured":"Blanchette, M., Green, E., Miller, W., Haussler, D.: Reconstructing large regions of an ancestral mammalian genome in silico. Genome Research\u00a014, 2412 (2004)","journal-title":"Genome Research"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"1557","DOI":"10.1101\/gr.5383506","volume":"16","author":"J. Ma","year":"2006","unstructured":"Ma, J., Zhang, L., Suh, B., Raney, B., Burhans, R., Kent, W., Blanchette, M., Haussler, D., Miller, W.: Reconstructing contiguous regions of an ancestral genome. Genome Research\u00a016, 1557 (2006)","journal-title":"Genome Research"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1109\/MC.2002.1016902","volume":"35","author":"B. Moret","year":"2002","unstructured":"Moret, B., Warnow, T.: Toward new software for computational phylogenetics. Computer\u00a035, 55\u201364 (2002)","journal-title":"Computer"},{"key":"15_CR6","first-page":"26","volume":"12","author":"G. Bourque","year":"2002","unstructured":"Bourque, G., Pevzner, P.: Genome-scale evolution: reconstructing gene orders in the ancestral species. Genome Research\u00a012, 26 (2002)","journal-title":"Genome Research"},{"key":"15_CR7","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, 3340\u20133346 (2005)","journal-title":"Bioinformatics"},{"key":"15_CR8","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/11851561_16","volume-title":"Algorithms in Bioinformatics","author":"A. Bergeron","year":"2006","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: A unifying view of genome rearrangements. In: B\u00fccher, P., Moret, B.M.E. (eds.) WABI 2006. LNCS (LNBI), vol.\u00a04175, pp. 163\u2013173. Springer, Heidelberg (2006)"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-94-011-4309-7_11","volume-title":"Comparative Genomics","author":"M. Cosner","year":"2000","unstructured":"Cosner, M., Jansen, R., Moret, B., Raubeson, L., Wang, L., Warnow, T., Wyman, S.: An empirical comparison of phylogenetic methods on chloroplast gene order data in Campanulaceae. In: Sankoff, D., Nadeau, J.H. (eds.) Comparative Genomics, pp. 99\u2013121. Kluwer Academic Publishers, Dordrecht (2000)"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Valach, M., Farkas, Z., Fricova, D., Kovac, J., Brejova, B., Vinar, T., Pfeiffer, I., Kucsera, J., Tomaska, L., Lang, B.F., Nosek, J.: Evolution of linear chromosomes and multipartite genomes in yeast mitochondria. Nucleic Acids Research (accepted, 2011)","DOI":"10.1093\/nar\/gkq1345"},{"key":"15_CR11","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1145\/225058.225112","volume-title":"Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing","author":"S. Hannenhalli","year":"1995","unstructured":"Hannenhalli, S., Pevzner, P.: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pp. 178\u2013189. ACM, New York (1995)"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: The inversion distance problem. Math. of Evolution and Phylogeny, 262\u2013290 (2005)","DOI":"10.1093\/oso\/9780198566106.003.0010"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01188586","volume":"13","author":"J. Kececioglu","year":"1995","unstructured":"Kececioglu, J., Sankoff, D.: Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica\u00a013, 180\u2013210 (1995)","journal-title":"Algorithmica"},{"issue":"5","key":"15_CR14","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(5), 483\u2013491 (2001)","journal-title":"Journal of Computational Biology"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Hannenhalli, S., Pevzner, P.A.: Transforming men into mice (polynomial algorithm for genomic distance problem). In: Foundations of Computer Science (FOCS), pp. 581\u2013592 (1995)","DOI":"10.1109\/SFCS.1995.492588"},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/978-3-540-69068-9_8","volume-title":"Combinatorial Pattern Matching","author":"A. Bergeron","year":"2008","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: HP distance via double cut and join distance. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 56\u201368. Springer, Heidelberg (2008)"},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"5300","DOI":"10.1016\/j.tcs.2009.09.008","volume":"410","author":"A. Bergeron","year":"2009","unstructured":"Bergeron, A., Mixtacki, J., Stoye, J.: A new linear time algorithm to compute the genomic distance via the double cut and join distance. Theoretical Computer Science\u00a0410, 5300\u20135316 (2009)","journal-title":"Theoretical Computer Science"},{"key":"15_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BFb0045092","volume-title":"Computing and Combinatorics","author":"D. Sankoff","year":"1997","unstructured":"Sankoff, D., Blanchette, M.: The median problem for breakpoints in comparative genomics. In: Jiang, T., Lee, D.T. (eds.) COCOON 1997. LNCS, vol.\u00a01276, pp. 251\u2013264. Springer, Heidelberg (1997)"},{"key":"15_CR19","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, 93 (2003)","journal-title":"INFORMS Journal on Computing"},{"key":"15_CR20","unstructured":"Pe\u2019er, I., Shamir, R.: The median problems for breakpoints are NP-complete. Electronic Colloquium on Computational Complexity (ECCC) 5 (1998)"},{"key":"15_CR21","unstructured":"Bryant, D.: The complexity of the breakpoint median problem. Technical Report CRM-2579, CRM Universite de Montreal (1998)"},{"key":"15_CR22","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1186\/1471-2105-10-120","volume":"10","author":"E. Tannier","year":"2009","unstructured":"Tannier, E., Zheng, C., Sankoff, D.: Multichromosomal median and halving problems under different genomic distances. BMC Bioinformatics\u00a010, 120 (2009)","journal-title":"BMC Bioinformatics"},{"key":"15_CR23","unstructured":"Blanchette, M., Bourque, G., Sankoff, D.: Breakpoint phylogenies. In: Genome Informatics Workshop (GIW), pp. 25\u201334 (1997)"},{"key":"15_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/3-540-44696-6_15","volume-title":"Algorithms in Bioinformatics","author":"A.C. Siepel","year":"2001","unstructured":"Siepel, A.C., Moret, B.M.E.: Finding an optimal inversion median: Experimental results. In: Gascuel, O., Moret, B.M.E. (eds.) WABI 2001. LNCS, vol.\u00a02149, pp. 189\u2013203. Springer, Heidelberg (2001)"},{"key":"15_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/3-540-44696-6_19","volume-title":"Algorithms in Bioinformatics","author":"A. Caprara","year":"2001","unstructured":"Caprara, A.: On the practical solution of the reversal median problem. In: Gascuel, O., Moret, B.M.E. (eds.) WABI 2001. LNCS, vol.\u00a02149, pp. 238\u2013251. Springer, Heidelberg (2001)"},{"issue":"8","key":"15_CR26","doi-asserted-by":"publisher","first-page":"1079","DOI":"10.1089\/cmb.2008.0116","volume":"15","author":"W. Arndt","year":"2008","unstructured":"Arndt, W., Tang, J.: Improving reversal median computation using commuting reversals and cycle information. Journal of Computational Biology\u00a015(8), 1079\u20131092 (2008)","journal-title":"Journal of Computational Biology"},{"key":"15_CR27","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1186\/1471-2164-9-S2-S15","volume":"9","author":"F. Yue","year":"2008","unstructured":"Yue, F., Zhang, M., Tang, J.: Phylogenetic reconstruction from transpositions. BMC Genomics 9\u00a09, S15 (2008)","journal-title":"BMC Genomics 9"},{"key":"15_CR28","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., Lin, Y., Swenson, K., Moret, B.: Heuristics for the inversion median problem. BMC Bioinformatics\u00a011, S30 (2010)","journal-title":"BMC Bioinformatics"},{"key":"15_CR29","first-page":"69","volume":"4","author":"Z. Adam","year":"2008","unstructured":"Adam, Z., Sankoff, D.: The ABC of MGR with DCJ. Evolutionary Bioinformatics Online\u00a04, 69\u201374 (2008)","journal-title":"Evolutionary Bioinformatics Online"},{"key":"15_CR30","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)"},{"key":"15_CR31","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01732471","volume":"7","author":"D. Sankoff","year":"1976","unstructured":"Sankoff, D., Cedergren, R., Lapalme, G.: Frequency of insertion-deletion, transversion, and transition in the evolution of 5S ribosomal RNA. Journal of Molecular Evolution\u00a07, 133\u2013149 (1976)","journal-title":"Journal of Molecular Evolution"},{"key":"15_CR32","doi-asserted-by":"crossref","unstructured":"Moret, B., Wyman, S., Bader, D., Warnow, T., Yan, M.: A new implementation and detailed study of breakpoint analysis. In: Pacific Symposium on Biocomputing (PSB), pp. 583\u2013594. Citeseer (2001)","DOI":"10.1142\/9789814447362_0056"},{"key":"15_CR33","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1093\/bioinformatics\/17.suppl_1.S165","volume":"17","author":"B. Moret","year":"2001","unstructured":"Moret, B., Wang, L., Warnow, T., Wyman, S.: New approaches for reconstructing phylogenies from gene order data. Bioinformatics\u00a017, S165 (2001)","journal-title":"Bioinformatics"},{"key":"15_CR34","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1016\/S0022-0000(02)00007-7","volume":"65","author":"B. Moret","year":"2002","unstructured":"Moret, B., Tang, J., Wang, L., Warnow, T.: Steps toward accurate reconstructions of phylogenies from gene-order data. Journal of Computer and System Sciences\u00a065, 508\u2013525 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR35","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1093\/bioinformatics\/btl300","volume":"23","author":"M. Bernt","year":"2007","unstructured":"Bernt, M., Merkle, D., Middendorf, M.: Using median sets for inferring phylogenetic trees. Bioinformatics\u00a023, e129 (2007)","journal-title":"Bioinformatics"},{"key":"15_CR36","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.tcs.2006.12.006","volume":"374","author":"N. Eriksen","year":"2007","unstructured":"Eriksen, N.: Reversal and transposition medians. Theoretical Computer Science\u00a0374, 111\u2013126 (2007)","journal-title":"Theoretical Computer Science"},{"key":"15_CR37","doi-asserted-by":"crossref","unstructured":"Eriksen, N.: Median clouds and a fast transposition median solver. In: International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC), DMTCS Proceedings, pp. 373\u2013384 (2009)","DOI":"10.46298\/dmtcs.2739"},{"key":"15_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/3-540-45784-4_40","volume-title":"Algorithms in Bioinformatics","author":"B. Moret","year":"2002","unstructured":"Moret, B., Siepel, A., Tang, J., Liu, T.: Inversion medians outperform breakpoint medians in phylogeny reconstruction from gene-order data. In: Guig\u00f3, R., Gusfield, D. (eds.) WABI 2002. LNCS, vol.\u00a02452, pp. 521\u2013536. Springer, Heidelberg (2002)"},{"key":"15_CR39","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.ympev.2005.03.026","volume":"36","author":"B. Larget","year":"2005","unstructured":"Larget, B., Kadane, J., Simon, D.: A Bayesian approach to the estimation of ancestral genome arrangements. Molecular Phylogenetics and Evolution\u00a036, 214\u2013223 (2005)","journal-title":"Molecular Phylogenetics and Evolution"},{"key":"15_CR40","doi-asserted-by":"publisher","first-page":"1572","DOI":"10.1093\/bioinformatics\/btg180","volume":"19","author":"F. Ronquist","year":"2003","unstructured":"Ronquist, F., Huelsenbeck, J.: MrBayes 3: Bayesian phylogenetic inference under mixed models. Bioinformatics\u00a019, 1572 (2003)","journal-title":"Bioinformatics"}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23038-7_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,9]],"date-time":"2025-03-09T12:10:27Z","timestamp":1741522227000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23038-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642230370","9783642230387"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23038-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}