Haplotype Tagging and Its Approximation Properties
Author Information
Author(s): Vinterbo Staal, Dreiseitl Stephan, Ohno-Machado Lucila
Primary Institution: Brigham and Women's Hospital
Hypothesis
Can we find an efficient algorithm for the haplotype tagging problem despite its NP-hardness?
Conclusion
The haplotype tagging problem is hard, but can be approached with a simple and fast algorithm that is optimal with respect to its approximation bounds.
Supporting Evidence
- The haplotype tagging problem is NP-hard but can be approximated within specific bounds.
- A simple algorithm is presented that runs in polynomial time and achieves the approximation bounds.
- The study connects the haplotype tagging problem to the minimum set cover problem.
Takeaway
This study shows that even though finding the best solution for haplotype tagging is really hard, we can still find a good enough solution quickly using a simple method.
Methodology
The study presents algorithms for the minimum haplotype tagging problem, analyzing their approximation properties and running times.
Limitations
The algorithms may not significantly improve upon the approximation bounds in polynomial time.
Digital Object Identifier (DOI)
Want to read the original?
Access the complete publication on the publisher's website