{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T13:39:31Z","timestamp":1742391571672},"reference-count":20,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":3015,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>New generation sequencing technologies offer unique opportunities and challenges for re-sequencing studies. In this article, we focus on re-sequencing experiments using the Solexa technology, based on bacterial artificial chromosome (BAC) clones, and address an experimental design problem. In these specific experiments, approximate coordinates of the BACs on a reference genome are known, and fine-scale differences between the BAC sequences and the reference are of interest. The high-throughput characteristics of the sequencing technology makes it possible to multiplex BAC sequencing experiments by pooling BACs for a cost-effective operation. However, the way BACs are pooled in such re-sequencing experiments has an effect on the downstream analysis of the generated data, mostly due to subsequences common to multiple BACs. The experimental design strategy we develop in this article offers combinatorial solutions based on approximation algorithms for the well-known max n-cut problem and the related max n-section problem on hypergraphs. Our algorithms, when applied to a number of sample cases give more than a 2-fold performance improvement over random partitioning.<\/jats:p>\n               <jats:p>Contact: \u00a0cenk@cs.sfu.ca<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn173","type":"journal-article","created":{"date-parts":[[2008,6,27]],"date-time":"2008-06-27T07:43:13Z","timestamp":1214552593000},"page":"i32-i40","source":"Crossref","is-referenced-by-count":12,"title":["Optimal pooling for genome re-sequencing with ultra-high-throughput short-read technologies"],"prefix":"10.1093","volume":"24","author":[{"given":"Iman","family":"Hajirasouliha","sequence":"first","affiliation":[{"name":"1 Lab for Computational Biology, Simon Fraser University, Burnaby, and 2BC Cancer Agency, Genome Sciences Center, Vancouver, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fereydoun","family":"Hormozdiari","sequence":"additional","affiliation":[{"name":"1 Lab for Computational Biology, Simon Fraser University, Burnaby, and 2BC Cancer Agency, Genome Sciences Center, Vancouver, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. Cenk","family":"Sahinalp","sequence":"additional","affiliation":[{"name":"1 Lab for Computational Biology, Simon Fraser University, Burnaby, and 2BC Cancer Agency, Genome Sciences Center, Vancouver, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inanc","family":"Birol","sequence":"additional","affiliation":[{"name":"1 Lab for Computational Biology, Simon Fraser University, Burnaby, and 2BC Cancer Agency, Genome Sciences Center, Vancouver, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2008,7,1]]},"reference":[{"key":"2023020210411708000_B1","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1517\/14622416.5.4.433","article-title":"Solexa ltd","volume":"5","author":"Bennett","year":"2004","journal-title":"Pharmacogenomics"},{"key":"2023020210411708000_B2","doi-asserted-by":"crossref","first-page":"2067","DOI":"10.1093\/bioinformatics\/bth205","article-title":"Fragment assembly with short reads","volume":"20","author":"Chaisson","year":"2004","journal-title":"Bioinformatics"},{"key":"2023020210411708000_B3","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1101\/gr.7088808","article-title":"Short read fragment assembly of bacterial genomes","volume":"18","author":"Chaisson","year":"2008","journal-title":"Genome Res"},{"key":"2023020210411708000_B4","article-title":"The capacitated max k-cut problem","volume-title":"Math. Progr","author":"Gaur","year":"2007"},{"key":"2023020210411708000_B5","first-page":"19.1","volume-title":"Chapter 5: Large-Scale BAC Clone Restriction Digest Fingerprinting","author":"Mathewson","year":"2007"},{"key":"2023020210411708000_B6","doi-asserted-by":"crossref","first-page":"R224","DOI":"10.1186\/gb-2007-8-10-r224","article-title":"A bac clone fingerprinting approach to the detection of human genome rearrangements","volume":"8","author":"Krzywinski","year":"2007","journal-title":"Genome Biol"},{"key":"2023020210411708000_B7","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1038\/nature03959","article-title":"Genome sequencing in open microfabricated high-density picoliter reactors","volume":"437","author":"Margulies","year":"2005","journal-title":"Nature"},{"key":"2023020210411708000_B8","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","article-title":"A space-economical suffix tree construction algorithm","volume":"23","author":"Mccreight","year":"1976","journal-title":"JACM"},{"key":"2023020210411708000_B9","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1137\/0105003","article-title":"Algorithms for the assignment and transportation problems","volume":"5","author":"Munkres","year":"1957","journal-title":"J. Soc. Ind. Appl. Math"},{"key":"2023020210411708000_B10","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1145\/369133.369230","article-title":"A new approach to fragment assembly in dna sequencing","volume-title":"RECOMB","author":"Pevzner","year":"2001"},{"key":"2023020210411708000_B11","doi-asserted-by":"crossref","first-page":"9748","DOI":"10.1073\/pnas.171285098","article-title":"An eulerian path approach to dna fragment assembly","volume":"98","author":"Pevzner","year":"2001","journal-title":"Proc. Natl. Acad Sci"},{"key":"2023020210411708000_B12","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/0888-7543(95)80219-C","article-title":"Pairwise end sequencing: a unified approach to genomic mapping and sequencing","volume":"26","author":"Roach","year":"1995","journal-title":"Genomics"},{"key":"2023020210411708000_B13","first-page":"300","article-title":"Symmetry breaking for suffix tree construction","volume-title":"Proceedings of the STOC","author":"Sahinalp","year":"1994"},{"key":"2023020210411708000_B14","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","article-title":"P-complete approximation problems","volume":"23","author":"Sahni","year":"1976","journal-title":"J. ACM"},{"key":"2023020210411708000_B15","doi-asserted-by":"crossref","first-page":"5463","DOI":"10.1073\/pnas.74.12.5463","article-title":"Dna sequencing with chain-terminating inhibitors","volume":"74","author":"Sanger","year":"1977","journal-title":"Proc. Natl Acad. Sci"},{"key":"2023020210411708000_B16","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0022-2836(80)90196-5","article-title":"Cloning in single-stranded bacteriophage as an aid to rapid DNA sequencing","volume":"143","author":"Sanger","year":"1980","journal-title":"J. Mol. Biol"},{"key":"2023020210411708000_B17","first-page":"729","article-title":"Nucleotide sequence of bacteriophage lambda","volume":"161","author":"Sanger","year":"1982","journal-title":"DNA"},{"key":"2023020210411708000_B18","unstructured":"Solexa web server\n          2008\n          \n            http:\/\/www.solexa.com"},{"key":"2023020210411708000_B19","doi-asserted-by":"crossref","first-page":"e484","DOI":"10.1371\/journal.pone.0000484","article-title":"Whole-genome sequencing and assembly with high-throughput, short read technologies","volume":"2","author":"Sundquist","year":"2007","journal-title":"PLoS ONE"},{"key":"2023020210411708000_B20","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1093\/bioinformatics\/btl629","article-title":"Assembling millions of short DNA sequences using ssake","volume":"23","author":"Warren","year":"2006","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i32\/49054305\/bioinformatics_24_13_i32.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i32\/49054305\/bioinformatics_24_13_i32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T12:27:18Z","timestamp":1675340838000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/13\/i32\/234056"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,1]]},"references-count":20,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2008,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn173","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,7,1]]},"published":{"date-parts":[[2008,7,1]]}}}