Related Experiment Video
Updated: Oct 21, 2025

Heuristic Mining of Hierarchical Genotypes and Accessory Genome Loci in Bacterial Populations
Published on: December 7, 2021
Scale-Free Spanning Trees and Their Application in Genomic Epidemiology
Yury Orlovich1, Kirill Kukharenko2, Volker Kaibel2
1Faculty of Applied Mathematics and Computer Science, Belarusian State University, Minsk, Belarus.
This study introduces algorithms for finding scale-free-like spanning trees, crucial for reconstructing viral transmission networks in genomic epidemiology. The methods accurately reconstruct hepatitis C transmission histories.
Area of Science:
- Graph theory
- Genomic epidemiology
- Computational biology
Background:
- Reconstructing viral transmission networks is vital for understanding disease spread.
- Existing methods may not fully capture the complex dynamics of pathogen transmission.
Purpose of the Study:
- To develop and analyze algorithms for identifying scale-free-like spanning trees.
- To apply these algorithms to reconstruct transmission networks in genomic epidemiology.
Main Methods:
- Introduced two objective functions: m-SF and s-SF spanning tree problems.
- Proved APX- and NP-hardness for these problems, even in restricted graph classes.
- Developed integer linear programming (ILP) formulations for the s-SF problem.
Main Results:
- Demonstrated the computational hardness of finding scale-free-like spanning trees.
- Validated the ILP approach using simulated and experimental data.
- Achieved accurate reconstruction of hepatitis C transmission histories in real-world outbreaks.
Conclusions:
- The proposed ILP-based approach is effective for reconstructing viral transmission histories.
- This work provides valuable algorithmic tools for genomic epidemiology.
- Scale-free-like spanning trees offer a promising framework for network reconstruction.
More Related Videos
11:35Screening for Functional Non-coding Genetic Variants Using Electrophoretic Mobility Shift Assay EMSA and DNA-affinity Precipitation Assay DAPA
Published on: August 21, 2016
08:27Large-Scale Multi-Omics Genome-Wide Association Studies Mo-GWAS: Guidelines for Sample Preparation and Normalization
Published on: July 27, 2021
Related Concept Videos
Genome-wide Association Studies-GWAS
GWAS does not require the identification of the target gene involved in...
Evolutionary Relationships through Genome Comparisons
Statistical Software for Data Analysis and Clinical Trials
Survival Tree
Building a Survival Tree
Constructing a...
Applications of Molecular Taxonomy
Statistical Methods for Analyzing Epidemiological Data