AF: Small: Algorithms for Haplotype Assembly from Next-Generation Sequencing Data

人类是二倍体生物，有两组染色体：22对常染色体和一对性染色体。一对常染色体中的两条染色体是同源的，即它们具有相似的DNA序列，本质上携带相同类型的信息，但不完全相同。一对染色体之间最常见的变异类型是两个序列中特定位置的碱基不同，即同源染色体上相应的等位基因不同。单个基因组中DNA变异的完整信息是由单倍型提供的，单倍型是在单个染色体的一个区域的连续位点上的等位基因列表。单倍型信息对医学和制药研究至关重要，包括了解基因表达和重组模式的变化。智力优势：本研究旨在从下一代测序数据中开发和分析单倍型组装的新算法。它主要包括三个方面：(1)从下一代测序数据中进行单倍型组装在计算上具有挑战性。第一个重点是提出分支定界算法，利用问题的某些结构特征来有效地找到精确的解。(2)随着单倍型组装问题的规模增大，精确的解决方案越来越难以获得。第二个重点是开发具有保证性能界限的快速启发式方法，以实现显式的复杂性-准确性权衡。(3)现有的单倍型组装方案处理包含核苷酸的DNA片段，其顺序已经由测序平台确定。第三个重点是开发用于寻找碱基调用和单倍型组装问题联合解决方案的算法，从而显著提高准确性。更广泛的影响：这项研究的结果将对许多依赖精确单倍型组装的领域产生重大影响，包括医学和药物基因组学，并将丰富德克萨斯大学奥斯汀分校工程专业学生的教育经验。

Humans are diploid organisms with two sets of chromosomes: 22 pairs of autosomes and one pair of sex chromosomes. The two chromosomes in a pair of autosomes are homologous, i.e., they have similar DNA sequences and essentially carry the same type of information but are not identical. The most common type of variation between chromosomes in a pair is that where the base in a specific location differs between the two sequences, i.e., the corresponding alleles on the homologous chromosomes are different. The complete information about DNA variations in an individual genome is provided by haplotypes, the list of alleles at contiguous sites in a region of a single chromosome. Haplotype information is essential for medical and pharmaceutical studies, including understanding variations in gene expressions and recombination patterns.Intellectual Merit:This research aims to develop and analyze novel algorithms for haplotype assembly from next-generation sequencing data. It consists of three main thrusts: (1) Haplotype assembly from next-generation sequencing data is computationally challenging. The first thrust proposes branch-and-bound algorithms that exploit certain structural features of the problem to efficiently find the exact solution. (2) As the size of the haplotype assembly problem grows, the exact solution is increasingly more difficult to obtain. The second thrust is focused on the development of fast heuristic methods with guaranteed performance bounds that enable explicit complexity-accuracy trade-offs. (3) Existing haplotype assembly schemes process DNA fragments comprising nucleotides whose order is already determined by the sequencing platform. The third thrust is focused on the development of algorithms for finding joint solution to the base-calling and haplotype assembly problems, enabling significant improvements in accuracy.Broader Impact:The results of this research will have a major impact on a number of fields that rely on accurate haplotype assembly, including medicine and pharmacogenomics, and will enrich the educational experience of engineering students at the University of Texas at Austin.