Related Experiment Video
Updated: Jun 14, 2026
09:40
Novel Sequence Discovery by Subtractive Genomics
Published on: January 25, 2019
Storage and retrieval of highly repetitive sequence collections
Veli Mäkinen1, Gonzalo Navarro, Jouni Sirén
1Department of Computer Science, University of Helsinki, Helsinki, Finland . vmakinen@cs.helsinki.fi
Summary
New full-text indexes efficiently analyze repetitive sequence collections, like genomes, by reducing space requirements. This enables faster in-memory analysis of large datasets with improved compression models.
Area of Science:
- Bioinformatics
- Computational Biology
- Data Compression
Background:
- Repetitive sequence collections, such as individual genomes, present analysis challenges due to their large size.
- Suffix trees are powerful tools for sequence analysis but require significant memory.
- Existing compressed suffix trees struggle with long-range repetitiveness.
Purpose of the Study:
- To develop novel static and dynamic full-text indexes for efficient analysis of highly repetitive sequence collections.
- To reduce the space complexity of suffix tree-based analyses.
- To enhance the capability of compressed suffix trees to capture longer-term repetitiveness.
Main Methods:
- Development of new static and dynamic full-text indexes.
- Integration of these indexes with a dynamic fully-compressed suffix tree.
- Focus on space complexity proportional to typical sequence length plus edit operations.
Main Results:
- The new indexes effectively capture high repetitiveness in sequence collections.
- Achieved space complexity is proportional to one typical sequence length plus total edit operations.
- Experimental results demonstrate the practicality and efficiency of the proposed methods.
Conclusions:
- The developed full-text indexes offer a practical solution for analyzing large, repetitive sequence collections.
- These indexes significantly reduce memory requirements for suffix tree-based analyses.
- The approach enhances the ability to handle complex, long-range repetitiveness in genomic and other sequence data.
Related Concept Videos
02:51Multi-species Conserved Sequences
Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...
03:21RNA-seq
RNA sequencing, or RNA-Seq, is a high-throughput sequencing technology used to study the transcriptome of a cell. Transcriptomics helps to interpret the functional elements of a genome and identify the molecular constituents of an organism. Additionally, it also helps in understanding the development of an organism and the occurrence of diseases.
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while microarray-based...
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while microarray-based...
03:00Next-generation Sequencing
The first human genome sequencing project cost $2.7 billion and was declared complete in 2003, after 15 years of international cooperation and collaboration between several research teams and funding agencies. Today, with the advent of next-generation sequencing technologies, the cost and time of sequencing a human genome have dropped over 100 fold.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features.
01:05Maxam-Gilbert Sequencing
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Challenges of the Maxam-Gilbert Method
The...
01:57Sanger Sequencing
DNA sequencing is a fundamental technique that is routinely used in the biological sciences. This method can be applied to a range of questions at different scales - from the sequencing of a cloned DNA fragment or the study of a mutation in a gene up to whole-genome sequencing. However, despite the widespread use of sequencing today, it was not until 1977 that Fredrick Sanger and his collaborators developed the chain-termination method to decode DNA sequences. It relies on the separation of a...
03:36Genome Annotation and Assembly
The genome refers to all of the genetic material in an organism. It can range from a few million base pairs in microbial cells to several billion base pairs in many eukaryotic organisms. Genome assembly refers to the process of taking the DNA sequencing data and putting it all back together in a correct order to create a close representation of the original genome. This is followed by the identification of functional elements on the newly assembled genome, a process called genome annotation.