{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:26:15Z","timestamp":1753881975877,"version":"3.41.2"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["CityU 11206120"],"award-info":[{"award-number":["CityU 11206120"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["NSFC 61972329"],"award-info":[{"award-number":["NSFC 61972329"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:p> This paper deals with the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications and lateral gene transfers (LGTs) for a given species tree [Formula: see text] and a given gene tree [Formula: see text]. Previously, [Tofigh A, Hallett M, Lagergren J, Simultaneous identification of duplications and lateral gene transfers, IEEE\/ACM Trans Comput Biol Bioinf 517\u2013535, 2011.] gave a fixed-parameter algorithm for this problem that runs in [Formula: see text] time, where [Formula: see text] is the number of vertices in [Formula: see text], [Formula: see text] is the number of vertices in [Formula: see text], and [Formula: see text] is the minimum cost of an LCA-reconciliation between [Formula: see text] and [Formula: see text]. In this paper, by refining their algorithm, we obtain a new one for the same problem that finds and outputs the solutions in a compact form within [Formula: see text] time. In the most interesting case where [Formula: see text], our algorithm is [Formula: see text] times faster. <\/jats:p>","DOI":"10.1142\/s0219720021500335","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T03:26:41Z","timestamp":1635391601000},"source":"Crossref","is-referenced-by-count":0,"title":["Identifying duplications and lateral gene transfers simultaneously and rapidly"],"prefix":"10.1142","volume":"20","author":[{"given":"Zhi-Zhong","family":"Chen","sequence":"first","affiliation":[{"name":"Division of Information System Design, Tokyo Denki University, Hatoyama Saitama 350-0394, Japan"}]},{"given":"Fei","family":"Deng","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong"}]},{"given":"Lusheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong"}]}],"member":"219","published-online":{"date-parts":[[2021,12,9]]},"reference":[{"key":"S0219720021500335BIB001","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2010.14"},{"key":"S0219720021500335BIB002","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/46.3.523"},{"key":"S0219720021500335BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/S0025-5564(97)10012-8"},{"key":"S0219720021500335BIB004","doi-asserted-by":"publisher","DOI":"10.1145\/332306.332359"},{"key":"S0219720021500335BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/11732990_18"},{"key":"S0219720021500335BIB006","doi-asserted-by":"publisher","DOI":"10.1006\/mpev.1996.0071"},{"key":"S0219720021500335BIB007","doi-asserted-by":"publisher","DOI":"10.2307\/2412519"},{"issue":"1","key":"S0219720021500335BIB008","first-page":"58","volume":"43","author":"Page R","year":"1994","journal-title":"Syst Biol"},{"key":"S0219720021500335BIB009","doi-asserted-by":"publisher","DOI":"10.1006\/mpev.1996.0390"},{"key":"S0219720021500335BIB010","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798343362"},{"key":"S0219720021500335BIB011","doi-asserted-by":"publisher","DOI":"10.1145\/369133.369188"},{"key":"S0219720021500335BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/11533719_11"},{"key":"S0219720021500335BIB013","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1186\/1471-2105-11-326","volume":"11","author":"Manolo G","year":"2010","journal-title":"BMC Bioinf"},{"key":"S0219720021500335BIB014","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl452"},{"key":"S0219720021500335BIB015","first-page":"279","volume-title":"Proc. 8th Pacific Symp Biocomputing (PSB03)","author":"Addario-Berry L","year":"2003"},{"key":"S0219720021500335BIB016","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2148-6-15"},{"key":"S0219720021500335BIB017","doi-asserted-by":"publisher","DOI":"10.1145\/974614.974656"},{"key":"S0219720021500335BIB018","first-page":"93","volume-title":"Proc. RECOMB International Workshop on Comp. Genomics","author":"Doyon J","year":"2011"},{"key":"S0219720021500335BIB019","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2012.79"},{"key":"S0219720021500335BIB020","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720021500335","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T08:15:07Z","timestamp":1646295307000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720021500335"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,9]]},"references-count":20,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["10.1142\/S0219720021500335"],"URL":"https:\/\/doi.org\/10.1142\/s0219720021500335","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"type":"print","value":"0219-7200"},{"type":"electronic","value":"1757-6334"}],"subject":[],"published":{"date-parts":[[2021,12,9]]},"article-number":"2150033"}}