Dissertation > Excellent graduate degree dissertation topics show

Research of Multiple Sequence Alignment Algorithm Based on Intelligent Optimization and Hidden Markov Model

Author: WangZuo
Tutor: LiangYanChun
School: Jilin University
Course: Applied Computer Technology
Keywords: multiple sequence alignment intelligent optimization hidden markov model particle swarm optimization simulated annealing artificial immune system
CLC: TP399
Type: Master's thesis
Year: 2006
Downloads: 256
Quote: 2
Read: Download Dissertation

Abstract


The steady progress of Human Genome Project and various modelsystems sequencing projects in recent years has led to the huge amounts ofbiological sequence data to deal with. Information science has been appliedto biology to produce the field called Bioinformatics. It is an interdisciplinaryscience encompassing mathematics, computer science, and biology to store,retrieve, manage and most importantly, to analyze these massive amounts ofdata. It also helps us to make biological sense out of the vast amounts of data.The acceleration in the accumulation of biological sequences is more andmore great, which makes it challenging to search for sequence similarity bycomparing many related sequences simultaneously. Multiple sequencealignment (MSA) is one of the most important techniques in the sequencecomparison.Algorithms for multiple sequence alignment are commonly used to findconserved regions in biomolecular sequences, to construct family andsuperfamily representations of sequences, and to reveal evolutionary historiesof species. Multiple sequence alignment is NP-hard problem. A very generalform of probabilistic model for sequences of symbols, called a hiddenMarkov model (HMM), has been applied to MSA.In the late 1980s hidden Markov models (HMM) began to be widelyused in many fields of Bioinformatics, such as multiple sequences alignment,gene finding, protein structure prediction, phylogenetic tree construction, etc.The critical and difficult problem for using HMM approach is how to set up asteady and reliable model by a finite training set, moreover, there is noknown deterministic algorithm that can guarantee to find the optimallytrained HMM with reasonable running time. Usually, Baum-Welch algorithmis used to estimate the model parameters (including state transitionprobabilities and symbol emission probabilities). However, it has a tendencyto stagnate on local optima. There do still exist many problems about thetraining algorithm of HMM. In this paper, two effective algorithms areproposed, which are used to train HMM.The research of intelligent optimization algorithms is currently a focusin the advanced field. These algorithms include artificial neural network(ANN), genetic algorithm (GA), simulated annealing (SA), particle swarmoptimization (PSO), artificial immune system (AIS), etc., which aredeveloped by simulating or revealing some phenomenon and process ofnature. They provide innovative thought and means to solve manycomplicated problems. These algorithms have attracted broad interests ofmany researchers in the world for their particular advantage and mechanismand have been applied to many fields successfully. The optimizationalgorithms based on computation intelligence are easy to realize and calculate,which involve only the basic mathematic operations, especially, most ofcomputational intelligence methods possess latent parallel and distributionmechanism, which provide comprehensive technique guarantee to deal with amass of data stored in database. Therefore, the study of intelligenceoptimization algorithms has important theoretical and practical significance.The particle swarm optimization (PSO) is an evolutionary computationtechnique based on swarm intelligence, the PSO has been found to be robustand fast in solving non-linear, non-differentiable and multi-modal problems.Simulated annealing is a generalization of a Monte Carlo method forexamining the equations of state and frozen states of n-body systems. Theconcept is based on the manner in which liquids freeze or metals recrystalizein the process of annealing. In this paper, a hybrid intelligence algorithm(HIA) is proposed, which is based on the parallel search structure of PSO andthe character of SA. The proposed algorithm is used to train the HMM,further, an integration algorithm based on the HMM and HIA for the MSA isconstructed. In HIA, SA uses the initial solution provided by PSO and teststhe sample rule at every annealing temperature, PSO uses the solutionsgenerated by SA for parallel search. SA has a serial structure while PSOadopts parallel search based on swarm, so the proposed algorithm possessesthe advantage of both of the two algorithms. The approach is tested on a setof standard instances taken from the Benchmark alignment database,BAliBASE. Numerical simulated results show that the proposed algorithmnot only improves the alignment abilities, but also reduces the time cost,which provides an effective approach for the MSA.The artificial immune system (AIS) is rapidly emerging inspired bytheoretical immunology and observed immune functions, principles, andmodels. The immune system is a naturally occurring event-response systemwhich can quickly adapt to changing situations. The AIS has appeared tooffer powerful and robust information processing capabilities for solvingcomplex problems. In this paper, a new AIS-based HMM learning algorithmfor MSA is proposed. The proposed algorithm is built on the principles ofclonal selection, affinity maturation and the abilities of learning and memory.The approach is also tested on a set of standard instances taken from theBenchmark alignment database, numerical results show the proposedalgorithm provide an effective approach for multiple sequence alignment.

Related Dissertations

  1. Packet Loss Recovering Technology for Speech Transmission over Network,TN912.3
  2. Research on Domain Entity Attribute and Event Extraction Technology,TP391.1
  3. Research on Feature Extraction and Classification of Tongue Shape and Tooth-Marked Tongue in TCM Tongue Diagnosis,TP391.41
  4. Computing Minimum Distance between Curves/Surfaces Based on PSO Algorithm,O182
  5. Active Power Filter and Its Application in Distribution Network,TN713.8
  6. Research on Fuzzy C-Mean Clustering Algorithm Based on Particle Swarm Optimization and Shuffled Frog Leaping Algorithm,TP18
  7. The Research and Implementation of the Fault Management System for Triple Play,TP315
  8. The Modified Harmony Search Algorithm with Control Parameters Co-evolution and Its Application,TP391.3
  9. Cooperative Optimization Scheduling with Application to Multi-Reservoir System During Non-Flood Period,TV697.11
  10. The Research of Trust Model and Related Technologies in P2P Networks,TP393.08
  11. Research on Multi-time Period Production and Procurement Plan of Supply Chain under Uncertainty,F224
  12. Multi-step-ahead Stock Price Index Forecasting Based on Hybrid Models,F224
  13. PSO-based Multi-robot Formation Control,TP242
  14. Image registration techniques and optimization algorithms research,TP391.41
  15. Support Vector Machine and Its Application in Burst Prediction Model,TD324
  16. The Research on Intelligent Methods of Power Transformer Fault Diagnosis,TM41
  17. Research on End-point Prediction Model of Electric Arc Furnace Based on SVM,TM924.4
  18. Study of Automatic Layout of Transmission Networks Single-line Power Flow Diagram for Dispatching Large Screen Display Based on Simulated Annealing,TM744
  19. Short-term Power Load Forecasting Based on the Particle Swarm Optimization Algorithm,TM715
  20. Parameter Identification and Simulation Research of the Turbo-generator Unit Speed Governor System Dynamic Model,TM311
  21. Study of the Unit Commitment Problem Under Energy-conservation Power Generation Dispatching Based on Multiple Objectives Particle Swarm Optimization,TM73

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > In other aspects of the application
© 2012 www.DissertationTopic.Net  Mobile