Research Of Multiple Sequence Alignment Algorithm Based On Intelligent Optimization And Hidden Markov Model

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.