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.