{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:34:40Z","timestamp":1772138080210,"version":"3.50.1"},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Motivation: Scaffolding is often an essential step in a genome assembly process, in which contigs are ordered and oriented using read pairs from a combination of paired-end libraries and longer-range mate-pair libraries. Although a simple idea, scaffolding is unfortunately hard to get right in practice. One source of problems is so-called PE-contamination in mate-pair libraries, in which a non-negligible fraction of the read pairs get the wrong orientation and a much smaller insert size than what is expected. This contamination has been discussed before, in relation to integrated scaffolders, but solutions rely on the orientation being observable, e.g. by finding the junction adapter sequence in the reads. This is not always possible, making orientation and insert size of a read pair stochastic. To our knowledge, there is neither previous work on modeling PE-contamination, nor a study on the effect PE-contamination has on scaffolding quality.<\/jats:p>\n                  <jats:p>Results: We have addressed PE-contamination in an update to our scaffolder BESST. We formulate the problem as an integer linear program which is solved using an efficient heuristic. The new method shows significant improvement over both integrated and stand-alone scaffolders in our experiments. The impact of modeling PE-contamination is quantified by comparing with the previous BESST model. We also show how other scaffolders are vulnerable to PE-contaminated libraries, resulting in an increased number of misassemblies, more conservative scaffolding and inflated assembly sizes.<\/jats:p>\n                  <jats:p>Availability and implementation: The model is implemented in BESST. Source code and usage instructions are found at https:\/\/github.com\/ksahlin\/BESST. BESST can also be downloaded using PyPI.<\/jats:p>\n                  <jats:p>Contact: \u00a0ksahlin@kth.se<\/jats:p>\n                  <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btw064","type":"journal-article","created":{"date-parts":[[2016,3,3]],"date-time":"2016-03-03T21:13:45Z","timestamp":1457039625000},"page":"1925-1932","source":"Crossref","is-referenced-by-count":42,"title":["Assembly scaffolding with PE-contaminated mate-pair libraries"],"prefix":"10.1093","volume":"32","author":[{"given":"Kristoffer","family":"Sahlin","sequence":"first","affiliation":[{"name":"1 Science for Life Laboratory, School of Computer Science and Communication, KTH Royal Institute of Technology, Solna, Sweden,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rayan","family":"Chikhi","sequence":"additional","affiliation":[{"name":"2 CNRS, CRIStAL, UMR 9189, Villeneuve D\u2019ascq 59650, France and"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Arvestad","sequence":"additional","affiliation":[{"name":"3 Swedish e-Science Research Centre, Science for Life Laboratory, and Department of Numerical Analysis and Computer Science, Stockholm University, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2016,3,2]]},"reference":[{"key":"2023020112331772500_btw064-B1","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":"2023020112331772500_btw064-B2","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1186\/1748-7188-8-22","article-title":"Space-efficient and exact de bruijn graph representation based on a bloom filter","volume":"8","author":"Chikhi","year":"2013","journal-title":"Algorithms Mol. Biol"},{"key":"2023020112331772500_btw064-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 Bioinf"},{"key":"2023020112331772500_btw064-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":"2023020112331772500_btw064-B5","doi-asserted-by":"crossref","first-page":"2224","DOI":"10.1101\/gr.126599.111","article-title":"Assemblathon 1: a competitive assessment of de novo short read assembly methods","volume":"21","author":"Earl","year":"2011","journal-title":"Genome Res"},{"key":"2023020112331772500_btw064-B6","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":"2023020112331772500_btw064-B7","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. USA"},{"key":"2023020112331772500_btw064-B8","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1093\/bioinformatics\/btt086","article-title":"QUAST: quality assessment tool for genome assemblies","volume":"29","author":"Gurevich","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020112331772500_btw064-B9","doi-asserted-by":"crossref","first-page":"R42","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":"2023020112331772500_btw064-B10","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1145\/585265.585267","article-title":"The greedy path-merging algorithm for contig scaffolding","volume":"49","author":"Huson","year":"2002","journal-title":"J. ACM"},{"key":"2023020112331772500_btw064-B11","author":"Illumina","year":"2012"},{"key":"2023020112331772500_btw064-B12","doi-asserted-by":"crossref","DOI":"10.1093\/bioinformatics\/bts480","article-title":"Snakemake \u2013 a scalable bioinformatics workflow engine","author":"K\u00f6ster","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020112331772500_btw064-B13","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":"2023020112331772500_btw064-B14","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":"2023020112331772500_btw064-B15","author":"Li","year":"2013"},{"key":"2023020112331772500_btw064-B16","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","article-title":"Fast and accurate long-read alignment with Burrows\u2013Wheeler transform","volume":"26","author":"Li","year":"2010","journal-title":"Bioinformatics"},{"key":"2023020112331772500_btw064-B17","doi-asserted-by":"crossref","DOI":"10.1093\/bioinformatics\/btv211","article-title":"Scaffmatch: Scaffolding algorithm based on maximum weight matching","author":"Mandric","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020112331772500_btw064-B18","doi-asserted-by":"crossref","DOI":"10.1093\/bioinformatics\/btv057","article-title":"Nxtrim: optimized trimming of illumina mate pair reads","author":"O\u2019Connell","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020112331772500_btw064-B19","doi-asserted-by":"crossref","first-page":"2215","DOI":"10.1093\/bioinformatics\/bts441","article-title":"Improved gap size estimation for scaffolding algorithms","volume":"28","author":"Sahlin","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020112331772500_btw064-B20","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1186\/1471-2105-15-281","article-title":"BESST \u2013 efficient scaffolding of large fragmented assemblies","volume":"15","author":"Sahlin","year":"2014","journal-title":"BMC Bioinf"},{"key":"2023020112331772500_btw064-B21","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":"2023020112331772500_btw064-B22","doi-asserted-by":"crossref","first-page":"2669","DOI":"10.1093\/bioinformatics\/btt476","article-title":"The MaSuRCA genome assembler","volume":"29","author":"Zimin","year":"2013","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/13\/1925\/49019650\/bioinformatics_32_13_1925.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/13\/1925\/49019650\/bioinformatics_32_13_1925.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T17:43:39Z","timestamp":1675273419000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/13\/1925\/1742757"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,2]]},"references-count":22,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2016,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw064","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/025650","asserted-by":"object"}]},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,7,1]]},"published":{"date-parts":[[2016,3,2]]}}}