The haplotype assembly problem aims at finding originate haplotypes of some fragments that obtained from sequencing methods. In diploid case in which organisms have pair chromosomes, like humans, the aim is to reconstruct two haplotypes such that each of reads is originated from one of the two reconstructed haplotypes. In diploid case, the problem is well studied and since it is NP-hard due to unavoidable errors of sequencing machines, exact approaches are of exponential order. So, many fast, but approximate approaches have been proposed. In triploid case, the aim is finding three haplotypes such that each read originates from one of the three haplotypes. The triploid case is much harder than the diploid case and faces with more computational difficulties. For this reason, a few researchers studied the triploid case of haplotype assembly problem. In this paper, two binary linear programming models are proposed for two cases of availability and non-availability of genotype data for triploid haplotype assembly and the computational efficiency of the models is tested on simulated datasets using AIMMS. The proposed models could be generalized to higher ploidy.

Keywords: Haplotype Assembly, Binary Linear Programming, Triploid, Exact Methods.

Full-Text [PDF 839 kb]   (564 Downloads)