Related Experiment Video
Updated: Jun 8, 2025
12:39
A Novel Bayesian Change-point Algorithm for Genome-wide Analysis of Diverse ChIPseq Data Types
Published on: December 10, 2012
11.3K
PangeBlocks: customized construction of pangenome graphs via maximal blocks
Jorge Avila Cartes1, Paola Bonizzoni2, Simone Ciccolella1
1Department of Informatics, Systems, and Communications, University of Milano - Bicocca, Viale Sarca, 20126, Milano, Italy.
BMC Bioinformatics
|November 4, 2024
Summary
This study formalizes pangenome graph construction as a Minimum Weighted Block Cover (MWBC) problem. An Integer Linear Programming (ILP) approach demonstrates how objective functions impact graph properties for downstream genomic analysis.
Area of Science:
- Computational Biology
- Bioinformatics
- Genomics
Background:
- Pangenome graph construction is crucial in pangenomics.
- Current methods lack explicit optimization criteria, obscuring the impact of graph topology on analyses like read mapping and variant calling.
Purpose of the Study:
- To formalize the pangenome graph construction problem.
- To investigate the effect of different optimization criteria on pangenome graph properties.
Main Methods:
- Reframing pangenome graph construction as a Minimum Weighted Block Cover (MWBC) problem using maximal blocks from Multiple Sequence Alignments (MSAs).
- Developing an Integer Linear Programming (ILP) formulation for the MWBC problem.
- Implementing and evaluating the ILP approach on SARS-CoV-2 genomes.
Main Results:
- Demonstrated that different objective functions yield pangenome graphs with distinct topological properties.
- Showcased how objective function selection influences downstream genomic tasks.
Conclusions:
- Customized pangenome graph construction based on objective functions significantly impacts graph characteristics.
- The formalization of the MWBC problem enables user-guided construction of graph representations for MSAs.
Related Concept Videos
01:17Karyotyping
58.2K
Overview
58.2K
02:54Evolutionary Relationships through Genome Comparisons
5.7K
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...
5.7K
03:36Genome Annotation and Assembly
18.8K
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.
18.8K
01:05Maxam-Gilbert Sequencing
11.1K
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...
11.1K
01:11Genome-wide Association Studies-GWAS
12.5K
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...
12.5K
03:21Genome Size and the Evolution of New Genes
7.9K
While every living organism has a genome of some kind (be it RNA, or DNA), there is considerable variation in the sizes of these blueprints. One major factor that impacts genome size is whether the organism is prokaryotic or eukaryotic. In prokaryotes, the genome contains little to no non-coding sequence, such that genes are tightly clustered in groups or operons sequentially along the chromosome. Conversely, the genes in eukaryotes are punctuated by long stretches of non-coding sequence.
7.9K