{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T03:23:14Z","timestamp":1768620194618,"version":"3.49.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,8,17]],"date-time":"2017-08-17T00:00:00Z","timestamp":1502928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Singapore MOE","award":["R-146-000-177-112 and R-146-000-134-112"],"award-info":[{"award-number":["R-146-000-177-112 and R-146-000-134-112"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>\n            By reconciling the phylogenetic tree of a gene family with the corresponding species tree, it is possible to infer lineage-specific duplications and losses with high confidence and hence to annotate orthologs and paralogs. The currently available reconciliation methods for nonbinary gene trees are computationally expensive for genome-scale applications. We present four\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>G<\/jats:italic>\n            |+|\n            <jats:italic>S<\/jats:italic>\n            |) algorithms to reconcile an arbitrary gene tree\n            <jats:italic>G<\/jats:italic>\n            with a binary species tree\n            <jats:italic>S<\/jats:italic>\n            in the duplication, loss, duploss (also known as mutation), and deep coalescence cost models, where |\u00b7 | denotes the number of nodes in a tree. The improvement is achieved through two innovations: a linear-time computation of compressed child-image subtrees and efficient reconstruction of irreducible duplication histories. Our technique for child-image subtree compression also results in an order of magnitude speedup in runtime for the dynamic programming and Wagner parsimony--based methods for tree reconciliation in the affine cost model.\n          <\/jats:p>","DOI":"10.1145\/3088512","type":"journal-article","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T11:49:04Z","timestamp":1503575344000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Reconciliation With Nonbinary Gene Trees Revisited"],"prefix":"10.1145","volume":"64","author":[{"given":"Yu","family":"Zheng","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}]},{"given":"Louxin","family":"Zhang","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2017,8,17]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502796"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bts225"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.141978.112"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tig.2013.07.001"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11809678_26"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02008-7_4"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1089\/106652700750050871"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2012.79"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87989-3_6"},{"key":"e_1_2_2_10_1","volume-title":"Algorithms","author":"Dasgupta Sanjoy","unstructured":"Sanjoy Dasgupta , Christos H. Papadimitriou , and Umesh Vazirani . 2006. Algorithms . McGraw-Hill, Inc. , New York, NY . Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani. 2006. Algorithms. McGraw-Hill, Inc., New York, NY."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/bbr045"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti325"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2006.13.320"},{"key":"e_1_2_2_14_1","volume-title":"Liberles","author":"Eulenstein Oliver","year":"2010","unstructured":"Oliver Eulenstein , Snehalata Huzurbazar , and David A . Liberles . 2010 . Reconciling phylogenetic trees. In Evolution After Gene Duplication. John Wiley 8 Sons, Hoboken, NJ, 185--206. Oliver Eulenstein, Snehalata Huzurbazar, and David A. Liberles. 2010. Reconciling phylogenetic trees. In Evolution After Gene Duplication. John Wiley 8 Sons, Hoboken, NJ, 185--206."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/19.1.83"},{"key":"e_1_2_2_16_1","unstructured":"Joseph Felsenstein. 2004. Inferring Phylogenies. Sinauer Associates Sunderland MA.  Joseph Felsenstein. 2004. Inferring Phylogenies. Sinauer Associates Sunderland MA."},{"key":"e_1_2_2_17_1","first-page":"99","article-title":"Distinguishing homologous from analogous proteins","volume":"19","author":"Fitch Walter M.","year":"1970","unstructured":"Walter M. Fitch . 1970 . Distinguishing homologous from analogous proteins . Systematic Biology 19 , 99 -- 113 . Walter M. Fitch. 1970. Distinguishing homologous from analogous proteins. Systematic Biology 19, 99--113.","journal-title":"Systematic Biology"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/28.2.132"},{"key":"e_1_2_2_19_1","volume-title":"Ponting","author":"Goodstadt Leo","year":"2006","unstructured":"Leo Goodstadt and Chris P . Ponting . 2006 . Phylogenetic reconstruction of orthology, paralogy, and conserved synteny for dog and human. PLoS Computational Biology 2, Article No . e133. Leo Goodstadt and Chris P. Ponting. 2006. Phylogenetic reconstruction of orthology, paralogy, and conserved synteny for dog and human. PLoS Computational Biology 2, Article No. e133."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.019"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.8.754"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature01644"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/bbr030"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33122-0_9"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2009.52"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/46.3.523"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1971.11992886"},{"key":"e_1_2_2_28_1","volume-title":"Eisen","author":"Pollard Daniel A.","year":"2006","unstructured":"Daniel A. Pollard , Venky N. Iyer , Alan M. Moses , and Michael B . Eisen . 2006 . Widespread discordance of gene trees with species tree in Drosophila evidence for incomplete lineage sorting. PLoS Genetics 2, Article No . e173. Daniel A. Pollard, Venky N. Iyer, Alan M. Moses, and Michael B. Eisen. 2006. Widespread discordance of gene trees with species tree in Drosophila evidence for incomplete lineage sorting. PLoS Genetics 2, Article No. e173."},{"key":"e_1_2_2_29_1","volume-title":"McMahon","author":"Sanderson Michael J.","year":"2007","unstructured":"Michael J. Sanderson and Michelle M . McMahon . 2007 . Inferring angiosperm phylogeny from EST data with widespread gene duplication. BMC Evolutionary Biology 7, Article S 3. Michael J. Sanderson and Michelle M. McMahon. 2007. Inferring angiosperm phylogeny from EST data with widespread gene duplication. BMC Evolutionary Biology 7, Article S3."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01681346"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bts386"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.1.92"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.278.5338.631"},{"key":"e_1_2_2_36_1","doi-asserted-by":"crossref","unstructured":"Cuong Than and Luay Nakhleh. 2009. Species tree inference by minimizing deep coalescences. PLoS Computational Biology 5 Article No. e1000501.  Cuong Than and Luay Nakhleh. 2009. Species tree inference by minimizing deep coalescences. PLoS Computational Biology 5 Article No. e1000501.","DOI":"10.1371\/journal.pcbi.1000501"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature06107"},{"key":"e_1_2_2_38_1","volume-title":"Models and Algorithms for Genome Evolution","author":"Warnow Tandy","unstructured":"Tandy Warnow . 2013. Large-scale multiple sequence alignment and phylogeny estimation . In Models and Algorithms for Genome Evolution , Vol. 19 , C. Chauve, N. El-Mabrouk, and E. Tannier, Eds. Springer , London, England, 85--146. Tandy Warnow. 2013. Large-scale multiple sequence alignment and phylogeny estimation. In Models and Algorithms for Genome Evolution, Vol. 19, C. Chauve, N. El-Mabrouk, and E. Tannier, Eds. Springer, London, England, 85--146."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2011.0174"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.1997.4.177"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2011.83"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03780-6_17"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3088512","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3088512","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:07Z","timestamp":1750217407000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3088512"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,17]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3088512"],"URL":"https:\/\/doi.org\/10.1145\/3088512","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,17]]},"assertion":[{"value":"2014-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}