Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms

References

• Alimonti P., Kann V. Hardness of approximating problems on cubic graphs. Theroet. Comput. Sci. (2000) 237:123–134Crossref, Google Scholar
• Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M.Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties (1999) (Springer, Berlin, Germany) Google Scholar
• Bafna V., Gusfield D., Lancia G., Yooseph S. Haplotyping as perfect phylogeny: A direct approach. J. Comput. Biol. (2003) 10:323–340Crossref, Google Scholar
• Bar-Yehuda R., Even S. A local-ratio theorem for approximating the weighted vertex cover problem. Ann. Discrete Math. (1985) 25:27–46Google Scholar
• Berman P., Karpinski M. On some tighter inapproximability results. (1998) . Technical report ECCC No. 29, Department of Computer Science, University of Trier, Trier, GermanyGoogle Scholar
• Chakravarti A. It's raining SNP, hallelujah? Nature Genetics (1998) 19:216–217Crossref, Google Scholar
• Chen J., Kanj I. A., Jia W. Vertex cover: Further observations and further improvements. J. Algorithms (2001) 41:280–301Crossref, Google Scholar
• Clark A. Inference of haplotypes from PCR-amplified samples of diploid populations. Molecular Biol. Evolution (1990) 7:111–122Google Scholar
• Eskin E., Halperin E., Karp R. Efficient reconstruction of haplotype structure via perfect phylogeny. J. Bioinformatics Comput. Biol. (2003) 1:1–20Crossref, Google Scholar
• Gusfield D. A practical algorithm for optimal inference of haplotypes from diploid populations. Annual Internat. Conf. Intelligent Systems Molecular Biol. (2000) (AAAI Press, Menlo Park, CA) 183–189Google Scholar
• Gusfield D. Inference of haplotypes from samples of diploid populations: Complexity and algorithms. J. Comput. Biol. (2001) 8:305–324Crossref, Google Scholar
• Gusfield D. Haplotype inference by pure parsimony. Annual Sympos. Combin. Pattern Matching. Springer Lecture Notes in Computer Science (2003) (Springer-Verlag, Berlin, Germany) 144–155No. 2676Crossref, Google Scholar
• Helmuth L. Genome research: Map of the human genome 3.0. Science (2001) 293:583–585Crossref, Google Scholar
• Hubbel E. Personal communication. (2002) Google Scholar
• International Human Genome Sequencing Consortium Initial sequencing and analysis of the human genome. Nature (2001) 409:860–921Crossref, Google Scholar
• Lancia G., Bafna V., Istrail S., Lippert R., Schwartz R. SNPs problems, complexity and algorithms. Annual Eur. Sympos. Algorithms. Springer Lecture Notes in Computer Science (2001) (Springer-Verlag, Berlin, Germany) 182–193No. 2161Crossref, Google Scholar
• Li L., Kim J. H., Waterman M. Haplotype reconstruction from SNP alignment. ACM Annual Internat. Conf. Comput. Molecular Biol. (2003) (ACM Press, New York) 207–216Crossref, Google Scholar
• Lippert R., Schwartz R., Lancia G., Istrail S. Algorithmic strategies for the SNPs haplotype assembly problem. Briefings Bioinformatics (2002) 3:23–31Crossref, Google Scholar
• Marshall E. Drug firms to create public database of genetic mutations. Sci. Magazine (1999) 284:406–407Google Scholar
• Nemhauser G. L., Trotter L. E. Vertex packings: Structural properties and algorithms. Math. Programming (1975) 8:232–248Crossref, Google Scholar
• Papadimitriou C. H., Yannakakis M. Optimization, approximation, and complexity classes. J. Comput. System Sci. (1991) 43:425–440Crossref, Google Scholar
• Rizzi R., Bafna V., Istrail S., Lancia G. Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem. Annual Workshop on Algorithms in Bioinformatics. Springer Lecture Notes in Computer Science (2002) (Springer-Verlag, Berlin, Germany) 29–43No. 2452Crossref, Google Scholar
• Venter J. C., et al. The sequence of the human genome. Science (2001) 291:1304–1351Crossref, Google Scholar