Abstract
The purpose of this chapter is to present a set of algorithms and their efficiency for the consistency based Multiple Sequence Alignment (MSA) problem. Based on the strength and adaptability of the Genetic Algorithm (GA) two approaches are developed depending on the MSA type. The first approach, for the non related sequences (no consistency), involves a Hybrid Genetic Algorithm (GA_TS) considering also Tabu Search (TS). The Traveling Salesman Problem (TSP) is also applied determining MSA orders. The second approach, for sequences with consistency, deals with a hybrid GA based on the Divide and Conquer principle (DCP) and it can save space. A consistent dot matrices (CDM) algorithm discovers consistency and creates MSA. The proposed GA (GA_TS_VS) also uses TS but it works with partitions. In conclusion, GAs are stochastic approaches that are proved very beneficial for MSA in terms of their performance.
TopIntroduction
Sequence Alignment is the procedure of comparing two (pair-wise alignment) or more (multiple sequence alignment) DNA or protein sequences by searching for a series of individual characters or character patterns that are in the same order in the sequences. Sequence alignment is useful for discovering functional, structural and evolutionary information in DNA or protein sequences. It is important to obtain the best possible, so-called “optimal”, alignment to discover this information (Mount 2004). Sequences that are very much similar in the parlance of sequence analysis probably have the same function. Additionally, if two sequences from different organisms are similar, there may have been a common ancestor sequence, and the sequences are then defined as homologous. An alignment indicates the changes that could have occurred between the two homologous sequences and a common ancestor sequence during the evolution as shown in Figure 1.
Figure 1. The evolutionary relationship between two similar sequences
In Figure 1 there is an origin of similar sequences. Sequences 1 and 2 are each assumed to be derived from a common ancestor sequence. Some of the ancestor sequences can be inferred from conserved positions in the two sequences. For positions that vary there are two possible choices at these sites in the ancestor. In the phylogenetic analysis of three or more similar sequences, the separate distances from the ancestor can be estimated (Mount, 2004).
There are two principal methods of pair-wise alignment: the Dot Matrix analysis and the Dynamic Programming (DP) algorithm. Dot Matrix should be considered as a pair-wise (two sequences) alignment method that displays any possible sequence alignment in diagonal. The DP develops a process that generates a matrix of numbers that represents all possible alignments between two sequences (Jones, Pevzner, 2004). The highest set of sequential scores in the matrix defines an optimal alignment. For proteins, an amino acid substitution matrix, such as the Dayhoff percent accepted mutation matrix 250 (PAM250) is used for score matches and mismatches (Mount, 2004)
Multiple Sequence Alignment (MSA) is among the most important tasks in computational biology.
MSA is a very important extension of paiwise sequence alignment where there is a mutual alignment of three or more sequences. Usually we can find large families of similar sequences by identifying homologues in many different species (Lesk, 2012). In biological sequence comparison, emphasis is given to the simultaneous alignment of several sequences. Genetic Algorithms (GAs) are stochastic approaches for efficient and robust search that can play a significant role for MSA. GA is an evolutionary technique for large space search. It is based on principles inspired by the genetic and evolution mechanisms observed in natural systems (Goldberg,1989; Davis,1991). The near global optimal solution for objective function for Fuzzy Non-Linear Industrial Production Planning Problems is obtained by hybrid meta-heuristics optimization algorithms such as line search, genetic algorithms, and simulated annealing (Vasant, 2012).
Key Terms in this Chapter
Motif: A conserved pattern of amino acids that is found in two or more proteins.
Homology: A statement of common evolutionary origin.
Homologous Genes: Genes whose sequences are so similar that they almost certainly arose from a common ancestor gene.
Dot Matrix: Diagrams that provide a graphical method for comparing two sequences. Dots are placed within the graph if the same letter appears at the corresponding positions in the sequences. A diagonal series of dots appearing as lines on the graph indicates an alignment of a series of positions in the sequences.
Phylogenetic Analysis: An investigation of the evolutionary relationships among a group of related sequences by producing a tree representation of the relationships.
Sequence Alignment: The comparison of two or more sequences by searching for a series of individual characters or character patterns that are in the same order in the sequences.
Dynamic Programming: Programming that solves the problem of finding the optimal alignment between two sequences by building a table.
Progressive Alignment: A procedure for generating an MSA that reduces the construction of the MSA to a series of pair-wise alignments.
Consensus: The calculated order of most frequent residues, either nucleotide or amino ascid, found at each position in a sequence alignment.
Genome: The entire set of DNA sequence information for an organism that is passed along from one generation to the next. It includes coding sequences for macromoleculus and noncoding sequences.
Sequence Similarity: A measurement of the matching characters in the alignment.
DNA: A double-stranded, helical molecule made up of sequences of four nucleotides (A, G, C, T) in each strand and backbones of sugars and phosphates.
Sum of Pairs: In the MSA of a set of sequences is the sum of the alignment scores for each pair of sequences in the MSA.
Diversification: To allow the process to search other parts of the solution space, driving it into new regions.
Multiple Sequence Alignment (MSA): An alignment of three or more sequences such that each column of the alignment is an attempt to represent the evolutionary changes in one sequence position, including substitutions, insertions, and deletions.