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

单倍型分析、寡核苷酸指纹图谱和 NMR 峰分配中的算法问题

• 批准号: 0309902
• 负责人: Tao Jiang
• 金额: $ 20万
• 依托单位: University of California-Riverside
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-09-01 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0309902&HistoricalAwards=false
• 关键词: Algorithmic; Problems; Haplotyping; Oligonucleotide; Fingerprinting

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.

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