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

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.