Recovering haplotype structure through recombination and gene conversion.

Abstract

Understanding haplotype evolution subject to mutation, recombination and gene conversion is fundamental to understand genetic specificities of human populations and hereditary bases of complex disorders. The goal of this project is to develop new algorithmic tools assisting the reconstruction of historical relationships between haplotypes and the inference of haplotypes from genotypes. We present two new algorithms. The first one finds an optimal pathway of mutations, recombinations and gene conversions leading to a given haplotype of size m from a population of h haplotypes. It runs in time O(mhs(2)), where s is the maximum number of contiguous sites that can be exchanged in a single gene conversion. The second one finds an optimal pathway of mutations and recombinations leading to a given genotype, and runs in time O(mh(2)). Both algorithms are based on a penalty score model and use a dynamic programming approach. We apply the second one to the problem of inferring haplotypes from genotypes, and show how it can be used as an independent tool, or to improve the performance of existing methods. The algorithms have been implemented in JAVA and are available on request.