Research On Tag SNP Selection Method Based On Bionic Algorithm

A DNA set of polymorphism based on the single nucleotide variations at the genomic level is called Single Nucleotide Polymorphism(SNP).Although genotyping all SNPs can provide disease association studies with accurate genetic information,its cost is too huge.Selecting tag SNP set can save cost while maintaining the information of original sequence.Currently,there are many methods are put forward by researchers for tag SNPs selection.However,they still h ave some drawbacks including low prediction accuracy,high computational complexity,the big number of tag SNP and so on.Thus,we propose two tag SNP selection methods based on biomimetic algorithm to improve performance.The main innovations and research achievements are as follows:A tag SNP selection method called FCGA based on fuzzy clustering and genetic algorithm is proposed by the paper.The method mainly includes three stages: the candidate tag SNPs set formation,tag SNPS selection and non-tag SNPs prediction.In the first stage,FCGA gets the candidate tag SNPs set by fuzzy clustering algorithm based on equivalence relation according to the LD association between SNPs,which not only can reduces the redundancy between sites,but also can reduce s the follow-up problem size during optimization process.Thus,it greatly reduces the time complexity.In the stage of tag SNPS selection,a genetic algorithm with elite reserved strategy is used to optimize the candidate set.The selected tag SNPs has highe r prediction accuracy at non-tag SNPs prediction stage by reasonable design of fitness function.What's more,by using the elite reserved strategy,prediction model which is used to predict non-informative SNPs is only need trained once which saves runnin g time greatly.FCBPSO,another tag SNP selection method based on improved discrete particle swarm algorithm is put forward by us.This method uses the same kind of framework and the first stage and the third stage is similar to the first method.While,in the optimization phase,in order to find the approximate optimal solution more quickly,FCBPSO adopts different velocity updating formula and displacement updating formula in the early and late stage of iterations according to the characteristics of optimization process.What's more,a correction strategy is introduced in the process of optimization,which enables the method to select tag SNPs according to a given number in advance.The two methods proposed in this paper have similar performance on predic tion accuracy,but the second has lower operation time.What's more,this method can select given number of tag SNPs by introducing number correction strategy which make up for the deficiency of the first method.Finally,in order to fairly demonstrate the effectiveness of our two methods,we conduct contrast experiments to make comparison with the current popular selection methods.Experimental results confirm that our two methods both have better performence.