Computational Problems in Noisy SNP and Haplotype Analysis: Block Scores, Block Identification, and Population Stratification

References

• Alon N., Spencer J. H.The Probabilistic Method (2000) (John Wiley and Sons, Inc., New York) Crossref, Google Scholar
• Bafna V., Halldorsson B. V., Schwartz R., Clark A., Istrail S. Haplotyles and informative SNP selection algorithms: Don't block out information. Proc. Seventh Annual Internat. Conf. Res. Comput. Molecular Biol. (RECOMB) (2003) (The Association for Computing Machinery, New York) 19–27Google Scholar
• Clark A. Inference of haplotypes from PCR-amplified samples of diploid populations. Molecular Biol. Evolution (1990) 7:111–122Google Scholar
• Cormen T. H., Leiserson C. E., Rivest R. L.Introduction to Algorithms (1990) (MIT Press, Cambridge, MA) Google Scholar
• Daly M. J., Rioux J. D., Schaffner S. F., Hudson T. J., Lander E. S. High-resolution haplotype structure in the human genome. Nature Genetics (2001) 29(2):229–232Crossref, Google Scholar
• Eskin E., Halperin E., Karp R. M. Large scale reconstruction of haplotypes from genotype data. Proc. Seventh Annual Internat. Conf. Res. Comput. Molecular Biol. (RECOMB) (2003) (The Association for Computing Machinery, New York) 104–113Crossref, Google Scholar
• Gabriel S. B., Schaffner S. F., Nguyen H., Moore J. M., Roy J., Blumenstiel B., Higgins J., DeFelice M., Lochner A., Faggart M., Liu-Cordero S. N., Rotimi C., Adeyemo A., Cooper R., Ward R., Lander E. S., Daly M. J., Altshuler D. The structure of haplotype blocks in the human genome. Science (2002) 296:2225–2229Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman and Co., San Francisco, CA) Google Scholar
• Gusfield D. Inference of haplotypes in samples of diploid populations: Complexity and algorithms. J. Comput. Biol. (2001) 8(3):305–323Crossref, Google Scholar
• Gusfield D. Haplotype by pure parsimony. Proc. Fourteenth Annual Sympos. Combin. Pattern Matching (CPM), Morelia, Mexico (2003) (Springer, Berlin) 144–155Google Scholar
• Halldorsson B. V., Bafna V., Edwards N., Lippert R., Yooseph S., Istrail S. Combinatorial problems arising in SNP. Discrete Math. Theoret. Comput. Sci. Lecture Notes in Computer Science (2003) (Springer-Verlag, Heidelberg, Germany) 26–47No. 2731Crossref, Google Scholar
• Hubbell E. Finding a parsimony solution to haplotype phase is NP-hard. (2003) (Affymetrix Inc., Santa Clara, CA) . Unpublished manuscriptGoogle Scholar
• Kimmel G., Sharan R., Shamir R. Identifying blocks and sub-populations in noisy SNP data. Proc. Third Workshop Algorithms in Bioinformatics (WABI) (2003) (Springer-Verlag, Berlin) 303–319Crossref, Google Scholar
• Koivisto M., Perola M., Varilo T., Hennah W., Ekelund J., Lukk M., Peltonen L., Ukkonen E., Mannila H. An MDL method for finding haplotype blocks and for estimating the strength of haplotype block boundaries. Proc. Pacific Sympos. Biocomputing (PSB), Big Island of Hawaii, Hawaii (2003) 8(World Scientific, Singapore) 502–513Google Scholar
• Kruglyak L., Nickerson D. A. Variation is the spice of life. Nature Genetics (2001) 27:234–236Crossref, Google Scholar
• MacQueen J. Some methods for classification and analysis of multivariate observations. Proc. Fifth Berkeley Sympos. Math. Statist. Probab. (1965) (University of California Press, Berkeley, CA) 281–297Google Scholar
• Ostrovsky R., Rabani Y. Polynomial time approximation schemes for geometric k-clustering. J. Assoc. Comput. Mach. (2002) 49:139–156Crossref, Google Scholar
• Patil N., Berno A. J., Hinds D. A., Barrett W. A., Doshi J. M., Hacker C. R., Kautzer C. R., Lee D. H., Marjoribanks C., McDonough D. P., Nguyen B. T., Norris M. C., Sheehan J. B., Shen N., Stern D., Stokowski R. P., Thomas D. J., Trulson M. O., Vyas K. R., Frazer K. A., Fodor S. P., Cox D. R. Blocks of limited haplotype diversity revealed by high-resolution scanning of human chromosome 21. Science (2001) 294:1719–1723Crossref, Google Scholar
• Sachidanandam R., Weissman D., Schmidt S. C., Kakol J. M., Stein L. D., Marth G., Sherry S., Mullikin J. C., Mortimore B. J., Willey D. L., Hunt S. E., Cole C. G., Coggill P. C., Rice C. M., Ning Z., Rogers J., Bentley D. R., Kwok P. Y., Mardis E. R., Yeh R. T., Schultz B., Cook L., Davenport R., Dante M., Fulton L., Hillier L., Waterston R. H., McPherson J. D., Gilman B., Schaffner S., Van Etten W. J., Reich D., Higgins J., Daly M. J., Blumenstiel B., Baldwin J., Stange-Thomann N., Zody M. C., Linton L., Lander E. S., Altshuler D. A map of human genome sequence variation containing 1.42 million single nucleotide polymorphisms. Nature (2001) 291:1298–2302Google Scholar
• Venter J. Craig, Adams M. D., Myers E. W., Li P. W., Mural R. J., Sutton G. G., Smith H. O., Yandell M., Evans C. A., Holt R. A., Gocayne et al J. D. The sequence of the human genome. Science (2001) 291:1304–1351Crossref, Google Scholar
• Waterman M. S.Introduction to Computational Biology: Maps, Sequences and Genomes (1995) (Chapman and Hall)Crossref, Google Scholar
• Zhang K., Deng M., Chen T., Waterman M. S., Sun F. A dynamic programming algorithm for haplotype block partitioning. Proc. National Acad. Sci. USA (2002) 99:7335–7339Crossref, Google Scholar