Combinatorial Optimization Problems in the Study of Human Polymorphisms

Scott Camazine

(February 23, 2004 2:30 PM - 3:30 PM)

Combinatorial Optimization Problems in the Study of Human Polymorphisms

Abstract

A polymorphism is a trait which shows variability in a population (e.g., the blood type): without polymorphisms, we would all look the same! The possible values of the trait are called alleles.

At genomic level, a polymorphism is a DNA region (string of A, T, C and Gs) whose content varies in a population. The smallest such polymorphism consists of a single base, and is called Single Nucleotide Polimorphism (SNP, pronounced "snip").

Trying to determine the allele values for a set of SNPs, for either an individual or an entire population, gives rise to several nice and challenging combinatorial problems. These problems, called "haplotyping" problems, have been extensively studied in the last few years. In this talk, we will illustrate the most important haplotyping problems and mention the results that have been obtained for their solution. In particular, some of such problems have been proved NP-hard and solved by (worst case) exponential-time algorithms, while others are solvable in polynomial time.