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单倍型通道的高效精确算法，以提高效率。这项工作的最终成果将是一个全基因组单倍型重建的算法框架，该框架将结合新的算法和克拉克一致性图数据结构和算法创建。

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.