{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:13:59Z","timestamp":1773274439801,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642312649","type":"print"},{"value":"9783642312656","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31265-6_32","type":"book-chapter","created":{"date-parts":[[2012,6,12]],"date-time":"2012-06-12T03:28:23Z","timestamp":1339471703000},"page":"399-412","source":"Crossref","is-referenced-by-count":1,"title":["Minimum Leaf Removal for Reconciliation: Complexity and Algorithms"],"prefix":"10.1007","author":[{"given":"Riccardo","family":"Dondi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"El-Mabrouk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-2","key":"32_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci.\u00a0237(1-2), 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"32_CR2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"S. Altschul","year":"1990","unstructured":"Altschul, S., Gish, W., Miller, W., Myers, E., Lipman, D.: Basic local alignment search tool. J. Mol. Biol.\u00a0215(3), 403\u2013410 (1990)","journal-title":"J. Mol. Biol."},{"key":"32_CR3","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/974614.974657","volume-title":"RECOMB 2004","author":"L. Arvestad","year":"2004","unstructured":"Arvestad, L., Berglung, A.C., Lagergren, J., Sennblad, B.: Gene tree reconstruction and orthology analysis based on an integrated model for duplications and sequence evolution. In: Gusfield, D. (ed.) RECOMB 2004, pp. 326\u2013335. ACM, New York (2004)"},{"key":"32_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-642-27660-6_13","volume-title":"SOFSEM 2012: Theory and Practice of Computer Science","author":"G. Blin","year":"2012","unstructured":"Blin, G., Bonizzoni, P., Dondi, R., Rizzi, R., Sikora, F.: Complexity Insights of the Minimum Duplication Problem. In: Bielikov\u00e1, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur\u00e1n, G. (eds.) SOFSEM 2012. LNCS, vol.\u00a07147, pp. 153\u2013164. Springer, Heidelberg (2012)"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"Blomme, T., Vandepoele, K., Bodt, S.D., Silmillion, C., Maere, S., van de Peer, Y.: The gain and loss of genes during 600 millions years of vertebrate evolution. Genome Biology\u00a07, R43 (2006)","DOI":"10.1186\/gb-2006-7-5-r43"},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2005.05.016","volume":"347","author":"P. Bonizzoni","year":"2005","unstructured":"Bonizzoni, P., Della Vedova, G., Dondi, R.: Reconciling a gene tree to a species tree under the duplication cost model. Theoretical Computer Science\u00a0347, 36\u201353 (2005)","journal-title":"Theoretical Computer Science"},{"key":"32_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/11809678_26","volume-title":"Computing and Combinatorics","author":"W.-C. Chang","year":"2006","unstructured":"Chang, W.-C., Eulenstein, O.: Reconciling Gene Trees with Apparent Polytomies. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol.\u00a04112, pp. 235\u2013244. Springer, Heidelberg (2006)"},{"key":"32_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/978-3-642-02008-7_4","volume-title":"Research in Computational Molecular Biology","author":"C. Chauve","year":"2009","unstructured":"Chauve, C., El-Mabrouk, N.: New Perspectives on Gene Family Evolution: Losses in Reconciliation and a Link with Supertrees. In: Batzoglou, S. (ed.) RECOMB 2009. LNCS, vol.\u00a05541, pp. 46\u201358. Springer, Heidelberg (2009)"},{"key":"32_CR9","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1089\/106652700750050871","volume":"7","author":"K. Chen","year":"2000","unstructured":"Chen, K., Durand, D., Farach-Colton, M.: Notung: Dating gene duplications using gene family trees. Journal of Computational Biology\u00a07, 429\u2013447 (2000)","journal-title":"Journal of Computational Biology"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1098\/rspb.2004.2969","volume":"272","author":"J. Cotton","year":"2005","unstructured":"Cotton, J., Page, R.: Rates and patterns of gene duplication and loss in the human genome. Proceedings of the Royal Society of London. Series B\u00a0272, 277\u2013283 (2005)","journal-title":"Proceedings of the Royal Society of London. Series B"},{"key":"32_CR11","doi-asserted-by":"crossref","unstructured":"Demuth, J., Bie, T.D., Stajich, J., Cristianini, N., Hahn, M.: The evolution of mammalian gene families. PLoS ONE\u00a01, e85 (2006)","DOI":"10.1371\/journal.pone.0000085"},{"key":"32_CR12","series-title":"LNBI","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/978-3-642-23038-7_8","volume-title":"Algorithms in Bioinformatics","author":"A. Doroftei","year":"2011","unstructured":"Doroftei, A., El-Mabrouk, N.: Removing Noise from Gene Trees. In: Przytycka, T.M., Sagot, M.-F. (eds.) WABI 2011. LNCS (LNBI), vol.\u00a06833, pp. 76\u201391. Springer, Heidelberg (2011)"},{"key":"32_CR13","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1089\/cmb.2006.13.320","volume":"13","author":"D. Durand","year":"2006","unstructured":"Durand, D., Hald\u00f3rsson, B., Vernot, B.: A hybrid micro-macroevolutionary approach to gene tree reconstruction. Journal of Computational Biology\u00a013, 320\u2013335 (2006)","journal-title":"Journal of Computational Biology"},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1126\/science.1086132","volume":"301","author":"E. Eichler","year":"2003","unstructured":"Eichler, E., Sankoff, D.: Structural dynamics of eukaryotic chromosome evolution. Science\u00a0301, 793\u2013797 (2003)","journal-title":"Science"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"132","DOI":"10.2307\/2412519","volume":"28","author":"M. Goodman","year":"1979","unstructured":"Goodman, M., Czelusniak, J., Moore, G., Romero-Herrera, A., Matsuda, G.: Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences. Systematic Zoology\u00a028, 132\u2013163 (1979)","journal-title":"Systematic Zoology"},{"key":"32_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-642-21260-4_17","volume-title":"Bioinformatics Research and Applications","author":"P. G\u00f3recki","year":"2011","unstructured":"G\u00f3recki, P., Eulenstein, O.: A Linear Time Algorithm for Error-Corrected Reconciliation of Unrooted Gene Trees. In: Chen, J., Wang, J., Zelikovsky, A. (eds.) ISBRA 2011. LNCS, vol.\u00a06674, pp. 148\u2013159. Springer, Heidelberg (2011)"},{"key":"32_CR17","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/j.tcs.2006.05.019","volume":"359","author":"P. Gorecki","year":"2006","unstructured":"Gorecki, P., Tiuryn, J.: DLS-trees: a model of evolutionary scenarios. Theoretical Computer Science\u00a0359, 378\u2013399 (2006)","journal-title":"Theoretical Computer Science"},{"key":"32_CR18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1006\/mpev.1996.0071","volume":"6","author":"R. Guig\u00f3","year":"1996","unstructured":"Guig\u00f3, R., Muchnik, I., Smith, T.: Reconstruction of ancient molecular phylogeny. Molecular Phylogenetics and Evolution\u00a06, 189\u2013213 (1996)","journal-title":"Molecular Phylogenetics and Evolution"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"Hahn, M.: Bias in phylogenetic tree reconciliation methods: implications for vertebrate genome evolution. Genome Biology\u00a08(R141) (2007)","DOI":"10.1186\/gb-2007-8-7-r141"},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"Hahn, M., Han, M., Han, S.G.: Gene family evolution across 12 drosophilia genomes. PLoS Genetics\u00a03, e197 (2007)","DOI":"10.1371\/journal.pgen.0030197"},{"issue":"5","key":"32_CR21","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1093\/bib\/bbr030","volume":"12","author":"D. Kristensen","year":"2011","unstructured":"Kristensen, D., Wolf, Y., Mushegian, A., Koonin, E.: Computational methods for gene orthology inference. Briefings in Bioinformatics\u00a012(5), 379\u2013391 (2011)","journal-title":"Briefings in Bioinformatics"},{"key":"32_CR22","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1137\/S0097539798343362","volume":"30","author":"B. Ma","year":"2000","unstructured":"Ma, B., Li, M., Zhang, L.: From gene trees to species trees. SIAM J. on Comput.\u00a030, 729\u2013752 (2000)","journal-title":"SIAM J. on Comput."},{"key":"32_CR23","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"32_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-86659-3","volume-title":"Evolution by gene duplication","author":"S. Ohno","year":"1970","unstructured":"Ohno, S.: Evolution by gene duplication. Springer, Berlin (1970)"},{"key":"32_CR25","first-page":"58","volume":"43","author":"R. Page","year":"1994","unstructured":"Page, R.: Maps between trees and cladistic analysis of historical associations among genes, organisms, and areas. Systematic Biology\u00a043, 58\u201377 (1994)","journal-title":"Systematic Biology"},{"key":"32_CR26","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1093\/bioinformatics\/14.9.819","volume":"14","author":"R. Page","year":"1998","unstructured":"Page, R.: Genetree: comparing gene and species phylogenies using reconciled trees. Bioinformatics\u00a014, 819\u2013820 (1998)","journal-title":"Bioinformatics"},{"key":"32_CR27","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1090\/dimacs\/037\/04","volume":"37","author":"R. Page","year":"1997","unstructured":"Page, R., Charleston, M.: Reconciled trees and incongruent gene and species trees. DIMACS Series in Discrete Mathematics and Theoretical Computer Science\u00a037, 57\u201370 (1997)","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"32_CR28","doi-asserted-by":"crossref","unstructured":"Page, R., Cotton, J.: Vertebrate phylogenomics: reconciled trees and gene duplications. In: Pacific Symposium on Biocomputing, pp. 536\u2013547 (2002)","DOI":"10.1142\/9789812799623_0050"},{"key":"32_CR29","doi-asserted-by":"crossref","unstructured":"Sanderson, M., McMahon, M.: Inferring angiosperm phylogeny from EST data with widespread gene duplication. BMC Evolutionary Biology\u00a07, S3 (2007)","DOI":"10.1186\/1471-2148-7-S1-S3"},{"key":"32_CR30","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1089\/cmb.2008.0092","volume":"15","author":"B. Vernot","year":"2008","unstructured":"Vernot, B., Stolzer, M., Goldman, A., Durand, D.: Reconciliation with non-binary species trees. Journal of Computational Biology\u00a015, 981\u20131006 (2008)","journal-title":"Journal of Computational Biology"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31265-6_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T22:42:58Z","timestamp":1743374578000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31265-6_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642312649","9783642312656"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31265-6_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}