Computational experiment for the solution of single nucleotide polymorphisms (SNPS) problems

Single Nucleotide Polymorphisms (SNPs) have recently received significant attention from researchers in different life science disciplines. The discovery of novel SNPs from expressed sequence tags could be an economical method for researchers when handling those species which do not have complete reference sequences. However, distinguishing sequence errors from putative SNPs is a significant problem for in silico methods. Previous researchers have indicated that series of SNPs from the same chromosome, called haplotypes, contain more information than individual SNPs. Thus, reconstructing individual haplotypes from SNP fragments becomes one of the core problems in whole genome sequencing research. Unfortunately, current methods do not have the ability to efficiently handle high error-rate data sets or longer individual haplotypes. Besides the single individual haplotype reconstruction problem, the tag SNP selection problem is the other haplotype-related application that is currently being focused on by researchers. Tag SNP is a kind of biomarker used to tag haplotypes. However, this has been proven to be a NP-hard problem. This study addresses three SNP-related topics—novel SNP discovery, tag SNP selection and single individual haplotype reconstruction—and presents novel computational methods associated with these areas. When mining SNPs from expressed sequence tag data sets, a fuzzy logic system, in conjunction with several statistical measurements, was used to produce highly reliable results. A pipeline framework which merged the advantages of block-based and LD—based models was introduced for selecting highly correlated tag SNPs. A radix tree-like structure and genetic algorithm were implemented in order to reconstruct the single individual haplotype reconstruction problem based on the minimum error correction strategy. Different species’ data types were used in this study, and the experimental results indicate that our methods provide the best solution for each topic at the present time