{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:05:03Z","timestamp":1773270303874,"version":"3.50.1"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"19","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Identification of every single genome present in a microbial sample is an important and challenging task with crucial applications. It is challenging because there are typically millions of cells in a microbial sample, the vast majority of which elude cultivation. The most accurate method to date is exhaustive single-cell sequencing using multiple displacement amplification, which is simply intractable for a large number of cells. However, there is hope for breaking this barrier, as the number of different cell types with distinct genome sequences is usually much smaller than the number of cells.<\/jats:p>\n               <jats:p>Results: Here, we present a novel divide and conquer method to sequence and de novo assemble all distinct genomes present in a microbial sample with a sequencing cost and computational complexity proportional to the number of genome types, rather than the number of cells. The method is implemented in a tool called Squeezambler. We evaluated Squeezambler on simulated data. The proposed divide and conquer method successfully reduces the cost of sequencing in comparison with the na\u00efve exhaustive approach.<\/jats:p>\n               <jats:p>Availability: Squeezambler and datasets are available at http:\/\/compbio.cs.wayne.edu\/software\/squeezambler\/.<\/jats:p>\n               <jats:p>Contact: \u00a0ztaghavi@wayne.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt420","type":"journal-article","created":{"date-parts":[[2013,8,6]],"date-time":"2013-08-06T05:30:10Z","timestamp":1375767010000},"page":"2395-2401","source":"Crossref","is-referenced-by-count":7,"title":["Distilled single-cell genome sequencing and <i>de novo<\/i> assembly for sparse microbial communities"],"prefix":"10.1093","volume":"29","author":[{"given":"Zeinab","family":"Taghavi","sequence":"first","affiliation":[{"name":"1 Department of Computer Science and 2Department of Obstetrics and Gynecology, Wayne State University, Detroit, MI 48202, USA"}]},{"given":"Narjes S.","family":"Movahedi","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science and 2Department of Obstetrics and Gynecology, Wayne State University, Detroit, MI 48202, USA"}]},{"given":"Sorin","family":"Dr\u01ceghici","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science and 2Department of Obstetrics and Gynecology, Wayne State University, Detroit, MI 48202, USA"},{"name":"1 Department of Computer Science and 2Department of Obstetrics and Gynecology, Wayne State University, Detroit, MI 48202, USA"}]},{"given":"Hamidreza","family":"Chitsaz","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science and 2Department of Obstetrics and Gynecology, Wayne State University, Detroit, MI 48202, USA"}]}],"member":"286","published-online":{"date-parts":[[2013,8,5]]},"reference":[{"key":"2023012810464248900_btt420-B1","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1089\/cmb.2012.0021","article-title":"SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing","volume":"19","author":"Bankevich","year":"2012","journal-title":"J. Comput. Biol."},{"key":"2023012810464248900_btt420-B2","doi-asserted-by":"crossref","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","article-title":"Decoding by linear programming","volume":"51","author":"Cand\u00e8s","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2023012810464248900_btt420-B3","doi-asserted-by":"crossref","first-page":"5406","DOI":"10.1109\/TIT.2006.885507","article-title":"Near-optimal signal recovery from random projections: Universal encoding strategies?","volume":"52","author":"Cand\u00e8s","year":"2006","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2023012810464248900_btt420-B4","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1038\/nbt.1966","article-title":"Efficient de novo assembly of single-cell bacterial genomes from short-read data sets","volume":"29","author":"Chitsaz","year":"2011","journal-title":"Nat. Biotechnol."},{"key":"2023012810464248900_btt420-B5","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1101\/gr.180501","article-title":"Rapid amplification of plasmid and phage DNA using Phi 29 DNA polymerase and multiply-primed rolling circle amplification","volume":"11","author":"Dean","year":"2001","journal-title":"Genome Res."},{"key":"2023012810464248900_btt420-B6","doi-asserted-by":"crossref","first-page":"5261","DOI":"10.1073\/pnas.082089499","article-title":"Comprehensive human genome amplification using multiple displacement amplification","volume":"99","author":"Dean","year":"2002","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012810464248900_btt420-B7","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","article-title":"Compressed sensing","volume":"52","author":"Donoho","year":"2006","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2023012810464248900_btt420-B8","doi-asserted-by":"crossref","first-page":"706","DOI":"10.1109\/TIT.2009.2037043","article-title":"Compressed genotyping","volume":"56","author":"Erlich","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2023012810464248900_btt420-B9","doi-asserted-by":"crossref","first-page":"6222","DOI":"10.1109\/TIT.2011.2162269","article-title":"Distilled sensing: adaptive sampling for sparse detection and estimation","volume":"57","author":"Haupt","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2023012810464248900_btt420-B10","doi-asserted-by":"crossref","first-page":"5555","DOI":"10.1073\/pnas.0801389105","article-title":"Complete genome of the uncultured Termite Group 1 bacteria in a single host protist cell","volume":"105","author":"Hongoh","year":"2008","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012810464248900_btt420-B11","doi-asserted-by":"crossref","first-page":"954","DOI":"10.1101\/gr.816903","article-title":"Unbiased whole-genome amplification directly from clinical samples","volume":"13","author":"Hosono","year":"2003","journal-title":"Genome Res."},{"key":"2023012810464248900_btt420-B12","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1093\/bioinformatics\/btr708","article-title":"ART: a next-generation sequencing read simulator","volume":"28","author":"Huang","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012810464248900_btt420-B13","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1038\/ng.1028","article-title":"De novo assembly and genotyping of variants using colored de bruijn graphs","volume":"44","author":"Iqbal","year":"2012","journal-title":"Nat. Genet."},{"key":"2023012810464248900_btt420-B14","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/j.mib.2008.05.006","article-title":"Genomic sequencing of single microbial cells from environmental samples","volume":"11","author":"Ishoey","year":"2008","journal-title":"Curr. Opin. Microbiol."},{"key":"2023012810464248900_btt420-B15","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1007\/s00253-006-0725-7","article-title":"Specific single-cell isolation and genomic amplification of uncultured microorganisms","volume":"74","author":"Kvist","year":"2007","journal-title":"Appl. Microbiol. Biotechnol."},{"key":"2023012810464248900_btt420-B16","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0888-7543(88)90007-9","article-title":"Genomic mapping by fingerprinting random clones: a mathematical analysis","volume":"2","author":"Lander","year":"1988","journal-title":"Genomics"},{"key":"2023012810464248900_btt420-B17","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1016\/j.mib.2007.08.005","article-title":"Single-cell genomic sequencing using Multiple Displacement Amplification","volume":"10","author":"Lasken","year":"2007","journal-title":"Curr. Opin. Microbiol."},{"key":"2023012810464248900_btt420-B18","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1186\/1472-6750-7-19","article-title":"Mechanism of chimera formation during the Multiple Displacement Amplification reaction","volume":"7","author":"Lasken","year":"2007","journal-title":"BMC Biotechnol."},{"key":"2023012810464248900_btt420-B19","doi-asserted-by":"crossref","first-page":"11889","DOI":"10.1073\/pnas.0704662104","article-title":"Dissecting biological \u201cdark matter\u201d with single-cell genetic analysis of rare and uncultivated TM7 microbes from the human mouth","volume":"104","author":"Marcy","year":"2007","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012810464248900_btt420-B20","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1038\/nature11209","article-title":"A framework for human microbiome research","volume":"486","author":"Methe","year":"2012","journal-title":"Nature"},{"key":"2023012810464248900_btt420-B21","first-page":"561","article-title":"De novo co-assembly of bacterial genomes from multiple single cells","volume-title":"IEEE Conference on Bioinformatics and Biomedicine","author":"Movahedi","year":"2012"},{"key":"2023012810464248900_btt420-B22","doi-asserted-by":"crossref","first-page":"e230","DOI":"10.1371\/journal.pbio.0050230","article-title":"Insights into the genome of large sulfur bacteria revealed by analysis of single filaments","volume":"5","author":"Mussmann","year":"2007","journal-title":"PLoS Biol."},{"key":"2023012810464248900_btt420-B23","doi-asserted-by":"crossref","first-page":"1420","DOI":"10.1093\/bioinformatics\/bts174","article-title":"IDBA-UD: a de novo assembler for single-cell and metagenomic sequencing data with highly uneven depth","volume":"28","author":"Peng","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012810464248900_btt420-B24","doi-asserted-by":"crossref","first-page":"3205","DOI":"10.1128\/AEM.02985-06","article-title":"Targeted access to the genomes of low-abundance organisms in complex microbial communities","volume":"73","author":"Podar","year":"2007","journal-title":"Appl. Environ. Microbiol."},{"key":"2023012810464248900_btt420-B25","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1038\/nature08821","article-title":"A human gut microbial gene catalogue established by metagenomic sequencing","volume":"464","author":"Qin","year":"2010","journal-title":"Nature"},{"key":"2023012810464248900_btt420-B26","doi-asserted-by":"crossref","first-page":"3342","DOI":"10.1128\/AEM.71.6.3342-3347.2005","article-title":"Genomic DNA amplification from a single bacterium","volume":"71","author":"Raghunathan","year":"2005","journal-title":"Appl. Environ. Microbiol."},{"key":"2023012810464248900_btt420-B27","doi-asserted-by":"crossref","first-page":"e6864","DOI":"10.1371\/journal.pone.0006864","article-title":"Whole genome amplification and de novo assembly of single bacterial cells","volume":"4","author":"Rodrigue","year":"2009","journal-title":"PLoS One"},{"key":"2023012810464248900_btt420-B28","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":"2023012810464248900_btt420-B29","first-page":"1125","article-title":"Learning fourier sparse set functions","volume":"22","author":"Stobbe","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"2023012810464248900_btt420-B30","first-page":"575","article-title":"Mdasim: a multiple displacement amplification simulator","volume-title":"IEEE Conference on Bioinformatics and Biomedicine","author":"Taghavi","year":"2012"},{"key":"2023012810464248900_btt420-B31","doi-asserted-by":"crossref","first-page":"R2","DOI":"10.1186\/gb-2013-14-1-r2","article-title":"MetAMOS: a modular and open source metagenomic assembly and analysis pipeline","volume":"14","author":"Treangen","year":"2013","journal-title":"Genome Biol."},{"key":"2023012810464248900_btt420-B32","first-page":"153","article-title":"Multistage adaptive estimation of sparse signals","volume-title":"IEEE Statistical Signal Processing Workshop (SSP)","author":"Wei","year":"2012"},{"key":"2023012810464248900_btt420-B33","doi-asserted-by":"crossref","first-page":"e5299","DOI":"10.1371\/journal.pone.0005299","article-title":"Assembling the marine metagenome, one cell at a time","volume":"4","author":"Woyke","year":"2009","journal-title":"PLoS One"},{"key":"2023012810464248900_btt420-B34","doi-asserted-by":"crossref","first-page":"680","DOI":"10.1038\/nbt1214","article-title":"Sequencing genomes from single cells by polymerase cloning","volume":"24","author":"Zhang","year":"2006","journal-title":"Nat. Biotechnol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/19\/2395\/48895549\/bioinformatics_29_19_2395.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/19\/2395\/48895549\/bioinformatics_29_19_2395.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T12:36:28Z","timestamp":1674909388000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/19\/2395\/189344"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8,5]]},"references-count":34,"journal-issue":{"issue":"19","published-print":{"date-parts":[[2013,10,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt420","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2013,10,1]]},"published":{"date-parts":[[2013,8,5]]}}}