Related Experiment Video
Updated: Mar 31, 2026
08:03
Heuristic Mining of Hierarchical Genotypes and Accessory Genome Loci in Bacterial Populations
Published on: December 7, 2021
2.9K
Graphical pan-genome analysis with compressed suffix trees and the Burrows-Wheeler transform
Uwe Baier1, Timo Beller1, Enno Ohlebusch1
1Institute of Theoretical Computer Science, Ulm University, 89069 Ulm, Germany.
Bioinformatics (Oxford, England)
|October 28, 2015
Summary
New algorithms efficiently construct compressed de Bruijn graphs for population genomics. These methods improve upon existing techniques, enabling scalable analysis of large genomic datasets and revealing population genetic structure.
Area of Science:
- Genomics
- Bioinformatics
- Computational Biology
Background:
- Low-cost genome sequencing provides extensive population genetic structure data.
- Population graphs represent variations across many individuals.
- Compressed de Bruijn graphs are used for population genome representation.
Purpose of the Study:
- To develop space-efficient algorithms for constructing compressed de Bruijn graphs.
- To improve upon the existing splitMEM algorithm for population genome representation.
Main Methods:
- Developed a linear-time suffix tree algorithm using a compressed suffix tree.
- Utilized the Burrows-Wheeler transform to construct the compressed de Bruijn graph in O(n) time.
- Applied algorithms to seven human genomes to demonstrate scalability.
Main Results:
- Presented two novel algorithms that outperform splitMEM in theory and practice.
- Achieved efficient construction of compressed de Bruijn graphs.
- Demonstrated scalability with human genome data.
Conclusions:
- The developed algorithms offer significant improvements for constructing population genome graphs.
- These methods enable more scalable and efficient analysis of large-scale genomic data.
- Facilitates deeper insights into population genetic structures.
Related Concept Videos
02:54Evolutionary Relationships through Genome Comparisons
7.2K
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
7.2K
01:11Genome-wide Association Studies-GWAS
16.6K
Genome-wide association studies or GWAS are used to identify whether common SNPs are associated with certain diseases. Suppose specific SNPs are more frequently observed in individuals with a particular disease than those without the disease. In that case, those SNPs are said to be associated with the disease. Chi-square analysis is performed to check the probability of the allele likely to be associated with the disease.
GWAS does not require the identification of the target gene involved in...
GWAS does not require the identification of the target gene involved in...
16.6K
03:36Genome Annotation and Assembly
21.5K
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.
21.5K