An overview of the haplotype problems and algorithms

Abstract

A single nucleotide polymorphism (SNP), as the most common form of genetic variation, has been widely studied to help analyze the possible association between diseases and genomes. To gain more information, SNPs on a single chromosome are usually studied together, which constitute a haplotype. Gaining haplotypes from biological experiments is usually very costly and time-consuming, which causes people to develop efficient methods to determine haplotypes from the computational angle. Many problems and algorithms about haplotypes have been proposed to reduce the cost of studies of disease association. In general, four categories of problems are widely researched: the haplotype assembly problem, the haplotype inference problem, the haplotype block partition problem, and the haplotype tagging SNP selection problem. The former two problems have been well reviewed by many researchers, whereas the latter two have not been comprehensively surveyed to our knowledge. In this paper, we try to make a detailed introduction to the four problems, especially the latter two.

Keywords

ioinformatics, haplotype, single nucleotide polymorphism (SNP), algorithm, complexity