CAREER: Combinatorial Algorithms for High-Throughput Collection and Analysis of Genomic Diversity Data

大规模病例/对照和人口研究的基因组多样性分析有望为从确定疾病易感性的遗传基础到揭示历史人口迁移模式等基本问题提供答案。然而，这些研究的可行性主要取决于解决一些技术和计算方面的挑战。在技术方面，尽管近年来取得了巨大的进步，但仍然需要一个灵活的高通量平台，能够在每次实验中以非常低的成本输入数十万个snp。在计算方面，有必要将最近开发的人类基因组变异结构统计模型与有效的组合方法相结合，以提供可预测的解决方案质量。拟议的研究和教育活动将在几个层面上解决上述挑战，包括对潜在的生物和技术问题进行建模和形式化，为已确定的问题找到有效的算法，将这些算法设计成高质量的开源生物信息学工具，并与行业研究人员和分子遗传学家密切合作，验证拟议的方法并将其应用于人口规模的基因组数据。主要项目成果将包括：(1)开发一种创新的高通量SNP基因分型分析方法，通过与溶液相单碱基扩展相结合，实现k-mer阵列尚未实现的潜力；(2)优化两种常用的SNP基因分型技术——DNA标签阵列和多重pcr。(3)具有可预测解质量的新颖似然最大化算法，用于解决两阶段抽样设计关联研究中出现的具有挑战性的计算问题，包括单倍型标记SNP选择和基因型数据的单倍型重建；(4)稳健的开源软件实现和对所提出算法进行实证评估的原则方法；(5)创新的课程和教育材料；包括编写关于计算基因组学的新教科书。项目的成功完成将降低大型关联研究的数据收集成本，从而在相同的预算范围内完成更多的研究。拟议的基于k-mer阵列的分析架构有望实现基因组技术的其他应用，例如基于基因组学的即时医疗诊断和大规模物种鉴定。拟议的教育和外联活动的更广泛影响包括增加代表性不足的群体参与研究和培训具有独特跨学科技能的未来研究人员。

Genomic diversity analyses of large-scale case/control and population studies promise to provide answers to fundamental problems ranging from determining the genetic basis of disease susceptibility to uncovering the pattern of historical population migrations. However, the feasibility of such studies critically depends on addressing a number of technological and computational challenges. On the technological front, despite the huge advances made in recent years, there is still a need for a flexible high-throughput platform capable of typing hundreds of thousands of SNPs at a very low-cost per experiment.Computationally, there is a need for integrating recently developed statistical models of the structure of genomic variability in human populations with efficient combinatorial methods delivering predictable solution quality.The proposed research and education activities will address the above challenges at several levels, including modeling and formalizing the underlying biological and technological problems, finding efficient algorithms for the identified problems, engineering these algorithms into high-quality open-source bioinformatics tools, and collaborating closely with industry researchers and molecular geneticists in validating the proposed methods and applying them to population-scale genomic data. Major project outcomes will include (1) development of an innovative high-throughput SNP genotyping assay realizing a yet unrealized potential of k-mer arrays by combination with solution-phase single-base extension, (2) optimization of two proven technologies that are in common use in SNP genotyping - DNA tag arrays and multiplex-PCR, (3) novel likelihood maximization algorithms with predictable solution quality for challenging computational problems arising in two-stage sampling design association studies, including haplotype tagging SNP selection and haplotype reconstruction from genotype data, (4) robust open-source software implementations and principled methodologies for the empirical evaluation of proposed algorithms, and (5) innovative curriculum and educational materials, including the creation of a new textbook on computational genomics. The successful completion of the project will lead to decreased data collection costs in large-scale association studies, thus enabling more studies to be completed within the same budget. The proposed assay architecture based on k-mer arrays is expected to enable additional applications of genomic technologies, such as genomics-based point-of-care medical diagnosis and large-scale species identification. Broader impacts of proposed educational and outreach activities include increasing participation of under-represented groups in research and training of future researchers with unique interdisciplinary skills.