{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T11:03:30Z","timestamp":1649070210307},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2006,5,17]],"date-time":"2006-05-17T00:00:00Z","timestamp":1147824000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2006,6]]},"DOI":"10.1007\/s10878-006-8212-8","type":"journal-article","created":{"date-parts":[[2006,5,22]],"date-time":"2006-05-22T06:21:26Z","timestamp":1148278886000},"page":"387-405","source":"Crossref","is-referenced-by-count":4,"title":["Inapproximability results for the lateral gene transfer problem"],"prefix":"10.1007","volume":"11","author":[{"given":"Bhaskar","family":"Dasgupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Ferrarini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uthra","family":"Gopalakrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nisha Raj","family":"Paryani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,17]]},"reference":[{"issue":"3","key":"8212_CR1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1998) Proof verification and hardness of approximation problems. Journal of the ACM 45(3):501\u2013555","journal-title":"Journal of the ACM"},{"key":"8212_CR2","volume-title":"Complexity and approximation. Combinatorial Optimization Problems and their Approximability Properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti Spaccamela A, Protasi M (1999) Complexity and approximation. Combinatorial Optimization Problems and their Approximability Properties. Springer-Verlag, Berlin"},{"key":"8212_CR3","unstructured":"Berman P, Karpinski M (1998) On some tighter inapproximability results, further improvements. Technical report TR98-065, Electronic Colloquium on Computational Complexity (ECCC); available online from http:\/\/eccc.uni-trier.de\/eccc-reports\/1998\/TR98-065\/index.html.."},{"key":"8212_CR4","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P Berman","year":"1992","unstructured":"Berman P, Schnitger G (1992) On the complexity of approximating the independent set problem. Information and Computation 96:77\u201394","journal-title":"Information and Computation"},{"key":"8212_CR5","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1038\/nrg1000","volume":"4","author":"JR Brown","year":"2003","unstructured":"Brown JR (2003) Ancient horizontal gene transfer. Nature Reviews, Genetics 4:121\u2013132","journal-title":"Nature Reviews, Genetics"},{"key":"8212_CR6","doi-asserted-by":"crossref","unstructured":"Hallett M, Lagergren J (2001) Efficient algorithms for lateral gene transfer problems. In Proc. 5th Annual International Conference on Computational Molecular Biology (RECOMB), Montreal, Canada, pp. 141\u2013148","DOI":"10.1145\/369133.369188"},{"key":"8212_CR7","unstructured":"Hallett M, Lagergren J (2004) Identifying lateral gene transfer events, submitted to journal (available online from http:\/\/www.mcb.mcgill.ca\/~hallett\/Lateral.pdf)"},{"key":"8212_CR8","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson DS (1974) Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9:256\u2013278","journal-title":"Journal of Computer and System Sciences"},{"key":"8212_CR9","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1006\/mpev.1996.0390","volume":"7","author":"RDM Page","year":"1997","unstructured":"Page RDM, Charleston MA (1997) From gene to organismal phylogeny: Reconciled tree and the gene tree\/species tree problem. Molecular Phylogentics and Evolution 7:231\u2013240","journal-title":"Molecular Phylogentics and Evolution"},{"issue":"3","key":"8212_CR10","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes. Journal of Computer and System Sciences 43(3):425\u2013440","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-8212-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-006-8212-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-8212-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:10Z","timestamp":1559261890000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-006-8212-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5,17]]},"references-count":10,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,6]]}},"alternative-id":["8212"],"URL":"https:\/\/doi.org\/10.1007\/s10878-006-8212-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,5,17]]}}}