Some Algorithmic Problems Arising in Systems Biology and Statistical Genetics
Event details
| Date | 13.07.2009 |
| Hour | 14:15 |
| Speaker | Prof. Richard M. Karp, University of California at Berkeley |
| Location | |
| Category | Conferences - Seminars |
The quest to understand how living cells work and how genetic variation is related to disease requires the extraction of knowledge from large bodies of genomic and molecular data. This effort leads to large-scale combinatorial optimization problems. We present approaches to three such problems: (1) Alignment of multiple genomes. One is given several closely related genomes in which pairs of highly similar segments called "anchors" are designated. The problem is to align the genomes so that, to the greatest extent possible, matching anchors are aligned against each other. We formulate this problem as an implicit hitting set problem, and develop and apply a generic approach to such problems. Joint work with Erick Moreno Centeno. (2) Given a set of "query proteins" and a network in which the vertices represent proteins and the edges represent physical interactions between proteins,find the most compact connected subnetwork containing at least one protein matching each query protein.Such subnetworks are likely to be functional units in the regulation of cellular processes.We present solution methods based on dynamic programming, integer programming and simple but effective heuristics. Joint work with colleagues at Tel-Aviv University. (3) Finding associations between SNPs and disease. A SNP (single-nucleotide polymorphism) is a site within a genome where two different nucleotides commonly occur. We discuss the construction of efficient sequential experimental designs to identify the SNPs most highly associated with a given disease.
Prof. Karp's webpage
Practical information
- General public
- Free