{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T10:15:19Z","timestamp":1760523319609,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662482209"},{"type":"electronic","value":"9783662482216"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48221-6_5","type":"book-chapter","created":{"date-parts":[[2015,8,27]],"date-time":"2015-08-27T14:14:31Z","timestamp":1440684871000},"page":"66-79","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Orthology Relation and Gene Tree Correction: Complexity Results"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Lafond","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"El-Mabrouk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,28]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"AV Aho","year":"1981","unstructured":"Aho, A.V., Sagiv, Y., Szymanski, T.G., Ullman, J.D.: Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J. Comp. 10, 405\u2013421 (1981)","journal-title":"SIAM J. Comp."},{"issue":"1","key":"5_CR2","doi-asserted-by":"publisher","first-page":"e53786","DOI":"10.1371\/journal.pone.0053786","volume":"8","author":"AM Altenhoff","year":"2013","unstructured":"Altenhoff, A.M., Gil, M., Gonnet, G.H., Dessimoz, C.: Inferring hierarchical orthologous groups from orthologous gene pairs. PLoS One 8(1), e53786 (2013)","journal-title":"PLoS One"},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1093\/nar\/gkm1020","volume":"36","author":"AC Berglund","year":"2008","unstructured":"Berglund, A.C., Sjolund, E., Ostlund, G., Sonnhammer, E.L.: InParanoid 6: eukaryotic ortholog clusters with inparalogs. Nucl. Acids Res. 36, 263\u2013266 (2008)","journal-title":"Nucl. Acids Res."},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-540-39890-5_11","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A Bretscher","year":"2003","unstructured":"Bretscher, A., Corneil, D.G., Habib, M., Paul, C.: A simple linear time LexBFS cograph recognition algorithm. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 119\u2013130. Springer, Heidelberg (2003)"},{"issue":"Supp. 10","key":"5_CR5","first-page":"S11","volume":"13","author":"R Chaudhary","year":"2011","unstructured":"Chaudhary, R., Burleigh, J.G., Eulenstein, O.: Efficient error correction algorithms for gene tree reconciliation based on duplication, duplication and loss, and deep coalescence. BMC Bioinf. 13(Supp. 10), S11 (2011)","journal-title":"BMC Bioinf."},{"key":"5_CR6","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. J. Comp. Biol. 7, 429\u2013447 (2000)","journal-title":"J. Comp. Biol."},{"issue":"1","key":"5_CR7","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1038\/75556","volume":"25","author":"The Gene Ontology Consortium","year":"2000","unstructured":"The Gene Ontology Consortium: Gene ontology: tool for the unification of biology. Nat. Genet. 25(1), 25\u201329 (2000)","journal-title":"Nat. Genet."},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"W84","DOI":"10.1093\/nar\/gkp373","volume":"37","author":"RS Datta","year":"2009","unstructured":"Datta, R.S., Meacham, C., Samad, B., Neyer, C., Sj\u00f6lander, K.: Berkeley PHOG: PhyloFacts orthology group prediction web server. Nucl. Acids Res. 37, W84\u2013W89 (2009)","journal-title":"Nucl. Acids Res."},{"key":"5_CR9","series-title":"Lecture Notes in Computer Science","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, vol. 6833, pp. 76\u201391. Springer, Heidelberg (2011)"},{"issue":"3","key":"5_CR10","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1109\/31.1748","volume":"35","author":"ES El-Mallah","year":"1988","unstructured":"El-Mallah, E.S., Colbourn, C.J.: The complexity of some edge deletion problems. IEEE Trans. Circ. Syst. 35(3), 354\u2013362 (1988)","journal-title":"IEEE Trans. Circ. Syst."},{"issue":"5","key":"5_CR11","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0168-9525(00)02005-9","volume":"16","author":"WM Fitch","year":"2000","unstructured":"Fitch, W.M.: Homology a personal view on some of the problems. TIG 16(5), 227\u2013231 (2000)","journal-title":"TIG"},{"key":"5_CR12","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.W., Romero-Herrera, A.E., Matsuda, G.: Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences. Syst. Zool. 28, 132\u2013163 (1979)","journal-title":"Syst. Zool."},{"issue":"Supp 10","key":"5_CR13","first-page":"S14","volume":"13","author":"P Gorecki","year":"2011","unstructured":"Gorecki, P., Eulenstein, O.: Algorithms: simultaneous error-correction and rooting for gene tree reconciliation and the gene duplication problem. BMC Bioinf. 13(Supp 10), S14 (2011)","journal-title":"BMC Bioinf."},{"key":"5_CR14","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. 6674, pp. 148\u2013159. Springer, Heidelberg (2011)"},{"issue":"1\u20132","key":"5_CR15","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s00285-012-0525-x","volume":"66","author":"M Hellmuth","year":"2013","unstructured":"Hellmuth, M., Hernandez-Rosales, M., Huber, K., Moulton, V., Stadler, P., Wieseke, N.: Orthology relations, symbolic ultrametrics, and cographs. J. Math. Biol. 66(1\u20132), 399\u2013420 (2013)","journal-title":"J. Math. Biol."},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Hellmuth, M., Wieseke, N., Lechner, M., Middendorf, M., Stadler, P.F., Lenhof, H-P.: Phylogenomics with paralogs. In: PNAS (2014)","DOI":"10.1073\/pnas.1412770112"},{"issue":"Suppl. 19","key":"5_CR17","first-page":"56","volume":"13","author":"M Hernandez-Rosales","year":"2012","unstructured":"Hernandez-Rosales, M., Hellmuth, M., Wieseke, N., Huber, K.T., Moulton, V., Stadler, P.: From event-labeled gene trees to species trees. BMC Bioinf. 13(Suppl. 19), 56 (2012)","journal-title":"BMC Bioinf."},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"D556","DOI":"10.1093\/nar\/gkq1109","volume":"39","author":"J Huerta-Cepas","year":"2011","unstructured":"Huerta-Cepas, J., Capella-Gutierrez, S., Pryszcz, L.P., Denisov, I., Kormes, D., Marcet-Houben, M., Gabald\u00f3n, T.: Phylomedb v3.0: an expanding repository of genome-wide collections of trees, alignments and phylogeny-based orthology and paralogy predictions. Nucl. Acids Res. 39, D556\u2013D560 (2011)","journal-title":"Nucl. Acids Res."},{"issue":"Suppl. 6","key":"5_CR19","doi-asserted-by":"publisher","first-page":"S12","DOI":"10.1186\/1471-2164-15-S6-S12","volume":"15","author":"M Lafond","year":"2014","unstructured":"Lafond, M., El-Mabrouk, N.: Orthology and paralogy constraints: satisfiability and consistency. BMC Genom. 15(Suppl. 6), S12 (2014)","journal-title":"BMC Genom."},{"issue":"Suppl. 15","key":"5_CR20","doi-asserted-by":"publisher","first-page":"S5","DOI":"10.1186\/1471-2105-14-S15-S5","volume":"14","author":"M Lafond","year":"2013","unstructured":"Lafond, M., Semeria, M., Swenson, K.M., Tannier, E., El-Mabrouk, N.: Gene tree correction guided by orthology. BMC Bioinf. 14(Suppl. 15), S5 (2013)","journal-title":"BMC Bioinf."},{"key":"5_CR21","first-page":"261","volume-title":"Error detection and correction of gene trees","author":"M Lafond","year":"2013","unstructured":"Lafond, M., Swenson, K.M., El-Mabrouk, N.: Models and algorithms for genome evolution. In: Chauve, C., El-Mabrouk, N., Tannier, E. (eds.) Error detection and correction of gene trees, pp. 261\u2013285. Springer, Heidelberg (2013)"},{"key":"5_CR22","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1186\/1471-2105-12-124","volume":"12","author":"M Lechner","year":"2011","unstructured":"Lechner, M., Findeib, S.S., Steiner, L., Marz, M., Stadler, P.F., Prohaska, S.J.: Proteinortho: detection of (co-)orthologs in large-scale analysis. BMC Bioinf. 12, 124 (2011)","journal-title":"BMC Bioinf."},{"issue":"2","key":"5_CR23","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is np-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR24","doi-asserted-by":"publisher","first-page":"2178","DOI":"10.1101\/gr.1224503","volume":"13","author":"L Li Jr","year":"2003","unstructured":"Li Jr, L., Stoeckert, C.J., Roos, D.S.: OrthoMCL: identification of ortholog groups for eukaryotic genomes. Genome Res. 13, 2178\u20132189 (2003)","journal-title":"Genome Res."},{"key":"5_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/978-3-642-22685-4_10","volume-title":"Computing and Combinatorics","author":"Y Liu","year":"2011","unstructured":"Liu, Y., Wang, J., Guo, J., Chen, J.: Cograph editing: complexity and parameterized algorithms. In: Fu, B., Du, D.-Z. (eds.) COCOON 2011. LNCS, vol. 6842, pp. 110\u2013121. Springer, Heidelberg (2011)"},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"D377","DOI":"10.1093\/nar\/gks1118","volume":"41","author":"H Mi","year":"2012","unstructured":"Mi, H., Muruganujan, A., Thomas, P.D.: Panther in 2013: modeling the evolution of gene function, and other gene attributes, in the context of phylogenetic trees. Nucl. Acids Res. 41, D377\u2013D386 (2012)","journal-title":"Nucl. Acids Res."},{"key":"5_CR27","volume-title":"Computers and intractability: a guide to the theory of np-completeness","author":"RG Michael","year":"1979","unstructured":"Michael, R.G., David, S.J.: Computers and intractability: a guide to the theory of np-completeness. WH Freeman & Co., San Francisco (1979)"},{"issue":"1","key":"5_CR28","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","volume":"113","author":"A Natanzon","year":"2001","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Appl. Math. 113(1), 109\u2013128 (2001)","journal-title":"Discrete Appl. Math."},{"key":"5_CR29","doi-asserted-by":"publisher","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":"5_CR30","doi-asserted-by":"publisher","first-page":"S3","DOI":"10.1186\/1471-2105-10-S6-S3","volume":"10","author":"S Penel","year":"2009","unstructured":"Penel, S., Arigon, A.M., Dufayard, J.F., Sertier, A.S., Daubin, V., Duret, L., Gouy, M., Perri\u00e8re, G.: Databases of homologous gene families for comparative genomics. BMC Bioinf. 10, S3\u2013S6 (2009)","journal-title":"BMC Bioinf."},{"key":"5_CR31","doi-asserted-by":"publisher","first-page":"e32","DOI":"10.1093\/nar\/gkq953","volume":"39","author":"LP Pryszcz","year":"2011","unstructured":"Pryszcz, L.P., Huerta-Cepas, J., Gabald\u00f3n, T.: MetaPhOrs: orthology and paralogy predictions from multiple phylogenetic evidence using a consistency-based confidence score. Nucl. Acids Res. 39, e32 (2011)","journal-title":"Nucl. Acids Res."},{"key":"5_CR32","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","volume":"53","author":"D Robinson","year":"1981","unstructured":"Robinson, D., Foulds, L.: Comparison of phylogenetic trees. Math. Biosc. 53, 131\u2013147 (1981)","journal-title":"Math. Biosc."},{"issue":"1","key":"5_CR33","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1186\/1748-7188-7-31","volume":"7","author":"KM Swenson","year":"2012","unstructured":"Swenson, K.M., Doroftei, A., El-Mabrouk, N.: Gene tree correction for reconciliation and species tree inference. Alg. Mol. Biol. 7(1), 31 (2012)","journal-title":"Alg. Mol. Biol."},{"key":"5_CR34","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1093\/nar\/28.1.33","volume":"28","author":"RL Tatusov","year":"2000","unstructured":"Tatusov, R.L., Galperin, M.Y., Natale, D.A., Koonin, E.V.: The COG database: a tool for genome-scale analysis of protein functions and evolution. Nucl. Acids Res. 28, 33\u201336 (2000)","journal-title":"Nucl. Acids Res."},{"issue":"8","key":"5_CR35","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1186\/1748-7188-8-12","volume":"8","author":"TH Nguyen","year":"2013","unstructured":"Nguyen, T.H., Ranwez, V., Pointet, S., Chifolleau, A.M., Doyon, J.P., Berry, V.: Reconciliation and local gene tree rearrangement can be of mutual profit. Alg. Mol. Biol. 8(8), 12 (2013)","journal-title":"Alg. Mol. Biol."},{"key":"5_CR36","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1101\/gr.073585.107","volume":"19","author":"AJ Vilella","year":"2009","unstructured":"Vilella, A.J., Severin, J., Ureta-Vidal, A., Heng, L., Durbin, R., Birney, E.: EnsemblCompara gene trees: complete, duplication-aware phylogenetic trees in vertebrates. Gen. Res. 19, 327\u2013335 (2009)","journal-title":"Gen. Res."}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48221-6_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T07:41:27Z","timestamp":1676965287000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48221-6_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662482209","9783662482216"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48221-6_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}