{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T00:53:42Z","timestamp":1750985622418,"version":"3.37.3"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2016,9,14]],"date-time":"2016-09-14T00:00:00Z","timestamp":1473811200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61232001","61420106009","61379108","61602156"],"award-info":[{"award-number":["61232001","61420106009","61379108","61602156"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"The National Science Fund for Excellent Young Scholars","award":["61622213"],"award-info":[{"award-number":["61622213"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>While aiming to determine orientations and orders of fragmented contigs, scaffolding is an essential step of assembly pipelines and can make assembly results more complete. Most existing scaffolding tools adopt scaffold graph approaches. However, due to repetitive regions in genome, sequencing errors and uneven sequencing depth, constructing an accurate scaffold graph is still a challenge task.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>In this paper, we present a novel algorithm (called BOSS), which employs paired reads for scaffolding. To construct a scaffold graph, BOSS utilizes the distribution of insert size to decide whether an edge between two vertices (contigs) should be added and how an edge should be weighed. Moreover, BOSS adopts an iterative strategy to detect spurious edges whose removal can guarantee no contradictions in the scaffold graph. Based on the scaffold graph constructed, BOSS employs a heuristic algorithm to sort vertices (contigs) and then generates scaffolds. The experimental results demonstrate that BOSS produces more satisfactory scaffolds, compared with other popular scaffolding tools on real sequencing data of four genomes.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and Implementation<\/jats:title><jats:p>BOSS is publicly available for download at https:\/\/github.com\/bioinfomaticsCSU\/BOSS.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btw597","type":"journal-article","created":{"date-parts":[[2016,9,16]],"date-time":"2016-09-16T00:10:35Z","timestamp":1473984635000},"page":"169-176","source":"Crossref","is-referenced-by-count":31,"title":["BOSS: a novel scaffolding algorithm based on an optimized scaffold graph"],"prefix":"10.1093","volume":"33","author":[{"given":"Junwei","family":"Luo","sequence":"first","affiliation":[{"name":"School of Information Science and Engineering, Central South University, ChangSha, China"},{"name":"College of Computer Science and Technology, Henan Polytechnic University, JiaoZuo, China"}]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Information Science and Engineering, Central South University, ChangSha, China"}]},{"given":"Zhen","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Information Science and Engineering, Central South University, ChangSha, China"}]},{"given":"Min","family":"Li","sequence":"additional","affiliation":[{"name":"School of Information Science and Engineering, Central South University, ChangSha, China"}]},{"given":"Fang-Xiang","family":"Wu","sequence":"additional","affiliation":[{"name":"Division of Biomedical Engineering, University of Saskatchewan, Saskatchewan, Canada"}]}],"member":"286","published-online":{"date-parts":[[2016,9,14]]},"reference":[{"key":"2023020204303986200_btw597-B1","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1093\/bioinformatics\/btv548","article-title":"ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction","volume":"32","author":"Bodily","year":"2016","journal-title":"Bioinformatics"},{"key":"2023020204303986200_btw597-B2","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1093\/bioinformatics\/btq683","article-title":"Scaffolding pre-assembled contigs using SSPACE","volume":"27","author":"Boetzer","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020204303986200_btw597-B3","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1186\/1471-2105-11-345","article-title":"SOPRA: scaffolding algorithm for paired reads via statistical optimization","volume":"11","author":"Dayarian","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023020204303986200_btw597-B4","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1093\/bioinformatics\/bts716","article-title":"SCARPA: scaffolding reads with practical algorithms","volume":"29","author":"Donmez","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020204303986200_btw597-B5","doi-asserted-by":"crossref","first-page":"1681","DOI":"10.1089\/cmb.2011.0170","article-title":"Opera: reconstructing optimal genomic scaffolds with high-throughput paired-end sequences","volume":"18","author":"Gao","year":"2011","journal-title":"J. Comput. Biol"},{"key":"2023020204303986200_btw597-B6","doi-asserted-by":"crossref","first-page":"1513","DOI":"10.1073\/pnas.1017351108","article-title":"High-quality draft assemblies of mammalian genomes from massively parallel sequence data","volume":"108","author":"Gnerre","year":"2011","journal-title":"Proc. Natl. Acad. Sci. U. S. A"},{"key":"2023020204303986200_btw597-B7","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1109\/TST.2013.6616523","article-title":"De novo assembly methods for next generation sequencing data","volume":"5","author":"He","year":"2013","journal-title":"Tsinghua Sci. Technol"},{"key":"2023020204303986200_btw597-B8","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1186\/gb-2014-15-3-r42","article-title":"A comprehensive evaluation of assembly scaffolding tools","volume":"15","author":"Hunt","year":"2014","journal-title":"Genome Biol"},{"key":"2023020204303986200_btw597-B9","doi-asserted-by":"crossref","first-page":"2964","DOI":"10.1093\/bioinformatics\/btr520","article-title":"Bambus 2: scaffolding metagenomes","volume":"31","author":"Koren","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020204303986200_btw597-B10","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol"},{"key":"2023020204303986200_btw597-B11","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/nmeth.1923","article-title":"Fast gapped-read alignment with Bowtie 2","volume":"9","author":"Langmead","year":"2012","journal-title":"Nat. Methods"},{"key":"2023020204303986200_btw597-B12","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows-Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020204303986200_btw597-B13","article-title":"ISEA: iterative seed-extension algorithm for de novo assembly using paired-end information and insert size distribution","author":"Li","year":"2016","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf"},{"key":"2023020204303986200_btw597-B14","doi-asserted-by":"crossref","first-page":"S9","DOI":"10.1186\/1471-2105-15-S9-S9","article-title":"Ilp-based maximum likelihood genome scaffolding","volume":"15","author":"Lindsay","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023020204303986200_btw597-B15","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1186\/2047-217X-1-18","article-title":"SOAPdenovo2: an empirically improved memory-efficient short-read de novo assembler","volume":"1","author":"Luo","year":"2012","journal-title":"GigaScience"},{"key":"2023020204303986200_btw597-B16","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1093\/bioinformatics\/btu762","article-title":"EPGA: de novo assembly using the distributions of reads and insert size","volume":"31","author":"Luo","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020204303986200_btw597-B17","doi-asserted-by":"crossref","first-page":"3988","DOI":"10.1093\/bioinformatics\/btv487","article-title":"EPGA2: memory-efficient de novo assembler","volume":"31","author":"Luo","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020204303986200_btw597-B18","doi-asserted-by":"crossref","first-page":"2632","DOI":"10.1093\/bioinformatics\/btv211","article-title":"ScaffMatch: Scaffolding Algorithm Based on Maximum Weight Matching","volume":"31","author":"Mandric","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020204303986200_btw597-B19","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1186\/1471-2105-15-281","article-title":"Besst-efficient scaffolding of large fragmented assemblies","volume":"15","author":"Sahlin","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023020204303986200_btw597-B20","doi-asserted-by":"crossref","first-page":"3259","DOI":"10.1093\/bioinformatics\/btr562","article-title":"Fast scaffolding with small independent mixed integer programs","volume":"27","author":"Salmela","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020204303986200_btw597-B21","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1101\/gr.089532.108","article-title":"ABySS: a parallel assembler for short-read sequence data","volume":"19","author":"Simpson","year":"2009","journal-title":"Genome Res"},{"key":"2023020204303986200_btw597-B22","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1101\/gr.131383.111","article-title":"GAGE: a critical evaluation of genome assemblies and assembly algorithms","volume":"22","author":"Salzberg","year":"2012","journal-title":"Genome Res"},{"key":"2023020204303986200_btw597-B23","doi-asserted-by":"crossref","first-page":"549C556","DOI":"10.1101\/gr.126953.111","article-title":"Efficient de novo assembly of large genomes using compressed data structures","volume":"22","author":"Simpson","year":"2012","journal-title":"Genome Res"},{"key":"2023020204303986200_btw597-B24","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1101\/gr.074492.107","article-title":"Velvet: algorithms for de novo short-read assembly using de Bruijn graphs","volume":"18","author":"Zerbino","year":"2008","journal-title":"Genome Res"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/2\/169\/49037270\/bioinformatics_33_2_169.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/2\/169\/49037270\/bioinformatics_33_2_169.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T04:16:45Z","timestamp":1692505005000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/33\/2\/169\/2525706"}},"subtitle":[],"editor":[{"given":"John","family":"Hancock","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2016,9,14]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw597","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2017,1,15]]},"published":{"date-parts":[[2016,9,14]]}}}