Book contents
- Frontmatter
- Contents
- Extended contents
- Preface
- Acknowledgments
- Editors and contributors
- A computational micro primer
- PART I Genomes
- 1 Identifying the genetic basis of disease
- 2 Pattern identification in a haplotype block
- 3 Genome reconstruction: a puzzle with a billion pieces
- 4 Dynamic programming: one algorithmic key for many biological locks
- 5 Measuring evidence: who's your daddy?
- PART II Gene Transcription and Regulation
- PART III Evolution
- PART IV Phylogeny
- PART V Regulatory Networks
- REFERENCES
- Glossary
- Index
2 - Pattern identification in a haplotype block
from PART I - Genomes
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Extended contents
- Preface
- Acknowledgments
- Editors and contributors
- A computational micro primer
- PART I Genomes
- 1 Identifying the genetic basis of disease
- 2 Pattern identification in a haplotype block
- 3 Genome reconstruction: a puzzle with a billion pieces
- 4 Dynamic programming: one algorithmic key for many biological locks
- 5 Measuring evidence: who's your daddy?
- PART II Gene Transcription and Regulation
- PART III Evolution
- PART IV Phylogeny
- PART V Regulatory Networks
- REFERENCES
- Glossary
- Index
Summary
A Single Nucleotide Polymorphism (SNP, pronounced snip) is a single nucleotide variation in the genome that recurs in a significant proportion of the population of a species. In recent years, the patterns of Linkage Disequilibrium (LD) observed in the human population reveal a block-like structure. The entire chromosome can be partitioned into high-LD regions, referred to as haplotype blocks, interspersed by low-LD regions, referred to as recombination hotspots. Within a haplotype block, there is little or no recombination and the SNPs are highly correlated. Consequently, a small subset of SNPs, called tag SNPs, is sufficient to distinguish the haplotype patterns of the block. Using tag SNPs for association studies can greatly reduce the genotyping cost since it does not require genotyping all SNPs. We illustrate how to recast the tag SNP selection problem as the set-covering problem and the integer-programming problem – two well-known optimization problems in computer science. Greedy algorithms and LP-relaxation techniques are then employed to tackle such optimization problems. We conclude the chapter by mentioning a few extensions.
Introduction
A DNA sequence is a string of the four nucleotide “letters” A (adenine), C (cytosine), G (guanine), and T (thymine). The genetic variations in DNA sequences have a major impact on genetic diseases and phenotypic differences. Among various genetic variations, the Single Nucleotide Polymorphism (SNP, pronounced snip) is one of the most frequent forms and has fundamental importance for disease association and drug design.
- Type
- Chapter
- Information
- Bioinformatics for Biologists , pp. 23 - 35Publisher: Cambridge University PressPrint publication year: 2011