{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T11:30:26Z","timestamp":1763724626327,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":23,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T00:00:00Z","timestamp":1666310400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"The Natural Science Foundation of Shandong Province","award":["ZR2018MF012"],"award-info":[{"award-number":["ZR2018MF012"]}]},{"name":"The National Natural Science Foundation of China","award":["61902221"],"award-info":[{"award-number":["61902221"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,10,21]]},"DOI":"10.1145\/3565387.3565409","type":"proceedings-article","created":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T01:47:11Z","timestamp":1670982431000},"page":"1-5","source":"Crossref","is-referenced-by-count":2,"title":["A New Approximation Algorithm for the Contig-Based One-Sided Repetitive Genomic Scaffold Filling Problem"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1803-4236","authenticated-orcid":false,"given":"Nan","family":"Liu","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Shandong Jianzhu University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0593-5206","authenticated-orcid":false,"given":"Yongqi","family":"Zhu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Shandong Jianzhu University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0920-6497","authenticated-orcid":false,"given":"Shenghua","family":"Li","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Shandong Jianzhu University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,12,13]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"36","article-title":"Survey on sequency assembly algorithms in high-throughput sequencing[J].","volume":"2019","unstructured":"ZHOU W X, SHI H H . Survey on sequency assembly algorithms in high-throughput sequencing[J]. Computer Science , 2019 ,46(05): 36 - 43 . ZHOU W X, SHI H H. Survey on sequency assembly algorithms in high-throughput sequencing[J].Computer Science,2019,46(05):36-43.","journal-title":"Computer Science"},{"key":"e_1_3_2_1_2_1","first-page":"143","article-title":"Benchmark of gene prediction software based on metagenomic long fragments[J]","volume":"39","year":"2019","unstructured":"LI R L, SHANG Q M, HAN X Y, ZHANG Y, ZHU H D.LI W Z . Benchmark of gene prediction software based on metagenomic long fragments[J] . Journal of Computer Applications , 2019 , 39 (S1): 143 - 149 . LI R L, SHANG Q M, HAN X Y, ZHANG Y, ZHU H D.LI W Z. Benchmark of gene prediction software based on metagenomic long fragments[J]. Journal of Computer Applications, 2019,39(S1):143-149.","journal-title":"Journal of Computer Applications"},{"key":"e_1_3_2_1_3_1","volume-title":"A polynomial time solution for permutation scaffold filling[C]\/\/10th Annual International Conference on Combinatorial Optimization and Applications","author":"Liu N","year":"2016","unstructured":"Liu N , Zou P , Zhu B H . A polynomial time solution for permutation scaffold filling[C]\/\/10th Annual International Conference on Combinatorial Optimization and Applications . Heidelberg : Springer Verlag , 2016 : 782-789. Liu N, Zou P, Zhu B H. A polynomial time solution for permutation scaffold filling[C]\/\/10th Annual International Conference on Combinatorial Optimization and Applications. Heidelberg: Springer Verlag, 2016: 782-789."},{"issue":"1","key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","first-page":"29","DOI":"10.4161\/sysb.24470","article-title":"Big data challenges and opportunities in high-throughput sequencing[J]","volume":"1","author":"Matthew Ward","year":"2013","unstructured":"R Matthew Ward , Robert Schmieder, Gareth Highnam , David Mittelman . Big data challenges and opportunities in high-throughput sequencing[J] . Systems Biomedicine , 2013 , 1 ( 1 ): 29 - 34 . R Matthew Ward, Robert Schmieder, Gareth Highnam, David Mittelman. Big data challenges and opportunities in high-throughput sequencing[J]. Systems Biomedicine, 2013,1(1): 29-34.","journal-title":"Systems Biomedicine"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Adriana Mu\u00f1oz Chunfang Zheng Qian Zhu Victor A Albert Steve Rounsley David Sankoff. Scaffold filling contig fusion and comparative gene order inference[J]. BioMed Central 2010 11(1): 304.  Adriana Mu\u00f1oz Chunfang Zheng Qian Zhu Victor A Albert Steve Rounsley David Sankoff. Scaffold filling contig fusion and comparative gene order inference[J]. BioMed Central 2010 11(1):304.","DOI":"10.1186\/1471-2105-11-304"},{"key":"e_1_3_2_1_6_1","volume-title":"Scaffold Filling under the Breakpoint and Related Distance[J]","author":"Haitao Jiang","year":"2012","unstructured":"Haitao Jiang , Chunfang Zheng, David Sankoff , Binhai Zhu. Scaffold Filling under the Breakpoint and Related Distance[J] . IEEE\/ACM Transactions on Computational Biology and Bioinformastics(TCBB) . 2012 ,9(4):1220-1229. Haitao Jiang, Chunfang Zheng, David Sankoff, Binhai Zhu. Scaffold Filling under the Breakpoint and Related Distance[J]. IEEE\/ACM Transactions on Computational Biology and Bioinformastics(TCBB).2012,9(4):1220-1229."},{"key":"e_1_3_2_1_7_1","volume-title":"On the approximability of comparing genomes with duplicates[C]\/\/2nd International Workshop on Algorithms and Computation","author":"Angibaud S","year":"2008","unstructured":"Angibaud S , Fertin G , Rusu I , On the approximability of comparing genomes with duplicates[C]\/\/2nd International Workshop on Algorithms and Computation . Heidelberg : Springer Verlag , 2008 : 34-45. Angibaud S, Fertin G, Rusu I, On the approximability of comparing genomes with duplicates[C]\/\/2nd International Workshop on Algorithms and Computation. Heidelberg: Springer Verlag, 2008: 34-45."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","first-page":"1220","DOI":"10.1109\/TCBB.2012.57","article-title":"2012. Scaffold filling under the breakpoint, related distances","author":"Jiang H. T.","year":"2012","unstructured":"Jiang , H. T. , Zheng , C. F. , Sankoff , D. and Zhu , B. H . 2012. Scaffold filling under the breakpoint, related distances . IEEE\/ACM Transactions on Computational Biology and Bioinformatics, ( 2012 ), 9(4), 1220 - 1229 . Jiang, H. T., Zheng, C. F., Sankoff, D. and Zhu, B. H. 2012. Scaffold filling under the breakpoint, related distances. IEEE\/ACM Transactions on Computational Biology and Bioinformatics, (2012), 9(4), 1220-1229.","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics, ("},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-11-304"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","article-title":"2005. Efficient sorting of genomic permutations by translocation, inversion and block interchange","volume":"21","author":"Yancopoulos S.","year":"2005","unstructured":"Yancopoulos , S. , Attie , O. and Friedberg , R . 2005. Efficient sorting of genomic permutations by translocation, inversion and block interchange . BMC Bioinformatics , 2005 , 21 : 3340 - 3346 . Yancopoulos, S., Attie, O. and Friedberg, R. 2005. Efficient sorting of genomic permutations by translocation, inversion and block interchange. BMC Bioinformatics, 2005,21: 3340-3346.","journal-title":"BMC Bioinformatics"},{"key":"e_1_3_2_1_11_1","volume-title":"The approximability of the exemplar breakpoint distance problem[C]\/\/Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management","author":"Chen Z X","year":"2006","unstructured":"Chen Z X , Fu B , Zhu B H . The approximability of the exemplar breakpoint distance problem[C]\/\/Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management . Heidelberg : Springer Verlag , 2006 : 291-302. Chen Z X, Fu B, Zhu B H. The approximability of the exemplar breakpoint distance problem[C]\/\/Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management. Heidelberg: Springer Verlag, 2006: 291-302."},{"key":"e_1_3_2_1_12_1","volume-title":"The exemplar breakpoint distance for non-trivial genomes cannot be approximated[C]\/\/Proceedings of the 3rd International Workshop on Algorithms and Computation","author":"Blin G","year":"2009","unstructured":"Blin G , Fertin G , Sikora F , The exemplar breakpoint distance for non-trivial genomes cannot be approximated[C]\/\/Proceedings of the 3rd International Workshop on Algorithms and Computation . Heidelberg : Springer Verlag , 2009 : 357-368. Blin G, Fertin G, Sikora F, The exemplar breakpoint distance for non-trivial genomes cannot be approximated[C]\/\/Proceedings of the 3rd International Workshop on Algorithms and Computation. Heidelberg: Springer Verlag, 2009: 357-368."},{"key":"e_1_3_2_1_13_1","volume-title":"Zhu","author":"Jiang H.","year":"2011","unstructured":"Jiang , H. , Zhong , F. , Zhu , B. : Filling scaffolds with gene repetitions: maximizing the number of adjacencies. Springer , Heidelberg 2011 ,6661: 55-64. Jiang, H., Zhong, F., Zhu, B.: Filling scaffolds with gene repetitions: maximizing the number of adjacencies. Springer, Heidelberg 2011,6661:55-64."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2013.100"},{"key":"e_1_3_2_1_15_1","first-page":"98","article-title":"Quick greedy computation for minimum common string partition[J]","volume":"2014","author":"Isaac Goldstein","unstructured":"Isaac Goldstein , Moshe Lewenstein . Quick greedy computation for minimum common string partition[J] . Theoretical Computer Science , 2014 ,542: 98 - 107 . Isaac Goldstein, Moshe Lewenstein. Quick greedy computation for minimum common string partition[J]. Theoretical Computer Science,2014,542: 98-107.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Marek Chrobak Petr Kolman Ji\u0159\u00ed Sgall. The greedy algorithm for the minimum common string partition problem[J]. ACM Transactions on Algorithms (TALG) 2005 1(2): 350-366.  Marek Chrobak Petr Kolman Ji\u0159\u00ed Sgall. The greedy algorithm for the minimum common string partition problem[J]. ACM Transactions on Algorithms (TALG) 2005 1(2): 350-366.","DOI":"10.1145\/1103963.1103971"},{"key":"e_1_3_2_1_17_1","volume-title":"Jiang","author":"Ma J.","year":"2016","unstructured":"Ma , J. , Jiang , H. : Notes on the 6\/5 -approximation algorithm for one-sided scaffold filling. Springer , Heidelberg, 2016 :145\u2013157. Ma, J., Jiang, H.: Notes on the 6\/5 -approximation algorithm for one-sided scaffold filling. Springer, Heidelberg,2016:145\u2013157."},{"key":"e_1_3_2_1_18_1","volume-title":"Algorithms and Hardness for Scaffold Filling to Maximize Increased Duo-preservations.[J]","author":"Ma Jingjing","year":"2021","unstructured":"Ma Jingjing , Jiang Haitao, Zhu Daming , Yang Runmin. Algorithms and Hardness for Scaffold Filling to Maximize Increased Duo-preservations.[J] . IEEE\/ACM transactions on computational biology and bioinformatics, 2021 :251-259. Ma Jingjing, Jiang Haitao, Zhu Daming, Yang Runmin. Algorithms and Hardness for Scaffold Filling to Maximize Increased Duo-preservations.[J]. IEEE\/ACM transactions on computational biology and bioinformatics,2021:251-259."},{"key":"e_1_3_2_1_19_1","volume-title":"Genomic scaffold filling: a progress report[C]\/\/10th International Workshop on Frontiers in Algorithmics","author":"Zhu B H","year":"2016","unstructured":"Zhu B H . Genomic scaffold filling: a progress report[C]\/\/10th International Workshop on Frontiers in Algorithmics . Heidelberg : Springer Verlag , 2016 : 8-16. Zhu B H. Genomic scaffold filling: a progress report[C]\/\/10th International Workshop on Frontiers in Algorithmics. Heidelberg: Springer Verlag, 2016: 8-16."},{"key":"e_1_3_2_1_20_1","volume-title":"Genomic scaffold filling revisited[C]\/\/27th Annual Symposium on Combinatorial Pattern Matching","author":"Jiang H T","year":"2016","unstructured":"Jiang H T , Fan C L , Yang B T , Genomic scaffold filling revisited[C]\/\/27th Annual Symposium on Combinatorial Pattern Matching , Dagstuhl : Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016 :1-13. Jiang H T, Fan C L, Yang B T, Genomic scaffold filling revisited[C]\/\/27th Annual Symposium on Combinatorial Pattern Matching, Dagstuhl: Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing,2016:1-13."},{"key":"e_1_3_2_1_21_1","article-title":"algorithm for the contig-based genomic scaffold filling problem[J]","volume":"2018","author":"Jiang H T","unstructured":"Jiang H T , Qingge L T , Zhu D M , A 2-approximation algorithm for the contig-based genomic scaffold filling problem[J] . Journal of Bioinformatics and Computational Biology . 2018 , 16(6). Jiang H T, Qingge L T, Zhu D M, A 2-approximation algorithm for the contig-based genomic scaffold filling problem[J]. Journal of Bioinformatics and Computational Biology.2018, 16(6).","journal-title":"Journal of Bioinformatics and Computational Biology"},{"key":"e_1_3_2_1_22_1","volume-title":"Beyond adjacency maximization: Scaffold filling for new string distances[C]\/\/28th Annual Symposium on Combinatorial Pattern Matching. Dagstuhl: Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH","author":"Bulteau L","year":"2017","unstructured":"Bulteau L , Fertin G , Komusiewicz C. Beyond adjacency maximization: Scaffold filling for new string distances[C]\/\/28th Annual Symposium on Combinatorial Pattern Matching. Dagstuhl: Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH , Dagstuhl Publishing , 2017 . Bulteau L, Fertin G, Komusiewicz C. Beyond adjacency maximization: Scaffold filling for new string distances[C]\/\/28th Annual Symposium on Combinatorial Pattern Matching. Dagstuhl: Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017."},{"key":"e_1_3_2_1_23_1","first-page":"7","article-title":"A new approximation algorithm for contig-based genomic scaffold filling[J]","volume":"2021","author":"Tan Guanlan","unstructured":"Tan Guanlan , Feng Qilong, Meng Xiangzhong , Wang Jianxin . A new approximation algorithm for contig-based genomic scaffold filling[J] . Theoretical Computer Science , 2021 ,853: 7 - 15 . Tan Guanlan, Feng Qilong, Meng Xiangzhong, Wang Jianxin. A new approximation algorithm for contig-based genomic scaffold filling[J]. Theoretical Computer Science,2021,853:7-15.","journal-title":"Theoretical Computer Science"}],"event":{"name":"CSAE 2022: The 6th International Conference on Computer Science and Application Engineering","acronym":"CSAE 2022","location":"Virtual Event China"},"container-title":["The 6th International Conference on Computer Science and Application Engineering"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3565387.3565409","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3565387.3565409","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:13Z","timestamp":1750178233000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3565387.3565409"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,21]]},"references-count":23,"alternative-id":["10.1145\/3565387.3565409","10.1145\/3565387"],"URL":"https:\/\/doi.org\/10.1145\/3565387.3565409","relation":{},"subject":[],"published":{"date-parts":[[2022,10,21]]}}}