AF: Small: Algorithms for Genetics: Epistatic Interactions, Haplotype Assembly, and Selection Signatures

遗传学算法：上位性相互作用、单倍型组装和选择信号我们DNA的变异(通常是遗传的)可能会产生重要的功能后果，包括疾病的易感性。然而，许多变化是由于随机漂移造成的，可能没有功能上的后果。识别在功能上重要的一小部分变异是深入了解疾病和其他表型遗传基础的关键，也是统计遗传学和其他领域的支柱。然而，基因组测序成本的迅速下降意味着整个种群的基因组将完全测序。大量遗传数据的可获得性，以及基因型和表型之间关系的复杂性，将推理问题的性质从统计转变为计算，并要求使用算法(组合和机器学习)技术。在这项提案中，PI提出了三个广泛领域的具体目标，这三个领域涉及使用算法技术来解决遗传学问题。1.上位性互作与几何嵌入：上位性互作是指两个遥远的基因座相互作用共同调节表型，这往往会混淆分析。然而，由于有数百万个基因座，测试所有基因对的相互作用在计算上是困难的。PI建议为这个问题开发快速算法。这种方法依赖于一种度量嵌入的发展，该度量嵌入将一个基因座上的基因类型映射到高维欧几里德度量中的一个点，使得相互作用的对具有较小的欧几里得距离。这种度量嵌入是新颖的，并且允许使用几何算法来快速检测上位性。单倍型组装：单倍型是指分离母本和父本的染色体。成功的解析对于提高遗传关联的有效性，了解种群的遗传史有着重要的影响。PI建议使用现代频闪测序技术和单基因组扩增来显著延长可实现的单倍型的长度。其中一个公式化的问题自然地映射到一类新的随机图中的连通性。混合选择：PI建议使用下一代测序数据来识别基因选择下的区域。具体地说，拟议的测试针对的是汇集的DNA和部分抽样的DNA，并采用了群体遗传学和组合优化的技术组合。广泛的影响和智力价值基因组学的巨大希望是，我们的完整序列将成为我们医疗记录的组成部分，主要的健康预测将通过变异获得信息。然而，由于缺乏分析工具，早期关于基因和表型相关性的研究受到阻碍。这里讨论的问题是该领域的核心问题，显然将增加遗传学家和生物学家的工具箱。这项研究还直接有助于CEISE-CCF为计算生物学开发新算法的使命，因为所提出的问题是在算法和遗传学的交叉点上独一无二的，并开辟了计算机科学研究的新途径。在整个项目过程中，将继续进行传播和宣传，以促进这项研究的更广泛影响。它将包括邀请和贡献的演示文稿、出版物、课堂项目和合作。软件将作为源代码或网络工具免费提供，用于学术、研究和非商业目的，增加遗传分析工具的基础设施。

Algorithms for genetics: epistatic interactions, haplotype assembly, and selection signaturesVariation in our DNA (often inherited) can have important functional consequences, including susceptibility to diseases. However, much of variation is due to random drift and may have no functional consequence. Identifying the small subset of variations that are functionally important is key to a deeper understanding of the genetic basis of diseases and other phenotypes, and is the mainstay of statistical genetics and other fields. However, rapidly falling costs of genome sequencing implies that genomes of entire populations will be completely sequenced. The availability of tremendous amounts of genetic data, and the complexity of relations between genotypes and phenotypes changes the nature of inference problems from statistical to computational, and demands the use of algorithmic (combinatorial and machine learning) techniques. In this proposal, the PIs propose specific goals in three broad areas, which involve the use of algorithmic techniques in solving problems in genetics. 1. Epistatic interactions and geometric embedding: Epistatic interactions where two distant loci interact to jointly mediate the phenotype often confound analyses. However, with millions of loci, testing all pairs for interactions is computationally intractable. The PIs propose to develop fast algorithms for this problem. The approach depends upon the development of a metric embedding that maps the genotypes at a locus to a point in a high dimensional Euclidean metric, such that interacting pairs have small Euclidean distances. This metric embedding is novel, and allows the use of geometric algorithms for fast detection of epistasis.2. Haplotype assembly: Haplotyping refers to the separation of the maternal and paternal chromosomes. Successful resolution has great impact in improving the efficacy of genetic association, and in understanding the genetic history of the population. The PIs propose the use of modern strobe-sequencing technologies and single genome amplification to dramatically expand the length of achievable haplotypes. One of the formulated problems maps naturally to connectivity in a new class of random graphs.3. Pooled selection: The PIs propose the identification of regions under genetic selection, using next generation sequencing data. Specifically, the proposed tests work on pooled DNA, and partially sampled DNA, and employ a combination of techniques from population genetics and combinatorial optimization.Broader Impact and Intellectual MeritThe great promise of genomics is that our complete sequence will be an integral part of our medical record, and the major health prognostics will be informed by variation. However, the early research in correlating genotypes and phenotypes is stymied by lack of analysis tools. The problems addressed here are central to the domain and will clearly add to the toolkit of geneticists and biologists. The research also contributes directly to the CISE-CCF mission of developing novel algorithms for Computational Biology, as the proposed problems are uniquely at the intersection of algorithmic and genetics, and open new avenues of research in Computer Science. Dissemination and outreach will continue through the length of the project contributing to the broader impact of this research. It will include invited and contributed presentations, publications, classroom projects, and collaborations. Software will be freely available as source-code, or web-tools, for academic, research and non-commercial purposes adding to the infrastructure of genetic analyses tools.