The Algorithms Of Sequence Alignment In Bioinformatics

Sequence alignment is a basic information processing method in bioinformatics and useful for discovering functional, structural, and evolutionary information in biological sequences. The main idea is to find a maximum base matching among biological sequences. The result of sequence comparison show the similarity/dissimilarity between sequences and the biological characteristic of the sequences. It is very important to look for a simple and effective algorithms of sequences alignment for biologist. Sequence alignment is also the first step for many problems in computational biology, including fragmentassembly, evolutionary tree reconstruction and genome analysis. There are many methods for the analysis of similarity of DNA sequences,but most of them are based on the the dynamic programming algorithm. The sequence alignment algorithm can be divided into pair-wise sequence alignment algorithms and multiple sequence alignment algorithm.In chapter 2, we introduce the traditional algorithms of sequence alignment based on the dynamic programming algorithm. We will find that all algorithms shared one characteristic: The traditional method is based on comparison of string. The similarity show these string have common substring. LCS is the problem for finding a maximum common subsequence (Longest Common Subsequence) in biological sequence. Recently, many authors have provided graphical representations of biological sequences. Base on this idea, we provide a new method to solve the LCS between biological sequecne and biological structure based on the graphical representation. The algorithm demonstrates the effectiveness for sequence visualization and comparison. And we also consider the algorithm to search the local alignment and global alignment between mRNA sequences and protein sequences in chapter 3.