Related Experiment Video
Updated: Jun 4, 2026

Heuristic Mining of Hierarchical Genotypes and Accessory Genome Loci in Bacterial Populations
Published on: December 7, 2021
Mathematical properties and bounds on haplotyping populations by pure parsimony
1Department of Industrial and Information Management, National Cheng Kung University, No.1 University Rd., Tainan 701, Taiwan. ilinwang@mail.ncku.edu.tw
Abstract:
Although the haplotype data can be used to analyze the function of DNA, due to the significant efforts required in collecting the haplotype data, usually the genotype data is collected and then the population haplotype inference (PHI) problem is solved to infer haplotype data from genotype data for a population. This paper investigates the PHI problem based on the pure parsimony criterion (HIPP), which seeks the minimum number of distinct haplotypes to infer a given genotype data. We analyze the mathematical structure and properties for the HIPP problem, propose techniques to reduce the given genotype data into an equivalent one of much smaller size, and analyze the relations of genotype data using a compatible graph. Based on the mathematical properties in the compatible graph, we propose a maximal clique heuristic to obtain an upper bound, and a new polynomial-sized integer linear programming formulation to obtain a lower bound for the HIPP problem.
Related Concept Videos
Hardy-Weinberg Principle
Evolutionary Relationships through Genome Comparisons
Mutation, Gene Flow, and Genetic Drift
What is Population Genetics?
Probability Laws
Gene Evolution - Fast or Slow?
In contrast, regions which code...

