Approximation properties of haplotype tagging
2006

Haplotype Tagging and Its Approximation Properties

publication Evidence: high

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)

10.1186/1471-2105-7-8

Want to read the original?

Access the complete publication on the publisher's website

View Original Publication