Change search
ReferencesLink to record
Permanent link

Direct link
The Bulk and The Tail of Minimal Absent Words in Genome Sequences
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB. Aalto University, Finland. (Computational Biological Physics, CBP)
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB. The Hebrew University of Jerusalem, Israel. (Computational Biological Physics, CBP)
State Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China.
2015 (English)In: Physical Biology, ISSN 1478-3967, E-ISSN 1478-3975, Vol. 13, no 2Article in journal (Other academic) Published
Abstract [en]

Minimal absent words (MAW) of a genomic sequence are subsequences that are absent themselves but the subwords of which are all present in the sequence. The characteristic distribution of genomic MAWs as a function of their length has been observed to be qualitatively similar for all living organisms, the bulk being rather short, and only relatively few being long. It has been an open issue whether the reason behind this phenomenon is statistical or reflects a biological mechanism, and what biological information is contained in absent words. % In this work we demonstrate that the bulk can be described by a probabilistic model of sampling words from random sequences, while the tail of long MAWs is of biological origin. We introduce the novel concept of a core of a minimal absent word, which are sequences present in the genome and closest to a given MAW. We show that in bacteria and yeast the cores of the longest MAWs, which exist in two or more copies, are located in highly conserved regions the most prominent example being ribosomal RNAs (rRNAs). We also show that while the distribution of the cores of long MAWs is roughly uniform over these genomes on a coarse-grained level, on a more detailed level it is strongly enhanced in 3' untranslated regions (UTRs) and, to a lesser extent, also in 5' UTRs. This indicates that MAWs and associated MAW cores correspond to fine-tuned evolutionary relationships, and suggest that they can be more widely used as markers for genomic complexity.

Place, publisher, year, edition, pages
Institute of Physics (IOP), 2015. Vol. 13, no 2
Keyword [en]
Minimal absent word; copy-mutation evolution model; random sequence
National Category
Biophysics Evolutionary Biology Genetics Bioinformatics (Computational Biology) Physical Sciences
URN: urn:nbn:se:kth:diva-173501DOI: 10.1088/1478-3975/13/2/026004OAI: diva2:853727

QC 20160429

Available from: 2015-09-14 Created: 2015-09-13 Last updated: 2016-04-29Bibliographically 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

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Aurell, ErikInnocenti, Nicolas
By organisation
Computational Biology, CB
In the same journal
Physical Biology
BiophysicsEvolutionary BiologyGeneticsBioinformatics (Computational Biology)Physical Sciences

Search outside of DiVA

GoogleGoogle Scholar
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: 110 hits
ReferencesLink to record
Permanent link

Direct link