Dissertation > Excellent graduate degree dissertation topics show

Research on Parallel GA for DNA Sequencing by Hybridization

Author: YuanZuoZuo
Tutor: XieHongZuo
School: Taiyuan University of Technology
Course: Applied Computer Technology
Keywords: Parallel computing Genetic Algorithms Fleet DNA sequencing by hybridization
CLC: TP18
Type: Master's thesis
Year: 2010
Downloads: 66
Quote: 0
Read: Download Dissertation

Abstract


By gene sequence to unlock the mystery of all life is the research goals of bioinformatics, DNA sequencing is the basis of the understanding of gene structure and function, and is the starting point for bioinformatics research. The start of the Human Genome Project to promote the rapid development of bioinformatics. July 2, 2008, the U.S. Department of Energy Joint Genome Institute claims that its mass sequencing project in 2009 to support DNA sequencing projects. Above show that the rapid sequencing of the genome sequence has been an urgent need. Sequencing by hybridization is currently one of the most widely used sequencing methods, it is divided into the hybridization experiments and sequence reconstructed in two steps. Hybridization experiments tend to be two types of error due to technical limitations and conditions, the resulting set of non-ideal spectrum gave the sequence reconstructed brought great difficulties. Has proven to contain error sequence refactoring problem is NP-hard problem. Many domestic and foreign research literature on the issue of hybrid. The exact algorithm solving sequencing by hybridization (branch and bound algorithm, dynamic programming, etc.) and heuristic search methods (tabu search algorithm, genetic algorithm, ant colony algorithm, simulated annealing algorithm) categories. By comparison, the exact algorithm is only applicable in the small sequence length, and heuristic search method does not depend on the problem space more applications. The genetic algorithm is based on Darwin's theory of biological evolution theory of natural selection and population genetics principle and developed a stochastic global search and optimization adaptive intelligent algorithm. The genetic algorithm is not the restrictive assumptions constraint of the search space. Verified better than other algorithms on problem solving contain erroneous DNA sequencing. Due to the inherent parallelism of the genetic algorithm is very suitable for massively parallel computing, parallel genetic algorithm can often improve processing speed, improve solving performance. Based on the above, the intent of this paper is to improve the existing parallel genetic algorithm applied to DNA sequencing by hybridization problem, the more accurate reconstruction of the DNA sequence, it takes less time. Firstly, modeling of the problem, the use of the existing model of genetic algorithm to solve the problem, determine the evolutionary strategy; then improved parallel genetic algorithm optimization solution model; finally build a fleet environment, and the results are analyzed and discussed. The core of this article lies in the choice of parallel genetic algorithm framework and migration of operating improvements. This paper analyzes the four parallel model of communication, combined with the problem of DNA sequencing by hybridization, choose to use coarse-grained - master-slave double parallel framework; migration operation parallel framework, proposes a new migration strategy. Verified by experiment, the new migration strategy to effectively reduce the communication overhead. The analysis of this article provides a frame of reference for the use of parallel genetic algorithm to calculate the complex biological engineering of parallel the Genetic Algorithm promotion and more effective application of practical value.

Related Dissertations

  1. Development of the on-line Training and Examination System of Army,TP311.52
  2. Designs and Applications of Fuzzy Synthetic Evaluation Models Based on Parallel Algorithms,TP18
  3. Based on Genetic Algorithm Pishihang irrigation canal water allocation marshalling model of,S274
  4. Genetic Algorithm in logistics and warehousing Optimization Research,F259.2
  5. Mining resources based on genetic algorithm optimization model of,O224
  6. The Research and Application of Modified Algorithms About Fuzzy Predictive Functional Control,TP273
  7. The Study on the Container Fleet Size of of Container Lines,F551
  8. Optimal Control of Emulsion System in Cold Rolling,TP273
  9. Research on the Marshalling-scheduling Model and Algorithms of Freight Trains Based on Game Theory,O225
  10. Multi-directional Mutation Genetic Algorithm and Research on Neural Network Optimization,TP18
  11. The Application of Using Genetic Algorithms on Universities Course-arranging System,TP18
  12. Research on Mobile Robot Path Planning and Simulation Realization,TP242
  13. Research and Design of a High-Performance Scalable Public Key Cryptographic Coprocessor,TN918.1
  14. Research on Video Compression Algorithm Based on Multi-core Computing Platform,TN919.81
  15. Research on Routing Algorithmin Sensor Networks Based on Cluster with Mobile Sink,TP212.9
  16. Research and Implement of the Theme Crawler for Automotive Industry,TP391.3
  17. The Research and Implement on Camera Calibration Technology Based on Trifocal Tensor,TP391.41
  18. Decision Support System of Vehicle Scheduling in Double Level Garage,TP242
  19. The Studies on Some Improvements of the GA and Their Applications in SVM,TP18
  20. A Reduction Method for Artificial Neural Network Inputs Based on An Improved Genetic Algorithm,TP18
  21. Research of Finite Element Method on GPU,O241.82

CLC: > Industrial Technology > Automation technology,computer technology > Automated basic theory > Artificial intelligence theory
© 2012 www.DissertationTopic.Net  Mobile