III: Small: Genome-Wide Algorithms for Haplotype Reconstruction and Beyond: A Combined Haplotype Assembly and Identical-by-Descent Tracts Approach

该项目将发展严谨和快速（实用）图论全基因组算法与基因组序列数据和图形在一套综合的研究和教育活动，旨在与统计建模相互协同;将这些应用于现实世界的问题和长期存在的计算机科学和数学问题的解决方案，影响分子生物学;并使学生、研究人员和相应领域的从业人员能够使用这些技术。该项目的重点是从具有不同多倍性数目的各种生物体和基因组的基因组序列数据中重建单倍型的算法，即，单倍型的数量。包括人类在内的哺乳动物基因组是二倍体基因组。然而，多倍体的数量在整个生命谱中从1（细菌）到超过100（蛇舌蕨）不等。HapCompass图论框架将基因组测序读段映射与人类基因组中的全基因组SNP数据相关联。HapCompass算法在HapCompass图的生成树循环基础上使用局部优化算法，用于对单倍型重建中的各种误差校正措施进行建模的目标函数。早期的工作提供了一个组合框架的错误校正模型的二倍体单倍型组装，一个框架所包含的大量文献的主题在接下来的十年。二倍体基因组的基本情况和HapCompass图论、数据结构和算法为在通过血统共享相同的单倍型区域的个体的样本中推广到多倍性和整合的全基因组单倍型重建奠定了基础。 此外，课程开发是从计算和用户的角度涵盖主题的计划。 所有材料和软件、源代码和文档都将可用。 软件将依赖于开放源代码模型。该项目将计算机科学与统计模型交织在一起，并对基因组学和分子生物学产生影响。 将开发基于多标准优化的更快和更准确的二倍体单倍型组装算法，该算法使用在罗盘图的生成树循环基础上的多个误差校正模型。 此外，强大的概括的图论和算法的多倍体基因组，允许一个共同的算法策略的计划。 该团队还正在开发一种最佳线性时间算法，用于在分阶段基因型数据的情况下进行共享IBD道识别，以及用于在非分阶段基因型数据中进行共享IBD道的IBD单倍型道识别的有效和精确算法，这些数据在单倍型数量上是线性的，在基因型数量上是次二次的，以提高效率。 这项工作的最终产品将是一个全基因组单倍型重建的算法框架，该框架是通过将新算法与Clark Consistency Graph数据结构和算法相结合而创建的。

The project will develop rigorous and fast (practical) graph-theoretic genome-wide algorithms associated with genome sequence data and graphs within an integrated set of research and educational activities designed to intertwine synergistically with statistical modeling; apply these to the solution of real-world problems and long-standing computer science and mathematics questions that impact molecular biology; and make these techniques accessible to students, researchers, and practitioners in the corresponding fields. The project focuses on algorithms for haplotype reconstruction from genome sequence data of various organisms and genomes having different polyploidy number, i.e., number of haplotypes. The mammalian genomes, human included, are diploid genomes. However, the polyploidy number varies across the life spectrum from 1 (bacteria) to more than 100 (adder's-tongue fern). The HapCompass graph-theoretic framework associates genome sequencing read mappings with the genome-wide SNP data in the human genome.The HapCompass algorithm uses local optimization algorithms on the spanning tree cycle basis of HapCompass graphs for objective functions that model various measures of error correction in haplotype reconstruction. Earlier work provided a combinatorial framework for error-correction models for diploid haplotype assembly, a framework embraced by the large literature on the topic in the following decade. The fundamental case of diploid genomes and the HapCompass graph theory, data structures and algorithms set the stage for generalizations to polyploidy and integrative genome-wide haplotype reconstruction in samples of individuals that share haplotypic regions identical by descent. In addition, curriculum development is plan that covers the topics from both a computing and the user perspective. All materials and software, source code, and documentation will be available. Software will rely on the open-source model.This project intertwines computer science with statistical models and an impact in genomics and molecular biology. Faster and more accurate algorithms for diploid haplotype assembly based on multi-criteria optimization using multiple models of error correction on the spanning-tree cycle bases of compass graphs will be developed. In addition, robust generalizations of the graph theory and algorithms for polyploid genomes that permit a common algorithmic strategy are planned. The team also is developing an optimal linear time algorithm for shared IBD tract identification in the case of phased genotype data, and efficient and exact algorithms for IBD haplotype tract identification for shared IBD tracts in unphased genotype data that are linear in the number of haplotypes and subquadratic in the number of genotypes to enhance efficiency. The final product of the work will be an algorithmic framework for genome-wide haplotype reconstruction created by combining the new algorithms and Clark Consistency Graph data structures and algorithms.