Change search
ReferencesLink to record
Permanent link

Direct link
SEK: Sparsity exploiting k-mer-based estimation of bacterial community composition
KTH, School of Electrical Engineering (EES), Communication Theory.ORCID iD: 0000-0003-2638-6047
Dept of Mathematics, Oregon State University, Corvallis, USA.
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB.
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB. (Computational Biological Physics, CBP)
Show others and affiliations
2014 (English)In: Bioinformatics, ISSN 1460-2059, Vol. 30, no 17, 2423-2431 p.Article in journal (Refereed) Published
Abstract [en]

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.

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.

Availability and implementation: A platform-independent Matlab implementation of the method is freely available at; source code that does not require access to Matlab is currently being tested and will be made available later through the above Web site.

Place, publisher, year, edition, pages
Oxford University Press, 2014. Vol. 30, no 17, 2423-2431 p.
Keyword [en]
bacterial community composition, sparsity, metagenomics
National Category
Bioinformatics (Computational Biology)
Research subject
Computer Science
URN: urn:nbn:se:kth:diva-152814DOI: 10.1093/bioinformatics/btu320ISI: 000342912400046ScopusID: 2-s2.0-84907029456OAI: diva2:751624
Swedish Research Council

QC 20141023

Available from: 2014-10-01 Created: 2014-10-01 Last updated: 2015-09-30Bibliographically approved
In thesis
1. Data Analysis and Next Generation Sequencing : Applications in Microbiology.
Open this publication in new window or tab >>Data Analysis and Next Generation Sequencing : Applications in Microbiology.
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Next Generation Sequencing (NGS) is a new technology that has revolutionized the way we study living organisms. Where previously only a few genes could be studied at a time through targeted direct probing, NGS offers the possibility to perform measurements for a whole genome at once. The drawback is that the amount of data generated in the process is large and extracting useful information from it requires new methods to process and analyze it.

The main contribution of this thesis is the development of a novel experimental method coined tagRNA-seq, combining 5’tagRACE, a previously developed technique, with RNA-sequencing technology. Briefly, tagRNA-seq makes it possible to identify the 5’ ends of RNAs in bacteria and directly probe for their type, primary or processed, by ligating short RNA sequences, the tags, to the beginnings of RNA molecules. We used the method to directly probe for transcription start and processing sites in two bacterial species, Escherichiacoli and Enterococcus faecalis. It was also used to study polyadenylation in E. coli, where the ability to identify processed RNA molecules proved to be useful to separate direct and indirect regulatory effects of this mechanism. We also demonstrate how data from tagRNA-seq experiments can be used to increase confidence on the discovery of anti-sense transcripts in bacteria. Analyses of RNA-seq data obtained in the context of these experiments revealed subtle artifacts in the coverage signal towards gene ends, that we were able to explain and quantify based Kolmogorov’s broken stick model. We also discovered evidences for circularization of a few RNA transcripts, both in our own data sets and publicly available data.

Designing the tags used in tagRNA-seq led us to the problem of words absent from a text. We focus on a particular subset of these, the minimal absent words (MAWs), and develop a theory providing a complete description of their size distribution in random text. We also show that MAWs in genomes from viruses and living organisms almost always exhibit a behavior different from random texts in the tail of the distribution, and that MAWs from this tail are closely related to sequences present in the genome that preferentially appear in regions with important regulatory functions.

Finally, and independently from tagRNA-seq, we propose a new approach to the problem of bacterial community reconstruction in metagenomic, based on techniques from compressed sensing. We provide a novel algorithm competing with state-of-the-art techniques in the field.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2015. xviii, 154 p.
TRITA-CSC-A, ISSN 1653-5723 ; 2015:15
RNA-seq, tagRNA-seq, primary and processed RNA, Enterococcus faecalis, Complex transcription, Metagenomics, 5'tagRACE, minimal absent words, compressed sensing, metagenomics, bacterial community reconstruction
National Category
Bioinformatics (Computational Biology) Microbiology Other Biological Topics Genetics
Research subject
Biological Physics
urn:nbn:se:kth:diva-173219 (URN)978-91-7595-699-2 (ISBN)
Public defence
2015-10-30, FA32, Roslagstullsbacken 21, Stockholm, 14:00 (English)

QC 20150930

Available from: 2015-09-30 Created: 2015-09-07 Last updated: 2015-11-06Bibliographically approved

Open Access in DiVA

SEK paper(672 kB)35 downloads
File information
File name FULLTEXT01.pdfFile size 672 kBChecksum SHA-512
Type fulltextMimetype application/pdf
SEK Code(3609 kB)0 downloads
File information
File name SOFTWARE01.zipFile size 3609 kBChecksum SHA-512
Type softwareMimetype application/zip

Other links

Publisher's full textScopusPublisher's website

Search in DiVA

By author/editor
Chatterjee, SaikatDong, SiyuanInnocenti, NicolasVehkaperä, MikkoSkoglund, MikaelK. Rasmussen, LarsAurell, Erik
By organisation
Communication TheoryComputational Biology, CBACCESS Linnaeus Centre
Bioinformatics (Computational Biology)

Search outside of DiVA

GoogleGoogle Scholar
Total: 35 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 85 hits
ReferencesLink to record
Permanent link

Direct link