A Set-Covering Approach with Column Generation for Parsimony Haplotyping

References

• Bafna V., Gusfield D., Lancia G., Yooseph S. Haplotyping as perfect phylogeny: A direct approach. J. Computational Biol. (2003) 10(3–4):323–340Crossref, Google Scholar
• Brown D. G., Harrower I. M. A new integer programming formulation for the pure parsimony problem in haplotype analysis. Annual Workshop on Algorithms in Bioinformatics (WABI), Lecture Notes in Computer Science (2004) (Springer, Berlin) 254–265Crossref, Google Scholar
• Brown D. G., Harrower I. M. A new formulation for haplotype inference by pure parsimony. (2005) . Technical report, Department of Computer Science, University of Waterloo, Waterloo, ON, CanadaGoogle Scholar
• Brown D. G., Harrower I. M. Integer programming approaches to haplotype inference by pure parsimony. IEEE/ACM Trans. Computational Biol. Bioinformatics (2006) 3:348–359Crossref, Google Scholar
• Eskin E., Halperin E., Karp R. Efficient reconstruction of haplotype structure via perfect phylogeny. J. Bioinformatics Computational Biol. (2003) 1(1):1–20Crossref, Google Scholar
• Gusfield D. A practical algorithm for optimal inference of haplotypes from diploid populations. Annual Internat. Conf. Intelligent Systems for Molecular Biol. (ISMB) (2000) (AAAI Press, Menlo Park, CA) 183–189Google Scholar
• Gusfield D. Inference of haplotypes from samples of diploid populations: Complexity and algorithms. J. Computational Biol. (2001) 8(3):305–324Crossref, Google Scholar
• Gusfield D. Haplotype inference by pure Parsimony. Annual Sympos. Combin. Pattern Matching, Lecture Notes in Computer Science (2003) 2676(Springer, Berlin) 144–155Crossref, Google Scholar
• Gusfield D., Orzack S. H. Haplotype inference. Handbook of Computational Molecular Biology (2005) (Chapman Hall/CRC-Press, Boca Raton, FL) 1–28Crossref, Google Scholar
• Halldorsson B., Istrail S., Sharan R. Islands of tractability for parsimony haplotyping. IEEE/ACM Trans. Computational Biol. Bioinformatics (2006) 3(3):303–311Crossref, Google Scholar
• Halldorsson B., Bafna V., Edwards N., Lippert R., Yooseph S., Istrail S. A survey of computational methods for determining haplotypes. Computational Methods for SNP and Haplotype Inference: DIMACS/RECOMB Satellite Workshop, Lecture Notes in Computer Science (2004) 2983(Springer, Berlin) 26–47Crossref, Google Scholar
• Huang Y. T., Chao K. M., Chen T. An approximation algorithm for haplotype inference by maximum parsimony. Proc. 2005 ACM Sympos. Appl. Comput. (SAC) (2005) Sante Fe, NM(ACM, New York) 146–150Crossref, Google Scholar
• Hudson R. Generating samples under the Wright-Fisher neutral model of genetic variation. Bioinformatics (2002) 18(2):337–338Crossref, Google Scholar
• Hudson R. Hudson Lab Home Page. (2003) . Retrieved March 2008, http://home.uchicago.edu/∼rhudson1Google Scholar
• International HapMap Consortium The International HapMap project. Nature (2003) 426(6968):789–796Crossref, Google Scholar
• International HapMap Consortium A haplotype map of the human genome. Nature (2005) 437(7063):1299–1320Crossref, Google Scholar
• International Human Genome Sequencing Consortium Initial sequencing and analysis of the human genome. Nature (2001) 409(6822):860–921Crossref, Google Scholar
• Kalpakis K., Namjoshi P. Haplotype phasing using semidefinite programming. Fifth IEEE Sympos. Bioinformatics Bioengineering (BIBE 2005) (2005) 19(IEEE Computer Society, Washington, D.C.) 145–152Crossref, Google Scholar
• Kimmel G., Shamir R. Gerbil: Genotype resolution and block identification using likelihood. Proc. National Acad. Sci. (2005) 102(1):158–162Crossref, Google Scholar
• Lancia G., Rizzi R. A polynomial solution to a special case of the parsimony haplotyping problem. Oper. Res. Lett. (2006) 34(3):289–295Crossref, Google Scholar
• Lancia G., Pinotti C., Rizzi R. Haplotyping populations by pure parsimony: Complexity, exact and approximation algorithms. INFORMS J. Comput. (2004) 16(4):17–29Link, Google Scholar
• Lynce I., Marques-Silva J. SAT in bioinformatics: Making the case with haplotype inference. Theory Application of Satisfiability Testing—SAT06, Lecture Notes in Computer Science (2006) 4121(Springer, Berlin) 136–141Crossref, Google Scholar
• Makhorin A. GLPK (GNU Linear Programming Kit). (2003) . Retrieved March 2008, http://www.gnu.org/software/glpk/Google Scholar
• Niu T., Qin Z. S., Xu X., Liu J. S. Bayesian haplotype inference for multiple linked single-nucleotide polymorphisms. Amer. J. Human Genetics (2002) 70:157–169Crossref, Google Scholar
• SeattleSNPs Education Program SeattleSNPs. (2006) . Retrieved March 2008, http://pga.gs.washington.eduGoogle Scholar
• Stephens M., Donnelly P. A comparison of Bayesian methods for haplotype reconstruction from population genotype data. Amer. J. Human Genetics (2003) 73:1162–1169Crossref, Google Scholar
• Stephens M., Scheet P. Accounting for decay of linkage disequilibrium in haplotype inference and missing-data imputation. Amer. J. Human Genetics (2005) 76:449–462Crossref, Google Scholar
• Venter J. C., Adams M. D., Myers E. W., Li P. W., Mural R. J., Sutton G. G., Smith H. O., et al. The sequence of the human genome. Science (2001) 291(5507):1304–1351Crossref, Google Scholar
• Wang L., Xu Y. Haplotype inference by maximum parsimony. Bioinformatics (2003) 19(14):1773–1780Crossref, Google Scholar