Algorithmic Problems in Haplotyping, Oligonucleotide Fingerprinting,and NMR Peak Assignment

生物和生物医学科学正在经历一场重大革命，新的实验方法，如高通量DNA测序、DNA微阵列、全基因组定位和单核苷酸多态性（SNP）技术，正在产生前所未有的大量遗传数据。对这些信息的探索严重依赖于用于数据分析的先进计算方法的发展。自从最近人类基因组计划完成以来，计算生物学（或生物信息学）的重点已经转移到与生物功能更直接相关的主题，即功能基因组学和蛋白质组学中出现的计算问题。在这个项目中，PI将研究一些新的算法问题，旨在解决计算生物学中的三个重要问题：(i)如何根据给定谱系的孟德尔遗传定律从基因型数据推断单倍型配置，（ii）如何解决聚类分析中缺失的值，以及（iii）如何将核磁共振峰分配给单个氨基酸。第一个问题是利用微卫星和单核苷酸多态性等标记物对遗传疾病进行精细定位的基础。问题（ii）出现在DNA阵列实验的离散寡核苷酸指纹分析中，并在微生物群落分类中具有重要应用。问题（iii）代表了基于核磁共振的蛋白质结构测定的关键步骤。尽管上述算法问题在文献中相对较新（事实上，其中一些是最近由PI与实验学家合作引入的），但它们与众所周知的组合优化问题有很强的联系，例如二部匹配、区间调度、图团划分（或着色）和集合覆盖。因此，它们的解也可能对通用算法和组合优化社区感兴趣。

Biological and biomedical sciences are undergoing a major revolutionas new experimental approaches, such as high-throughput DNAsequencing, DNA microarray, whole genome location, andsingle nucleotide polymorphism (SNP) techniques, are yieldingunprecedented amounts of genetic data. The exploration of thisinformation is critically dependent upon the development ofadvanced computational methods for data analysis. Since the recentcompletion of the Human Genome Project, the focus of ComputationalBiology (or Bioinformatics) has shifted to topics that are moredirectly related to biological functions, i.e. computational problemsthat arise in functional genomics and proteomics.In this project, the PI will study some new algorithmic problemsthat aim at addressing three important questions incomputational biology: (i) how to infer haplotype configurations fromgenotype data based on the Mendelian law of inheritance for a givenpedigree, (ii) how to resolve missing values in clusteranalysis for oligonucleotide fingerprinting, and (iii) how toassign NMR peaks to individual amino acids. The first question isfundamental to the fine-mapping of genetic diseasesusing markers such as microsatellites and SNPs.Question (ii) arises in the analysis of discretized oligonucleotidefingerprints from DNA array experiments and has important applicationsin the classification of microbial communities. Question (iii)represents a crucial step in NMR-based protein structure determination.Although the above algorithmic problems are relatively new in theliterature (in fact, some of them were recently introduced by the PI in collaboration with experimentalists), they have strong ties towell-known combinatorial optimization problems such as bipartite matching,interval scheduling, graph clique partition (or coloring), and set cover.Therefore, their solutions could also be of interest to the generalalgorithms and combinatorial optimization communities.