Biomedical Engineering Reference
In-Depth Information
Chapter 7
Haplotype Inference Using Propositional
Satisfiability
Ana Gra¸a, Joao Marques-Silva, and Ines Lynce
Abstract
Haplotype inference is an important problem in computational biology,
which has deserved large effort and attention in the recent years. Haplotypes encode
the genetic data of an individual at a single chromosome. However, humans are
diploid (chromosomes have maternal and paternal origin), and it is technologi-
cally infeasible to separate the information from homologous chromosomes. Hence,
mathematical methods are required to solve the haplotype inference problem. A rel-
evant approach is the pure parsimony. The haplotype inference by pure parsimony
(HIPP) aims at finding the minimum number of haplotypes which explains a given
set of genotypes. This problem is NP-hard.
Boolean satisfiability (SAT) has successful applications in several fields. The use
of SAT-based techniques with pure parsimony haplotyping has shown to produce
very efficient results. This chapter describes the haplotype inference problem and
the SAT-based models developed to solve the problem. Experimental results con-
firm that the SAT-based methods represent the state of the art in the field of HIPP.
7.1
Introduction
Recent advances in sequencing technologies have enabled sequencing the genome
of thousands of people efficiently and inexpensively. Such information has of-
fered investigators new opportunities to understand the genetic differences between
human beings, and later mapping such differences with common human diseases.
The International HapMap Project
1
and the 1000 Genomes Project
2
represent
significant efforts to catalog the genetic variations among human beings.
Search WWH ::
Custom Search