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

点击翻译按钮获取中文摘要

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.