{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T09:03:05Z","timestamp":1778058185605,"version":"3.51.4"},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"17","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,9,1]]},"abstract":"<jats:p>Motivation: Estimation of bacterial community composition from a high-throughput sequenced sample is an important task in metagenomics applications. As the sample sequence data typically harbors reads of variable lengths and different levels of biological and technical noise, accurate statistical analysis of such data is challenging. Currently popular estimation methods are typically time-consuming in a desktop computing environment.<\/jats:p>\n               <jats:p>Results: Using sparsity enforcing methods from the general sparse signal processing field (such as compressed sensing), we derive a solution to the community composition estimation problem by a simultaneous assignment of all sample reads to a pre-processed reference database. A general statistical model based on kernel density estimation techniques is introduced for the assignment task, and the model solution is obtained using convex optimization tools. Further, we design a greedy algorithm solution for a fast solution. Our approach offers a reasonably fast community composition estimation method, which is shown to be more robust to input data variation than a recently introduced related method.<\/jats:p>\n               <jats:p>Availability and implementation: A platform-independent Matlab implementation of the method is freely available at http:\/\/www.ee.kth.se\/ctsoftware; source code that does not require access to Matlab is currently being tested and will be made available later through the above Web site.<\/jats:p>\n               <jats:p>Contact: sach@kth.se<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu320","type":"journal-article","created":{"date-parts":[[2014,5,9]],"date-time":"2014-05-09T04:37:58Z","timestamp":1399610278000},"page":"2423-2431","source":"Crossref","is-referenced-by-count":12,"title":["SEK: sparsity exploiting <i>k<\/i>-mer-based estimation of bacterial community composition"],"prefix":"10.1093","volume":"30","author":[{"given":"Saikat","family":"Chatterjee","sequence":"first","affiliation":[{"name":"1 \u00a01Department of Communication Theory, KTH Royal Institute of Technology, Stockholm, Sweden, 2Department of Mathematics, Oregon State University, Corvallis, OR, USA, 3Systems Biology program, KTH Royal Institute of Technology, Sweden, 4Aalto University, Esbo, Finland, 5Department of Computational Biology, KTH Royal Institute of Technology, Stockholm, Sweden, 6Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland, 7Department of Physics, Tsinghua University, Beijing, China, 8Department of Signal Processing and 9Department of Information and Computer Science, Aalto University, Esbo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Koslicki","sequence":"additional","affiliation":[{"name":"1 \u00a01Department of Communication Theory, KTH Royal Institute of Technology, Stockholm, Sweden, 2Department of Mathematics, Oregon State University, Corvallis, OR, USA, 3Systems Biology program, KTH Royal Institute of Technology, Sweden, 4Aalto University, Esbo, Finland, 5Department of Computational Biology, KTH Royal Institute of Technology, Stockholm, Sweden, 6Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland, 7Department of Physics, Tsinghua University, Beijing, China, 8Department of Signal Processing and 9Department of Information and Computer Science, Aalto University, Esbo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siyuan","family":"Dong","sequence":"additional","affiliation":[{"name":"1 \u00a01Department of Communication Theory, KTH Royal Institute of Technology, Stockholm, Sweden, 2Department of Mathematics, Oregon State University, Corvallis, OR, USA, 3Systems Biology program, KTH Royal Institute of Technology, Sweden, 4Aalto University, Esbo, Finland, 5Department of Computational Biology, KTH Royal Institute of Technology, Stockholm, Sweden, 6Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland, 7Department of Physics, Tsinghua University, Beijing, China, 8Department of Signal Processing and 9Department of Information and Computer Science, Aalto University, Esbo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Innocenti","sequence":"additional","affiliation":[{"name":"1 \u00a01Department of Communication Theory, KTH Royal Institute of Technology, Stockholm, Sweden, 2Department of Mathematics, Oregon State University, Corvallis, OR, USA, 3Systems Biology program, KTH Royal Institute of Technology, Sweden, 4Aalto University, Esbo, Finland, 5Department of Computational Biology, KTH Royal Institute of Technology, Stockholm, Sweden, 6Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland, 7Department of Physics, Tsinghua University, Beijing, China, 8Department of Signal Processing and 9Department of Information and Computer Science, Aalto University, Esbo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Cheng","sequence":"additional","affiliation":[{"name":"1 \u00a01Department of Communication Theory, KTH Royal Institute of Technology, Stockholm, Sweden, 2Department of Mathematics, Oregon State University, Corvallis, OR, USA, 3Systems Biology program, KTH Royal Institute of Technology, Sweden, 4Aalto University, Esbo, Finland, 5Department of Computational Biology, KTH Royal Institute of Technology, Stockholm, Sweden, 6Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland, 7Department of Physics, Tsinghua University, Beijing, China, 8Department of Signal Processing and 9Department of Information and Computer Science, Aalto University, Esbo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yueheng","family":"Lan","sequence":"additional","affiliation":[{"name":"1 \u00a01Department of Communication Theory, KTH Royal Institute of Technology, Stockholm, Sweden, 2Department of Mathematics, Oregon State University, Corvallis, OR, USA, 3Systems Biology program, KTH Royal Institute of Technology, Sweden, 4Aalto University, Esbo, Finland, 5Department of Computational Biology, KTH Royal Institute of Technology, Stockholm, Sweden, 6Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland, 7Department of Physics, Tsinghua University, Beijing, China, 8Department of Signal Processing and 9Department of Information and Computer Science, Aalto University, Esbo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikko","family":"Vehkaper\u00e4","sequence":"additional","affiliation":[{"name":"1 \u00a01Department of Communication Theory, KTH Royal Institute of Technology, Stockholm, Sweden, 2Department of Mathematics, Oregon State University, Corvallis, OR, USA, 3Systems Biology program, KTH Royal Institute of Technology, Sweden, 4Aalto University, Esbo, Finland, 5Department of Computational Biology, KTH Royal Institute of Technology, Stockholm, Sweden, 6Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland, 7Department of Physics, Tsinghua University, Beijing, China, 8Department of Signal Processing and 9Department of Information and Computer Science, Aalto University, Esbo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikael","family":"Skoglund","sequence":"additional","affiliation":[{"name":"1 \u00a01Department of Communication Theory, KTH Royal Institute of Technology, Stockholm, Sweden, 2Department of Mathematics, Oregon State University, Corvallis, OR, USA, 3Systems Biology program, KTH Royal Institute of Technology, Sweden, 4Aalto University, Esbo, Finland, 5Department of Computational Biology, KTH Royal Institute of Technology, Stockholm, Sweden, 6Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland, 7Department of Physics, Tsinghua University, Beijing, China, 8Department of Signal Processing and 9Department of Information and Computer Science, Aalto University, Esbo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars K.","family":"Rasmussen","sequence":"additional","affiliation":[{"name":"1 \u00a01Department of Communication Theory, KTH Royal Institute of Technology, Stockholm, Sweden, 2Department of Mathematics, Oregon State University, Corvallis, OR, USA, 3Systems Biology program, KTH Royal Institute of Technology, Sweden, 4Aalto University, Esbo, Finland, 5Department of Computational Biology, KTH Royal Institute of Technology, Stockholm, Sweden, 6Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland, 7Department of Physics, Tsinghua University, Beijing, China, 8Department of Signal Processing and 9Department of Information and Computer Science, Aalto University, Esbo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik","family":"Aurell","sequence":"additional","affiliation":[{"name":"1 \u00a01Department of Communication Theory, KTH Royal Institute of Technology, Stockholm, Sweden, 2Department of Mathematics, Oregon State University, Corvallis, OR, USA, 3Systems Biology program, KTH Royal Institute of Technology, Sweden, 4Aalto University, Esbo, Finland, 5Department of Computational Biology, KTH Royal Institute of Technology, Stockholm, Sweden, 6Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland, 7Department of Physics, Tsinghua University, Beijing, China, 8Department of Signal Processing and 9Department of Information and Computer Science, Aalto University, Esbo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jukka","family":"Corander","sequence":"additional","affiliation":[{"name":"1 \u00a01Department of Communication Theory, KTH Royal Institute of Technology, Stockholm, Sweden, 2Department of Mathematics, Oregon State University, Corvallis, OR, USA, 3Systems Biology program, KTH Royal Institute of Technology, Sweden, 4Aalto University, Esbo, Finland, 5Department of Computational Biology, KTH Royal Institute of Technology, Stockholm, Sweden, 6Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland, 7Department of Physics, Tsinghua University, Beijing, China, 8Department of Signal Processing and 9Department of Information and Computer Science, Aalto University, Esbo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2014,5,7]]},"reference":[{"key":"2023012711524654100_btu320-B1","doi-asserted-by":"crossref","first-page":"e205","DOI":"10.1093\/nar\/gkt1070","article-title":"High-resolution microbial community reconstruction by integrating short reads from multiple 16S rRNA regions","volume":"41","author":"Amir","year":"2013","journal-title":"Nucleic Acids Res."},{"key":"2023012711524654100_btu320-B2","doi-asserted-by":"crossref","first-page":"1723","DOI":"10.1089\/cmb.2011.0189","article-title":"Bacterial community reconstruction using compressed sensing","volume":"18","author":"Amir","year":"2011","journal-title":"J. Comput. Biol."},{"key":"2023012711524654100_btu320-B3","doi-asserted-by":"crossref","first-page":"e94","DOI":"10.1093\/nar\/gks251","article-title":"Grinder: a versatile amplicon and shotgun sequence simulator","volume":"40","author":"Angly","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023012711524654100_btu320-B4","doi-asserted-by":"crossref","first-page":"i420","DOI":"10.1093\/bioinformatics\/btq365","article-title":"Characteristics of 454 pyrosequencing data\u2013enabling realistic simulation with flowsim","volume":"26","author":"Balzer","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012711524654100_btu320-B5","volume-title":"Pattern Recognition and Machine Learning","author":"Bishop","year":"2006"},{"key":"2023012711524654100_btu320-B6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"Boyd","year":"2004"},{"key":"2023012711524654100_btu320-B7","doi-asserted-by":"crossref","first-page":"e95","DOI":"10.1093\/nar\/gkr349","article-title":"Esprit-tree: hierarchical clustering analysis of millions of 16s rRNA pyrosequences in quasilinear computational time","volume":"39","author":"Cai","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023012711524654100_btu320-B8","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1109\/MSP.2007.914731","article-title":"An introduction to compressive sampling","volume":"25","author":"Candes","year":"2008","journal-title":"IEEE Signal Proc. Mag."},{"key":"2023012711524654100_btu320-B9","doi-asserted-by":"crossref","DOI":"10.1109\/ICASSP.2011.5947235","article-title":"Look ahead orthogonal matching pursuit","author":"Chatterjee","year":"2011"},{"key":"2023012711524654100_btu320-B10","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1109\/TSP.2011.2173682","article-title":"Projection-based and look-ahead strategies for atom selection","volume":"60","author":"Chatterjee","year":"2012","journal-title":"IEEE Trans.Signal Process."},{"key":"2023012711524654100_btu320-B11","doi-asserted-by":"crossref","first-page":"5240","DOI":"10.1093\/nar\/gks227","article-title":"Bayesian estimation of bacterial community composition from 454 sequencing data","volume":"40","author":"Cheng","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023012711524654100_btu320-B12","volume-title":"A system for disciplined convex programming","author":"CVX"},{"key":"2023012711524654100_btu320-B13","doi-asserted-by":"crossref","first-page":"2460","DOI":"10.1093\/bioinformatics\/btq461","article-title":"Search and clustering orders of magnitude faster than blast","volume":"26","author":"Edgar","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012711524654100_btu320-B14","first-page":"407","article-title":"Least angle regression","volume":"32","author":"Effron","year":"2004","journal-title":"Ann. Statist."},{"key":"2023012711524654100_btu320-B15","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1101\/gr.112730.110","article-title":"Chimeric 16s rRNA sequence formation and detection in sanger and 454-pyrosequenced pcr amplicons","volume":"21","author":"Haas","year":"2011","journal-title":"Genome Res."},{"key":"2023012711524654100_btu320-B16","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1109\/LSP.2011.2147313","article-title":"Backtracking-based matching pursuit method for sparse signal reconstruction","volume":"18","author":"Huang","year":"2011","journal-title":"IEEE Signal Process. Lett."},{"key":"2023012711524654100_btu320-B17","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1101\/gr.5969107","article-title":"Megan analysis of metagenomic data","volume":"17","author":"Huson","year":"2007","journal-title":"Genome Res."},{"key":"2023012711524654100_btu320-B18","doi-asserted-by":"crossref","first-page":"2096","DOI":"10.1093\/bioinformatics\/btt336","article-title":"Quikr: a method for rapid reconstruction of bacterial communities via compressive sensing","volume":"29","author":"Koslicki","year":"2013","journal-title":"Bioinformatics"},{"key":"2023012711524654100_btu320-B19","doi-asserted-by":"crossref","first-page":"1618","DOI":"10.1093\/bioinformatics\/btr266","article-title":"Mixture models for analysis of the taxonomic composition of metagenomes","volume":"27","author":"Meinicke","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012711524654100_btu320-B20","doi-asserted-by":"crossref","first-page":"S17","DOI":"10.1186\/1471-2164-12-S3-S17","article-title":"Analysis of 16s rRNA environmental sequences using megan","volume":"12","author":"Mitra","year":"2011","journal-title":"BMC Genomics"},{"key":"2023012711524654100_btu320-B21","doi-asserted-by":"crossref","first-page":"e60811","DOI":"10.1371\/journal.pone.0060811","article-title":"Species identification and profiling of complex microbial communities using shotgun illumina sequencing of 16s rRNA amplicon sequences","volume":"8","author":"Ong","year":"2013","journal-title":"PLoS One"},{"key":"2023012711524654100_btu320-B22","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1109\/JSTSP.2009.2039172","article-title":"l\n            \u00a02\/l1-optimization in block-sparse compressed sensing and its strong thresholds","volume":"4","author":"Stojnic","year":"2010","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"2023012711524654100_btu320-B23","doi-asserted-by":"crossref","first-page":"4655","DOI":"10.1109\/TIT.2007.909108","article-title":"Signal recovery from random measurements via orthogonal matching pursuit","volume":"53","author":"Tropp","year":"2007","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2023012711524654100_btu320-B24","doi-asserted-by":"crossref","first-page":"1126","DOI":"10.1126\/science.1133420","article-title":"Quantitative phylogenetic assessment of microbial communities in diverse environments","volume":"315","author":"von Mering","year":"2007","journal-title":"Science"},{"key":"2023012711524654100_btu320-B25","doi-asserted-by":"crossref","first-page":"5261","DOI":"10.1128\/AEM.00062-07","article-title":"Na\u00efve bayesian classifier for rapid assignment of rrna sequences into the new bacterial taxonomy","volume":"73","author":"Wang","year":"2007","journal-title":"Appl. Environ. Microbiol."},{"key":"2023012711524654100_btu320-B26","doi-asserted-by":"crossref","first-page":"1453","DOI":"10.1128\/AEM.02181-07","article-title":"Metagenomics: read length matters","volume":"74","author":"Wommack","year":"2008","journal-title":"Appl Environ Microbiol."},{"key":"2023012711524654100_btu320-B27","volume-title":"Accurate Profiling of Microbial Communities From Massively Parallel Sequencing Using Convex Optimization","author":"Zuk","year":"2012"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/17\/2423\/48927193\/bioinformatics_30_17_2423.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/17\/2423\/48927193\/bioinformatics_30_17_2423.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T12:14:22Z","timestamp":1674821662000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/17\/2423\/2748194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,7]]},"references-count":27,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2014,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu320","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,7]]}}}