Haplotype inference by pure-parsimony using revamped delayed haplotype selection. (c2011)

Abstract

In recent years, there has been a worldwide initiative to gather as much information as possible about the human genome, resulting in the Human Genome Project (HGP). The HGP project was founded on the basis of gathering genetic information to be used in various bioinformatics areas. The Human Genome Project’s main purpose is to find the common ancestry among various peoples around the globe in order to identify origins and gene-related diseases. Haplotype Inference(HI) is one of the problems tackled in the HGP, whereby from a given population of genotypes the goal is to find the minimum number of haplotypes from which the genotypes could have derived. Clark’s Algorithm is the first known algorithm to deal with this problem from a Computer Scientist’s perspective. It has been the basis for many other algorithms afterwards. One such algorithm is the Delayed Haplotype Selection(DS). Our work is an improvement of the DS. We call the resulting algorithm Revamped Haplotype Selection(RDS) algorithm. We test our algorithm on real and simulated data, and compare it to the DS algorithm and a Branch-and-Bound approach (known as HAPAR). Results prove that our algorithm significantly outperforms both in the quality of the solution as well as in running time.