ITR: Algorithmic Problems in Population-Scale Genomics

University Of California-Davis, Davis CA

Investigators

Abstract

EIA-0220154 Gusfield, Daniel University of California-Davis ITR: Algorithmic Problems in Population-Scale Genomics Now that genomic level technologies are widely available (for sequencing, resequencing, micro-array screening of sequences etc.), the dream of comparing sequence variations at the population level is starting to become a reality. These comparisons will be used to help to identify the genetic basis of disease susceptibility, and will have additional uses. This shift to opulation-scale genomics introduces a new set of computational problems, and provides a huge opportunity for high-impact algorithm development and research. This project focuses on novel, critical computational problems that arise in population-scale genomic data acquisition and analysis. The specific computational problems to be addressed arise out of on-going population-scale investigations into population-level genomic variability. It will focus on novel computational problems that have not been previously formulated and addressed, and problems where additional formulations are needed to better capture the relevant biology. Although the algorithmic techniques will be grounded in theoretical computer science and discrete mathematics (and the results will be of interest in those fields), the standards for success will be the ultimate applicability of the results in genomics. The research will be conducted at several levels: modeling and defining important problems; finding and developing efficient algorithms; implementing and distributing software for the most important results; and applying the software on population-scale genomic data. Our first focus is on problems related to computationally extracting haplotype information from genotype information, and the construction and use of haplotype maps. The larger significance of the project will be the development of powerful computational tools for use by geneticists and gene mappers, which will help to more effectively identify the genetic bases for disease susceptibility and other important genetic traits.