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.