Display Settings:


Send to:

Choose Destination
Bioinformatics. 2005 Sep 1;21 Suppl 2:ii173-9.

Recovering haplotype structure through recombination and gene conversion.

Author information

  • 1Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, Succursale Centre-ville, Montréal, QC, Canada.



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.

[PubMed - indexed for MEDLINE]
Free full text
PubMed Commons home

PubMed Commons

How to join PubMed Commons

    Supplemental Content

    Icon for HighWire
    Loading ...
    Write to the Help Desk