摘要
The investigation of genetic differences among humans has given evidence thatmutations in DNA sequences are responsible for some genetic diseases. The most common mutation isthe one that involves only a single nucleotide of the DNA sequence, which is called a singlenucleotide polymorphism (SNP). As a consequence, computing a complete map of all SNPs occurring inthe human populations is one of the primary goals of recent studies in human genomics. Theconstruction of such a map requires to determine the DNA sequences that from all chromosomes. Indiploid organisms like humans, each chromosome consists of two sequences called haplotypes.Distinguishing the information contained in both haplotypes when analyzing chromosome sequencesposes several new computational issues which collectively form a new emerging topic of ComputationalBiology known as Haplotyping. This paper is a comprehensive study of some new combinatorialapproaches proposed in this research area and it mainly focuses on the formulations and algorithmicsolutions of some basic biological problems. Three statistical approaches are briefly discussed atthe end of the paper.
The investigation of genetic differences among humans has given evidence thatmutations in DNA sequences are responsible for some genetic diseases. The most common mutation isthe one that involves only a single nucleotide of the DNA sequence, which is called a singlenucleotide polymorphism (SNP). As a consequence, computing a complete map of all SNPs occurring inthe human populations is one of the primary goals of recent studies in human genomics. Theconstruction of such a map requires to determine the DNA sequences that from all chromosomes. Indiploid organisms like humans, each chromosome consists of two sequences called haplotypes.Distinguishing the information contained in both haplotypes when analyzing chromosome sequencesposes several new computational issues which collectively form a new emerging topic of ComputationalBiology known as Haplotyping. This paper is a comprehensive study of some new combinatorialapproaches proposed in this research area and it mainly focuses on the formulations and algorithmicsolutions of some basic biological problems. Three statistical approaches are briefly discussed atthe end of the paper.
基金
美国自然科学基金