Haplotype Assembly Problem Models in Diploid and Polyploid Cases

The haplotype assembly problem aims at finding the haplotypes from a number of sequenced fragments. This problem can be considered in two diploid and polyploid cases. Diploid case aims at finding two haplotypes but in polyploid case the number of haplotypes is grater than two. For example, humans are diploid i.e., they have two copies of their chromosomes, one inherited from the mother and the other inherited from the father. Many plants are polyploid i.e., their somatic cells contain more than two copies of each chromosome. For instance, cultivars of potato, coffee, cotton and peanut are polyploid. The polyploid case is more complicated and challenging diploid case. In this paper, a zero-one integer linear programming (ILP) model is proposed that can be used for solving haplotype assembly problem in both diploid and polyploid cases. It is compared with the previous model for diploid case using simulated dataset. Experiments show that the new model can be solved within much shorter time by CPLEX

کلیدواژه ها:

Diploid ، Polyploid ، Haplotype assembly ، Integer linear programming