Related Concept Videos
Gene Duplication and Divergence
The duplicated copies of the gene are called Paralogs. Paralogs with similar sequences and functions form a gene family. Across several species, a large number of gene families are...
Evolutionary Relationships through Genome Comparisons
Phylogeny
Synteny and Evolution
Around 80 million years ago, the human and mice lineages diverged from the common ancestor. During the course of evolution, the ancestral...
Genome Annotation and Assembly
Genomic DNA in Eukaryotes
You might also read
Related Articles
Articles linked to this work by shared authors, journal, and citation graph.
TruEst: a better estimator of evolutionary distance under the INFER model.
Related Experiment Video
Updated: Dec 28, 2025

Heuristic Mining of Hierarchical Genotypes and Accessory Genome Loci in Bacterial Populations
Published on: December 7, 2021
A unified ILP framework for core ancestral genome reconstruction problems.
Pavel Avdeyev1, Nikita Alexeev2, Yongwu Rong3
1Department of Mathematics, The George Washington University, Washington, DC 20052, USA.
This study introduces integer linear programming formulations for ancestral genome reconstruction, addressing genome median and halving problems. These methods accurately reconstruct ancestral genomes, combining homology and rearrangement approaches for improved biological relevance.
Area of Science:
- Computational genomics
- Bioinformatics
- Evolutionary biology
Background:
- Reconstructing ancestral genomes is crucial for understanding evolutionary history.
- Genome rearrangements and whole-genome duplications (WGDs) are major drivers of genomic change.
- Existing methods for ancestral genome reconstruction face challenges in biological relevance and accuracy.
Purpose of the Study:
- To develop novel computational methods for ancestral genome reconstruction.
- To address the genome median, genome halving, and genome aliquoting problems.
- To improve the biological relevance and accuracy of ancestral genome reconstruction.
Main Methods:
- Integer linear programming (ILP) formulations were developed for ancestral genome reconstruction problems.
- Polynomial-size ILP formulations were created for the genome median and genome halving problems.
- Restricted and conserved versions of these problems were formulated to enhance biological relevance.
Main Results:
- The proposed ILP formulations demonstrated good accuracy in reconstructing ancestral genomes.
- The ILP formulations for conserved versions of the problems have linear size, enabling practical application.
- The developed approach effectively combines homology- and rearrangements-based methods for ancestral reconstruction.
Conclusions:
- Integer linear programming provides a powerful and accurate framework for ancestral genome reconstruction.
- The novel ILP formulations, particularly for conserved versions, offer a practical and biologically relevant approach.
- This work advances the field of comparative genomics by providing robust tools for studying genome evolution.

