tailieunhanh - Solving haplotype assembly problem using harmony search

In this paper, Harmony Search (HS) is considered a clustering approach. Extensive computational experiments indicate that the designed HS algorithm achieves a higher accuracy than the genetic algorithm (GA) or particle swarm optimization (PSO) to the MEC model in most cases. | International Journal of Computer Networks and Communications Security C VOL. 1, NO. 4, SEPTEMBER 2013, 110–118 Available online at: ISSN 2308-9830 N C S Solving Haplotype Assembly Problem Using Harmony Search Saman Poursiah Navi1, Ehsan Asgarian2 1 Department of Computer Engineering, Islamic Azad University, Quchan Branch, Quchan, Iran 2 Department of Computer Engineering, Sharif University of Technology, Tehran, Iran E-mail: 1samanpoursiah@ ABSTRACT Single Nucleotide Polymorphisms (SNPs), a single DNA base varying from one individual to another, are believed to be the most frequent form responsible for genetic differences. Haplotypes have more information for disease-associating than individual SNPs or genotypes; it is substantially more difficult to determine haplotypes through experiments. Hence, computational methods that can reduce the cost of determining haplotypes become attractive alternatives. MEC, as a standard model for haplotype reconstruction, is fed by fragments input to infer the best pair of haplotypes with minimum errors needing correction. It is proved that haplotype reconstruction in the MEC model is a NP-Hard problem. Thus, researchers’ desire reduced running time and obtaining acceptable results. Heuristic algorithms and different clustering methods are employed to achieve these goals. In this paper, Harmony Search (HS) is considered a clustering approach. Extensive computational experiments indicate that the designed HS algorithm achieves a higher accuracy than the genetic algorithm (GA) or particle swarm optimization (PSO) to the MEC model in most cases. Keywords: Clustering, Bioinformatics, Evolutionary Optimization, Reconstruction Rate. 1 INTRODUCTION Availability of the complete genome sequence for human beings makes it possible to investigate genetic differences and associate genetic variations with complex diseases [1]. It is generally accepted that all human beings share about 99% identity at the DNA