Related Experiment Video
Updated: Jun 21, 2025
05:01
A Pathway Association Study Tool for GWAS Analyses of Metabolic Pathway Information
Published on: July 1, 2020
3.3K
Maximum-scoring path sets on pangenome graphs of constant treewidth.
Broňa Brejová1, Travis Gagie2, Eva Herencsárová1
1Department of Computer Science, Faculty of Mathematics, Physics and Informatics, Comenius University in Bratislava, Bratislava, Slovakia.
Frontiers in Bioinformatics
|July 16, 2024
Summary
This study introduces a new graph problem, maximum-scoring path sets (MSPS), extending sequence analysis to complex biological graphs. An efficient algorithm is presented for finding optimal path sets in graphs with constant treewidth.
Area of Science:
- Computational Biology
- Graph Theory
- Bioinformatics
Background:
- Previous work focused on maximum-scoring segment sets in sequences.
- Biological data is increasingly represented as complex graphs, such as pangenomes.
Purpose of the Study:
- To generalize the maximum-scoring segment set problem from sequences to vertex-weighted graphs.
- To introduce and solve the maximum-scoring path sets (MSPS) problem.
- To develop an efficient algorithm for MSPS on graphs with constant treewidth.
Main Methods:
- Generalization of sequence-based algorithms to graph structures.
- Development of a linear-time algorithm for graphs with constant treewidth.
Main Results:
- The maximum-scoring path sets (MSPS) problem is formally defined for vertex-weighted graphs.
- A linear-time algorithm is presented for graphs with constant treewidth.
- The algorithm's applicability to pangenome graphs and related biological problems is demonstrated.
Conclusions:
- The MSPS problem provides a unified framework for various biological analyses on pangenome graphs.
- The developed algorithm offers an efficient solution for these complex biological data structures.
Related Concept Videos
01:18Polygenic Traits
65.7K
When more than one gene is responsible for a given phenotype, the trait is considered polygenic. Human height is a polygenic trait. Studies have uncovered hundreds of loci that influence height, and there are believed to be many more. Due to the high number of genes involved, as well as environmental and nutritional factors, height varies significantly within a given population. The distribution of height forms a bell-shaped curve, with relatively few individuals in the population at the...
65.7K
03:21Phylogenetic Trees
45.3K
Phylogenetic trees come in many forms. It matters in which sequence the organisms are arranged from the bottom to the top of the tree, but the branches can rotate at their nodes without altering the information. The lines connecting individual nodes can be straight, angled, or even curved.
45.3K
01:18pV-Diagrams
4.1K
The pV diagram, which is a graph of pressure versus volume of the gas under study, is helpful in describing certain aspects of the substance. When the substance behaves like an ideal gas, the ideal gas equation describes the relationship between its pressure and volume. On a pV diagram, it is common to plot an isotherm, which is a curve showing p as a function of V with the number of molecules and the temperature fixed. Then, for an ideal gas, the product of the pressure of the gas and its...
4.1K
01:10Interference: Path Lengths
1.3K
Consider two sources of sound, that may or may not be in phase, emitting waves at a single frequency, and consider the frequencies to be the same.
Two special sources may be considered when they are in phase. This can be easily achieved by feeding the two sources from the same source. An example would be synchronizing the two speakers by feeding them with the same source, such as the sound waves produced by a tuning fork. This setup ensures that the two sources have the same frequency and are...
Two special sources may be considered when they are in phase. This can be easily achieved by feeding the two sources from the same source. An example would be synchronizing the two speakers by feeding them with the same source, such as the sound waves produced by a tuning fork. This setup ensures that the two sources have the same frequency and are...
1.3K
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
02:33Combinatorial Gene Control
8.3K
Combinatorial gene control is the synergistic action of several transcriptional factors to regulate the expression of a single gene. The absence of one or more of these factors may lead to a significant difference in the level of gene expression or repression.
The expression of more than 30,000 genes is controlled by approximately 2000-3000 transcription factors. This is possible because a single transcription factor can recognize more than one regulatory sequence. The specificity in gene...
The expression of more than 30,000 genes is controlled by approximately 2000-3000 transcription factors. This is possible because a single transcription factor can recognize more than one regulatory sequence. The specificity in gene...
8.3K