Speaker: Bogdan Pasaniuc
Day:  Wednesday, 4/5/2006
Room: ITEB 336
Time: 3:30pm

Title: Approximation algorithms for selection of Robust Tag SNPs
 
A Single Nucleotide Polymorphism (SNP) is a position in the genome at which exactly two of the possible four nucleotides occur in a large percentage of the population. In recent years, SNPs have become more and more popular for association studies of genetic diseases or traits. Although the cost of sequencing SNPs is gradually reducing, it is still uneconomical to sequence all SNPs. However, because of the low haplotype diversity within a block, a small subset of SNPs (called "tag SNPs") is sufficient to capture the haplotype pattern of the block. We are going to present the problem of finding the Minimum Size Set of Tag SNPs along with a variant of it, the Minimum Robust Tag SNPs, variant that allows sequencing errors. The relation to the Set Covering problem, respectively Set Multicover problem will be presented. We are going to show that the greedy algorithm for the Minimum Robust Tag SNPs problem achieves an approximation factor of 2*ln (k), where k is the number of haplotypes. 
 
References: 
 
Y. Huang, K. Zhang, T. Chen, and K. Chao, "Approximation Algorithms for the
Selection of Robust Tag SNPs" Lecture Notes in Computer Science / Lecture Notes in Bioinformatics, pp.  278-289, Bergen, Norway.
 
Vijay V. Vazirani, "Approximation Algorithms"
Springer-Verlag, Berlin, 2001.