Abstract: Determining triploid individual haplotype plays an important role in promoting the study of exploring genetic traits and phenotypic differences of triploid species.In this paper,based on the minimum error correction with genotype information (MEC/GI) model,an enumeration strategy based enumeration haplotyping triploid (EHTR) algorithm was proposed for solving triploid individual haplotype reconstruction problem.The EHTR algorithm reconstructs the SNP sites of the three haplotypes one after another.When reconstructing a given SNP site,it enumerates three kinds of SNP values in terms of the genotype of the site,and chooses one with the most high support degree coming from the SNP fragments that are covering the corresponding SNP site.The total time complexity is O(mn+mlogm+cnl).In the experiments,two kinds of simulators CELSIM and MetaSim were invoked to generate SNP fragments.The reconstruction rate and running time were compared and analyzed among algorithms EHTR,GTIHR,W-GA and Q-PSO with different parameters setting,such as fragment coverage,error rate,single fragment length,haplotype length and haplotype hamming distance.Under different parameter setting,the EHTR algorithm can obtain higher reconstruction rate in shorter running time,which is proved by a number of experiments.

Key words: Sequence analysis,Triploid,Haplotype,Genotype,Minimum error correction,Enumeration