Lajoie Mathieu, El-Mabrouk Nadia
Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, Succursale Centre-ville, Montréal, QC, Canada.
Bioinformatics. 2005 Sep 1;21 Suppl 2:ii173-9. doi: 10.1093/bioinformatics/bti1128.
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.
理解受突变、重组和基因转换影响的单倍型进化，对于理解人类群体的遗传特异性和复杂疾病的遗传基础至关重要。本项目的目标是开发新的算法工具，以辅助重建单倍型之间的历史关系，并从基因型推断单倍型。
我们提出了两种新算法。第一种算法从h个单倍型的群体中找到一条导致给定大小为m的单倍型的最优突变、重组和基因转换路径。其运行时间为O(mhs(2))，其中s是单次基因转换中可交换的连续位点的最大数量。第二种算法找到一条导致给定基因型的最优突变和重组路径，运行时间为O(mh(2))。两种算法均基于惩罚得分模型，并采用动态规划方法。我们将第二种算法应用于从基因型推断单倍型的问题，并展示了它如何用作独立工具或提高现有方法的性能。
这些算法已用Java实现，可根据要求提供。
