title: Recovering haplotype structure through recombination and gene conversion.
abstract: BACKGROUND
  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.
  
  
  RESULTS
  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.
  
  
  BACKGROUND
  The algorithms have been implemented in JAVA and are available on request.
authors.affiliation: Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, Succursale Centre-ville, Montréal, QC, Canada.
authors.forename: Mathieu
authors.initials: M
authors.lastname: Lajoie
authors.forename: Nadia
authors.initials: N
authors.lastname: El-Mabrouk
mesh_terms: D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods; D004252:DNA Mutational Analysis / Q000379:methods*; D019143:Evolution, Molecular; D005785:Gene Conversion / Q000235:genetics*; D014644:Genetic Variation / Q000235:genetics; D006239:Haplotypes / Q000235:genetics*; D008957:Models, Genetic; D010802:Phylogeny; D011995:Recombination, Genetic / Q000235:genetics; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software