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

遗传算法：上位相互作用、单倍型组装和选择特征我们DNA的变异（通常是遗传的）可以产生重要的功能后果，包括对疾病的易感性。然而，许多变异是由于随机漂移，可能没有功能后果。识别功能上重要的一小部分变异是深入了解疾病和其他表型的遗传基础的关键，也是统计遗传学和其他领域的支柱。然而，基因组测序成本的迅速下降意味着整个种群的基因组将被完全测序。大量遗传数据的可用性，以及基因型和表型之间关系的复杂性改变了推理问题的性质，从统计到计算，并要求使用算法（组合和机器学习）技术。在本提案中，pi在三个广泛的领域提出了具体的目标，这些领域涉及使用算法技术来解决遗传学问题。1. 上位相互作用和几何嵌入：上位相互作用，其中两个遥远的位点相互作用共同介导表型经常混淆分析。然而，对于数以百万计的基因座，测试所有对的相互作用在计算上是难以处理的。pi建议开发快速算法来解决这个问题。该方法依赖于一种度量嵌入的发展，该嵌入将基因型映射到高维欧几里得度量中的一个点，这样相互作用的对具有小的欧几里得距离。这种度量嵌入是新颖的，允许使用几何算法来快速检测上位性。单倍型组装：单倍型是指母亲和父亲染色体的分离。成功的解决对提高遗传关联的有效性和了解群体的遗传史有很大的影响。pi建议使用现代频闪测序技术和单基因组扩增来显著扩大可实现的单倍型的长度。其中一个公式化的问题自然地映射到一类新的随机图中的连通性。集合选择：pi利用下一代测序数据提出遗传选择下的区域识别。具体来说，所提出的测试适用于汇集的DNA和部分采样的DNA，并采用群体遗传学和组合优化技术的组合。更广泛的影响和智力价值基因组学的伟大前景是，我们的完整序列将成为我们医疗记录的一个组成部分，主要的健康预测将由变异来提供信息。然而，由于缺乏分析工具，对基因型和表型相关性的早期研究受到了阻碍。这里讨论的问题是该领域的核心问题，显然会增加遗传学家和生物学家的工具包。这项研究也直接有助于CISE-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.