Haplotype Inference from Genotype Data Using Evolutionary Method (ARO)

Single Nucleotide Polymorphism (SNP) is one of the most common structural changes in the genomic sequences. Haplotypes are sets of SNPs in each chromosome. Haplotypes in some organisms such as human are in diploid form i.e. there are two copies for each chromosome which one inherited from father and the other inherited from mother [1, 2]. Chraterizing the haplotypes provide valuable information for researchers which can help in several dominas such as drug desgins and genetic desiases [3-5].Since obtaining haplotypes from experimental methods are expensive, several computational methods have been proposed which reconstruct haplotypes based on genotype data [6-8]. It should be noted that the approaches which uses genotype data are categorized as haplotype inference. The aim of these methods is to search the smallest number of distinct haplotypes that can generate the given genotypes [9] and it is proved to be NP-hard [10, 11]. In this paper, we propose a new algorithm based on the Asexual Reproduction Algorithm (ARO) [12]. High convergence speed and less parameter setting against similar algorithms such as GA, are the main advantages of ARO. For this purpose, several new ideas are presented to improve the efficiency of the ARO in the haplotypes inference problemsuch as changing the structure of individual, improving the ProLarva operator and etc.In order to evaluatethe method four real data sets has been used. The obtained results demonstrate that the proposed method often outperforms compairing methods both on switch error rate and genotype error rate

Keywords:

Haplotype , Genotype , Haplotype inference , NP-hard , ARO