{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T10:13:19Z","timestamp":1778667199002,"version":"3.51.4"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2018,12]]},"abstract":"<jats:p> The genomic scaffold filling problem has attracted a lot of attention recently. The problem is on filling an incomplete sequence (scaffold) [Formula: see text] into [Formula: see text], with respect to a complete reference genome [Formula: see text], such that the number of common\/shared adjacencies between [Formula: see text] and [Formula: see text] is maximized. The problem is NP-complete, and admits a constant-factor approximation. However, the sequence input [Formula: see text] is not quite practical and does not fit most of the real datasets (where a scaffold is more often given as a list of contigs). In this paper, we revisit the genomic scaffold filling problem by considering this important case when a scaffold [Formula: see text] is given, the missing genes can only be inserted in between the contigs, and the objective is to maximize the number of common adjacencies between [Formula: see text] and the filled genome [Formula: see text]. For this problem, we present a simple NP-completeness proof, we then present a factor-2 approximation algorithm. <\/jats:p>","DOI":"10.1142\/s0219720018500221","type":"journal-article","created":{"date-parts":[[2018,8,20]],"date-time":"2018-08-20T01:46:45Z","timestamp":1534729605000},"page":"1850022","source":"Crossref","is-referenced-by-count":4,"title":["A 2-approximation algorithm for the contig-based genomic scaffold filling problem"],"prefix":"10.1142","volume":"16","author":[{"given":"Haitao","family":"Jiang","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Shandong University, Jinan, Shandong, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Letu","family":"Qingge","sequence":"additional","affiliation":[{"name":"Gianforte School of Computing, Montana State University, Bozeman, MT 59717, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daming","family":"Zhu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Shandong University, Jinan, Shandong, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[{"name":"Gianforte School of Computing, Montana State University, Bozeman, MT 59717, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2019,1,7]]},"reference":[{"key":"S0219720018500221BIB001","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2012-13-6-r56"},{"key":"S0219720018500221BIB002","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-015-0663-4"},{"key":"S0219720018500221BIB003","doi-asserted-by":"publisher","DOI":"10.1126\/science.1180614"},{"key":"S0219720018500221BIB004","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-11-304"},{"key":"S0219720018500221BIB005","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti535"},{"key":"S0219720018500221BIB006","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2012.57"},{"key":"S0219720018500221BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9077-1"},{"key":"S0219720018500221BIB009","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00175"},{"key":"S0219720018500221BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.07.011"},{"key":"S0219720018500221BIB016","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2013.100"},{"key":"S0219720018500221BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9938-9"},{"key":"S0219720018500221BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.12.005"},{"key":"S0219720018500221BIB020","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585267"},{"key":"S0219720018500221BIB021","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2014-15-3-r42"},{"key":"S0219720018500221BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5298-9_9"},{"key":"S0219720018500221BIB026","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"S0219720018500221BIB027","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2017-1555"},{"key":"S0219720018500221BIB028","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey MR","year":"1979"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720018500221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:48:10Z","timestamp":1565124490000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720018500221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12]]},"references-count":18,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2019,1,7]]},"published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.1142\/S0219720018500221"],"URL":"https:\/\/doi.org\/10.1142\/s0219720018500221","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12]]}}}