Article Preview
Top1. Introduction
The main goal of Bioinformatics is to understand a living cell better and its functionality at the molecular level. This can be fulfilled by the analysis of the raw molecular sequences and structural data. In sequence analysis, different concepts such as sequence alignment, motif and pattern discovery are covered. In core, sequence alignment is a fundamental problem in computational genomics. The sequence represents one or more genomes where all its length should not be compulsorily equal. Here, the sequence is nothing but the combinations of letters of the alphabet. Different types of sequences like DNA, RNA and proteins are formed by the “central dogma” of biology in which DNA is transcribed to RNA and that is translated into proteins (Xiong, J. 2006).
Sequence alignment is a concept, in which similarity or difference between the sequences is found. When two sequences are compared to align according to their similarity, it is known as pair-wise alignment. As the extension of pair-wise alignment, MSA was introduced. In this alignment, three or more sequences are aligned. Figure 1 represents the two different forms of sequence alignment. The MSA can be defined as the process that arrange n sequences where n>2 in such a way that a maximum number of residues from each sequence is matched.
The MSA reveals more biological information than any pair-wise alignments can do. Multiple Protein sequence alignment identifies many conserved and functional critical amino acid residues. The three major tasks in the MSA are scoring, creating an alignment and assessing its significance. The traditional alignment methods can be characterized into two forms, namely exhaustive and heuristic algorithm. Exhaustive methods need extract dimensions to take all possible ways of sequence matching like dynamic programming sequence matching in pair-wise alignment. The drawback of this method is computationally intensive and handles only dataset with the small number of sequences. To overcome this problem, many heuristic algorithms have been developed. This can be classified into Progressive Alignment (PA), Iterative Alignment (IA) and Block-based Alignment (BA) types.BA method (Mohsen et al., 2011) is used to find the conserved domains and motifs. It is not done through PA and IA methods.
The PA algorithms initially start aligning most similar pairs of sequence and then continue with less similar ones. Even though PA is fast, it is not suitable for aligning sequences of different lengths. Some of the progressive type algorithms are T-Coffee (Notre dame C et al., 2000), DBClustal (Thompson J D et al., 2000), PRALINE (Simossis V A et al., 2005), where PRALINE is more sophisticated and accurate alignment program, but extremely slow in terms of time. This problem is overcome by the iterative alignment. The main idea of this is to repeatedly modify suboptimal solutions to find the optimal solution. In general, more information is gathered from global alignment than the particular divergent residues. An important advantage of Evolutionary Algorithm (EA) based approach over progressive methods is that, different fitness function can be tested without modifying the alignment procedure. There are many works proposed using EA like (Notre dame C et al., 2000; Rasmussen TK et al., 2003; Lee Z J et al., 2008; Kaya M et al., 2014). In essence, EA based methods reduced the computational time for NP-complete problems. In this proposed work, one of the evolutionary algorithms, PSO along with CA rules is used. All the algorithms for MSA are evaluated according to a particular scoring function which is the objective function for finding one of the best solutions. The scoring function, Sum of Pairs (SP) and Total Column Score (TC) are considered in most of the algorithms.