An Algorithm Design For Haplotype Reconstruction Based On Graph Theory And The The Visual Experiment Platform Development

The analysis and identifiction of haplotype plays a crucial role in locating gene precisely, understanding gene function, and complex disease diagnosis and drug research. Unfortunately, direct determination of individual haplotypes by biological methods is very expensive under the current experimental conditions. Therefore, identification of individual haplotype through computer technology has extremely practical significance. The haplotype assembly problem is a computational problem that induces the corresponding haplotypes by given a set of DNA sequence fragment data of an individual. Most of recent models for haplotype assembly problem have been proven to be NP hard, designation of fast and accurate haplotype reconstruction algorithms to solve haplotype assembly problem becomes an important research direction in bioinformatics.We at first surveyed the existing computational models and algorithms, then analysed the process of reconstruction and proposed a new algorithm for haplotype assembly problem. We transform the SNP matrix into loci linked graph according to the uniformity and difference between SNP loci, by finding the no conflict coloring sequence of loci linked graph to complete the reconstruction process. Experiments shows that this algorithm has excellent performance, and could reconstruct haplotype accurately. Compare to the other two excellent algorithms, our algorithm spend less time in the same circumstance, has hige practical value.The quality of the performance of an algorithm needs detection by experiments. In the command line environment, operations are complex, the readability of experimental results is poor, and the experiments data needs to be treated separately. Therefore the experimental processes are tedious. So far there is no visualization platform to replace operation in command line environment to test the performance of the algorithms of the haplotype assembley. In order to simplify the experimental process, we designed and developed a visualization platform. Based on several mature JavaWeb technologies, the platform could be deployed easily and have good scalability. The experiments can be conducted by the operations through the visual interface with this platform, which is simple. The visualable experiment results are clear and intuitive and can be exported. It provides a great convenience for the algorithm experimental work.