Using Parallel Fusion Clustering Method to Solve Haplotype Assembly

It is generally accepted that all human share about 99% of identity at the DNA level and only some regions of differences in DNA sequences are responsible for genetic diseases [7,8]. The availability of complete genome sequence for human beings '6] makes it possible to investigate genetic differences and to associate genetic variations with complex diseases [4]. Single Nucleotide Polymorphisms (SNPs), single DNA bases varying from one individual to another, are believed to be the most frequent form responsible for genetic differences [5] and are found approximately every 1000 base pairs in the human genome and turn to be promising tools for doing disease association study. The nucleotide in a SNP site is called an allele. Most SNPs have two different alleles, known here as 'A' and 'B'. The SNP sequence information on each copy of a pair of chromosomes in a diploid genome is a haplotype which is a string over {'A','B'}. Although haplotypes have more information for disease associating than individual SNPs and genotype information, it is substantially more difficult to determine haplotypes. Hence, computational methods are employed to reduce the cost of determining haplotypes. Individual haplotyping or haplotype assembly (discussed in this paper) is based on SNP fragments as input data to infer the best pair of haplotypes with the minimum extent of contradiction. In other words, methods are partitioning the SNP fragments into two classes, where each class corresponds to one haplotype. MEC, LHR, MEC/GI and some other models have been discussed for haplotype reconstruction [9], [10], [3]. Minimum Error Correction (MEC) as a standard model for haplotype reconstruction based on SNP fragments is decided to be the center of our research. This model is solved by different heuristic algorithms and classification models (like [2,4]).