{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T21:35:45Z","timestamp":1770413745487,"version":"3.49.0"},"reference-count":18,"publisher":"Oxford University Press (OUP)","issue":"17","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: One of the important steps of genome assembly is scaffolding, in which contigs are linked using information from read-pairs. Scaffolding provides estimates about the order, relative orientation and distance between contigs. We have found that contig distance estimates are generally strongly biased and based on false assumptions. Since erroneous distance estimates can mislead in subsequent analysis, it is important to provide unbiased estimation of contig distance.<\/jats:p>\n               <jats:p>Results: In this article, we show that state-of-the-art programs for scaffolding are using an incorrect model of gap size estimation. We discuss why current maximum likelihood estimators are biased and describe what different cases of bias we are facing. Furthermore, we provide a model for the distribution of reads that span a gap and derive the maximum likelihood equation for the gap length. We motivate why this estimate is sound and show empirically that it outperforms gap estimators in popular scaffolding programs. Our results have consequences both for scaffolding software, structural variation detection and for library insert-size estimation as is commonly performed by read aligners.<\/jats:p>\n               <jats:p>Availability: A reference implementation is provided at https:\/\/github.com\/SciLifeLab\/gapest<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are availible at Bioinformatics online.<\/jats:p>\n               <jats:p>Contact: \u00a0ksahlin@csc.kth.se<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts441","type":"journal-article","created":{"date-parts":[[2012,8,24]],"date-time":"2012-08-24T11:33:19Z","timestamp":1345807999000},"page":"2215-2222","source":"Crossref","is-referenced-by-count":20,"title":["Improved gap size estimation for scaffolding algorithms"],"prefix":"10.1093","volume":"28","author":[{"given":"Kristoffer","family":"Sahlin","sequence":"first","affiliation":[{"name":"1 Department of Computational Biology, mKTH Royal Institute of Technology, Science for Life Laboratory, School of Computer Science and Communication, Solna, 2Department of Plant Physiology, Ume\u00e5 Plant Science Centre, Ume\u00e5 University, Ume\u00e5, Sweden, 3KTH Royal Institute of Technology, Science for Life Laboratory, School of Biotechnology, Division of Gene Technology, Solna, Sweden and 4Department of Numerical Analysis and Computer Science, Swedish e-Science Research Centre (SeRC), Stockholm University, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathaniel","family":"Street","sequence":"additional","affiliation":[{"name":"1 Department of Computational Biology, mKTH Royal Institute of Technology, Science for Life Laboratory, School of Computer Science and Communication, Solna, 2Department of Plant Physiology, Ume\u00e5 Plant Science Centre, Ume\u00e5 University, Ume\u00e5, Sweden, 3KTH Royal Institute of Technology, Science for Life Laboratory, School of Biotechnology, Division of Gene Technology, Solna, Sweden and 4Department of Numerical Analysis and Computer Science, Swedish e-Science Research Centre (SeRC), Stockholm University, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joakim","family":"Lundeberg","sequence":"additional","affiliation":[{"name":"1 Department of Computational Biology, mKTH Royal Institute of Technology, Science for Life Laboratory, School of Computer Science and Communication, Solna, 2Department of Plant Physiology, Ume\u00e5 Plant Science Centre, Ume\u00e5 University, Ume\u00e5, Sweden, 3KTH Royal Institute of Technology, Science for Life Laboratory, School of Biotechnology, Division of Gene Technology, Solna, Sweden and 4Department of Numerical Analysis and Computer Science, Swedish e-Science Research Centre (SeRC), Stockholm University, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Arvestad","sequence":"additional","affiliation":[{"name":"1 Department of Computational Biology, mKTH Royal Institute of Technology, Science for Life Laboratory, School of Computer Science and Communication, Solna, 2Department of Plant Physiology, Ume\u00e5 Plant Science Centre, Ume\u00e5 University, Ume\u00e5, Sweden, 3KTH Royal Institute of Technology, Science for Life Laboratory, School of Biotechnology, Division of Gene Technology, Solna, Sweden and 4Department of Numerical Analysis and Computer Science, Swedish e-Science Research Centre (SeRC), Stockholm University, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2012,8,20]]},"reference":[{"key":"2023012512561591100_bts441-B1","first-page":"578","article-title":"Scaffolding pre-assembled contigs using SSPACE","volume":"4","author":"Boetzer","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012512561591100_bts441-B2","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":"2023012512561591100_bts441-B3","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":"11","author":"Gao","year":"2011","journal-title":"J. Comput. Biol."},{"key":"2023012512561591100_bts441-B4","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":"2023012512561591100_bts441-B5","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.1186\/gb-2004-5-2-r12","article-title":"Versatile and open software for comparing large genomes","volume":"5","author":"Kurtz","year":"2004","journal-title":"Genome Biol."},{"key":"2023012512561591100_bts441-B6","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":"2023012512561591100_bts441-B7","doi-asserted-by":"crossref","first-page":"153","DOI":"10.2307\/1403464","article-title":"Maximum likelihood: an introduction","volume":"58","author":"Le Cam","year":"1990","journal-title":"Int. Stat. Rev."},{"key":"2023012512561591100_bts441-B8","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":"2023012512561591100_bts441-B9","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1186\/1756-0500-4-449","article-title":"An efficient simulator of 454 data using configurable statistical models","volume":"4","author":"Lysholm","year":"2011","journal-title":"BMC Res. Notes 2011"},{"key":"2023012512561591100_bts441-B10","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.tig.2007.12.007","article-title":"The impact of next-generation sequencing technology on genetics","volume":"24","author":"Mardis","year":"2008","journal-title":"Trends Gene."},{"key":"2023012512561591100_bts441-B11","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1186\/1471-2164-11-242","article-title":"Finishing genomes with limited resources: lessons from an ensemble of microbial genomes","volume":"11","author":"Nagarajan","year":"2010","journal-title":"BMC Genom."},{"key":"2023012512561591100_bts441-B12","doi-asserted-by":"crossref","first-page":"R55","DOI":"10.1186\/gb-2008-9-3-r55","article-title":"Genome assembly forensics: finding the elusive mis-assembly","volume":"9","author":"Phillippy","year":"2008","journal-title":"Genome Biol."},{"key":"2023012512561591100_bts441-B13","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1101\/gr.1536204","article-title":"Hierarchical scaffolding with Bambus","volume":"14","author":"Pop","year":"2011","journal-title":"Genome Res."},{"key":"2023012512561591100_bts441-B14","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.tig.2007.12.006","article-title":"Bioinformatics challenges of new sequencing technology","volume":"24","author":"Pop","year":"2008","journal-title":"Trends Genet."},{"key":"2023012512561591100_bts441-B15","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1093\/bib\/bbp026","article-title":"Genome assembly reborn: recent computational challenges","volume":"10","author":"Pop","year":"2009","journal-title":"Brief. Bioinform."},{"key":"2023012512561591100_bts441-B16","doi-asserted-by":"crossref","first-page":"e3373","DOI":"10.1371\/journal.pone.0003373","article-title":"MetaSim\u2014A sequencing simulator for genomics and metagenomics","volume":"3","author":"Richter","year":"2008","journal-title":"PLoS One"},{"key":"2023012512561591100_bts441-B17","doi-asserted-by":"crossref","first-page":"3259","DOI":"10.1093\/bioinformatics\/btr562","article-title":"Fast scaffolding with small independent mixed integer programs","volume":"23","author":"Salmela","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012512561591100_bts441-B18","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."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/17\/2215\/48874559\/bioinformatics_28_17_2215.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/17\/2215\/48874559\/bioinformatics_28_17_2215.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T18:15:56Z","timestamp":1674670556000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/17\/2215\/246308"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,20]]},"references-count":18,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2012,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts441","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2012,9,1]]},"published":{"date-parts":[[2012,8,20]]}}}