Related Experiment Videos
A note on efficient computation of haplotypes via perfect phylogeny
Vineet Bafna1, Dan Gusfield, Sridhar Hannenhalli
1Department of Computer Science & Engineering, University of California at San Diego, La Jolla, CA 92093, USA. vbafna@cs.ucsd.edu
Summary
Inferring haplotype phase is computationally challenging. This study shows that speeding up existing algorithms for the perfect phylogeny haplotyping problem is not possible with current methods, and finding the most parsimonious solution is NP-hard.
Area of Science:
- Computational Biology
- Genetics
- Bioinformatics
Background:
- Haplotype phase inference is crucial for understanding genomic variation.
- Recent advances in haplotyping algorithms address regions with rare recombination.
- The perfect phylogeny haplotyping (PPH) problem is a key area in this field.
Purpose of the Study:
- To investigate the time complexity of existing PPH algorithms.
- To determine if a more efficient linear time solution exists.
- To assess the computational difficulty of finding a parsimonious PPH solution.
Main Methods:
- Reductions to Boolean matrix multiplication to analyze time complexity.
- NP-hardness proof via reduction from the Vertex Cover problem.
Main Results:
- Existing PPH algorithms cannot be sped up to achieve linear time complexity.
- The best achievable time bound is O(nm(omega-1)), related to matrix multiplication exponent.
- Finding a PPH solution that minimizes distinct haplotypes is NP-hard.
Conclusions:
- Linear time solutions for PPH likely require novel algorithmic approaches.
- The problem of finding the most parsimonious haplotype solution is computationally intractable for large datasets.