Premium
The pure parsimony haplotyping problem: overview and computational advances
Author(s) -
Catanzaro Daniele,
Labbé Martine
Publication year - 2009
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00716.x
Subject(s) - haplotype , cardinality (data modeling) , set (abstract data type) , computer science , population , range (aeronautics) , haplotype estimation , computational biology , mathematical optimization , algorithm , mathematics , data mining , genotype , biology , genetics , gene , medicine , materials science , environmental health , composite material , programming language
Haplotyping estimation from aligned single‐nucleotide polymorphism fragments has attracted more and more attention in recent years due to its importance in analysis of many fine‐scale genetic data. Its application fields range from mapping of complex disease genes to inferring population histories, passing through designing drugs, functional genomics, and pharmacogenetics. The literature proposes a number of estimation criteria to select a set of haplotypes among possible alternatives. Usually, such criteria can be expressed under the form of objective functions, and the sets of haplotypes that optimize them are referred to as optimal. One of the most important estimation criteria is the pure parsimony, which states that the optimal set of haplotypes for a given set of genotypes is that having minimal cardinality. Finding the minimal number of haplotypes necessary to explain a given set of genotypes involves solving an optimization problem, called the pure parsimony haplotyping (PPH) estimation problem, which is notoriously ‐hard. This article provides an overview of PPH, and discusses the different approaches to solution that occur in the literature.