{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T00:41:13Z","timestamp":1649119273353},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2018,10]]},"abstract":"<jats:p> Metagenomic studies identify the species present in an environmental sample usually by using procedures that match molecular sequences, e.g. genes, with the species taxonomy. Here, we first formulate the problem of gene-species matching in the parsimony framework using binary phylogenetic gene and species trees under the deep coalescence cost and the assumption that each gene is paired uniquely with one species. In particular, we solve the problem in the cases when one of the trees is a caterpillar. Next, we propose a dynamic programming algorithm, which solves the problem exactly, however, its time and space complexity is exponential. Next, we generalize the problem to include non-binary trees and show the solution for caterpillar trees. We then propose time and space-efficient heuristic algorithms for solving the gene-species matching problem for any input trees. Finally, we present the results of computational experiments on simulated and empirical datasets consisting of binary tree pairs. <\/jats:p>","DOI":"10.1142\/s0219720018400218","type":"journal-article","created":{"date-parts":[[2018,9,20]],"date-time":"2018-09-20T03:24:20Z","timestamp":1537413860000},"page":"1840021","source":"Crossref","is-referenced-by-count":1,"title":["Minimizing the deep coalescence cost"],"prefix":"10.1142","volume":"16","author":[{"given":"Dawid","family":"D\u0105bkowski","sequence":"first","affiliation":[{"name":"Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Banacha 2, Warsaw 02-097, Poland"}]},{"given":"Pawe\u0142","family":"Tabaszewski","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Banacha 2, Warsaw 02-097, Poland"}]},{"given":"Pawe\u0142","family":"G\u00f3recki","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Banacha 2, Warsaw 02-097, Poland"}]}],"member":"219","published-online":{"date-parts":[[2018,11,12]]},"reference":[{"key":"S0219720018400218BIB001","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/978-3-319-19048-8_4","volume-title":"Bioinformatics Research and Applications","author":"Betkier A","year":"2015"},{"key":"S0219720018400218BIB003","doi-asserted-by":"publisher","DOI":"10.1080\/10635150701405560"},{"key":"S0219720018400218BIB004","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-13-S10-S11"},{"key":"S0219720018400218BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32241-9_45"},{"issue":"1","key":"S0219720018400218BIB006","first-page":"231","volume":"11","author":"G\u00f3recki P","year":"2014","journal-title":"IEEE\/ACM TCBB"},{"key":"S0219720018400218BIB007","first-page":"155","volume":"1","author":"G\u00f3recki P","year":"2015","journal-title":"IEEE\/ACM TCBB"},{"issue":"2","key":"S0219720018400218BIB008","first-page":"552","volume":"10","author":"G\u00f3recki P","year":"2013","journal-title":"IEEE\/ACM TCBB"},{"key":"S0219720018400218BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.019"},{"issue":"9","key":"S0219720018400218BIB010","first-page":"2033","volume":"59","author":"Jennings W","year":"2005","journal-title":"Evolution"},{"key":"S0219720018400218BIB011","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/46.3.523"},{"issue":"5","key":"S0219720018400218BIB012","first-page":"1571","volume":"15","author":"Mykowiecka A","year":"2018","journal-title":"IEEE\/ACM TCBB"},{"key":"S0219720018400218BIB013","volume-title":"Molecular Evolution: A Phylogenetic Approach","author":"Page RDM","year":"1998"},{"key":"S0219720018400218BIB014","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkm1005"},{"key":"S0219720018400218BIB015","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1000501"},{"key":"S0219720018400218BIB016","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2010.0102"},{"issue":"1","key":"S0219720018400218BIB017","first-page":"61","volume":"10","author":"Than CV","year":"2013","journal-title":"IEEE\/ACM TCBB"},{"key":"S0219720018400218BIB018","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2008.0092"},{"key":"S0219720018400218BIB019","doi-asserted-by":"publisher","DOI":"10.1101\/gr.161968.113"},{"key":"S0219720018400218BIB020","doi-asserted-by":"publisher","DOI":"10.1098\/rstb.1925.0002"},{"key":"S0219720018400218BIB021","first-page":"1685","volume":"8","author":"Zhang L","year":"2011","journal-title":"IEEE\/ACM TCBB"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720018400218","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T13:35:09Z","timestamp":1565098509000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720018400218"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10]]},"references-count":20,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2018,11,12]]},"published-print":{"date-parts":[[2018,10]]}},"alternative-id":["10.1142\/S0219720018400218"],"URL":"https:\/\/doi.org\/10.1142\/s0219720018400218","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10]]}}}