Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Integer programming approaches to haplotype inference by pure parsimony.

Daniel G Brown1, Ian M Harrower

  • 1David R. Cheriton School of Computer Science, University of Waterloo, 200 University Ave. West, Waterloo, ON N2L 3G1 Canada. browndg@cs.uwaterloo.ca

IEEE/ACM Transactions on Computational Biology and Bioinformatics
|October 20, 2006
PubMed
Summary

This study introduces a new integer programming (IP) formulation to efficiently solve the Haplotype Inference by Pure Parsimony (HIPP) problem. The enhanced IP approach improves upon existing methods, enabling faster analysis of complex genotype data.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Large-scale land acquisitions exacerbate local farmland inequalities in Tanzania.

Proceedings of the National Academy of Sciences of the United States of America·2023
Same author

Carbon emissions from the global land rush and potential mitigation.

Nature food·2023
Same author

Computational Creativity and Aesthetics with Algorithmic Information Theory.

Entropy (Basel, Switzerland)·2021
Same author

On the Problem of Small Objects.

Entropy (Basel, Switzerland)·2021
Same author

Mean and Variance of Phylogenetic Trees.

Systematic biology·2019
Same author

Estimating local biodiversity change: a critique of papers claiming no net loss of local diversity.

Ecology·2016

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Genetics

Background:

  • The Haplotype Inference by Pure Parsimony (HIPP) problem, introduced by Gusfield in 2003, is crucial for genetic analysis.
  • Gusfield's initial integer programming (IP) solution, while effective for small datasets, suffers from potential exponential size complexity.
  • Previous research has focused on developing polynomial-sized IP formulations to address the scalability limitations of earlier methods.

Purpose of the Study:

  • To advance integer programming (IP) approaches for the Haplotype Inference by Pure Parsimony (HIPP) problem.
  • To introduce novel valid cuts and a hybrid IP formulation to enhance computational efficiency and problem-solving capacity.
  • To provide a comprehensive empirical comparison of different IP formulations on diverse genotype datasets.

Related Experiment Videos

Main Methods:

  • Extension of existing polynomial-sized integer programming (IP) formulations for HIPP by incorporating new classes of valid cuts.
  • Development of a novel hybrid IP formulation that combines strengths of two prior approaches.
  • Empirical evaluation and comparison of the proposed IP formulations against existing methods using simulated and real genotype sequences.

Main Results:

  • The new hybrid IP formulation effectively solves complex HIPP instances that were intractable for exponential-sized formulations.
  • The proposed formulation demonstrates improved performance and efficiency in analyzing both simulated and real genotype data.
  • The enhanced IP approach offers flexibility for future extensions, including error tolerance and population structure modeling.

Conclusions:

  • The novel hybrid IP formulation represents a significant advancement in solving the Haplotype Inference by Pure Parsimony (HIPP) problem.
  • This approach enhances the efficiency and scalability of haplotype inference, particularly for complex genetic datasets.
  • The developed method provides a robust framework for future research in computational genomics and population genetics.