Sequence alignment methods are used to detect and quantify similarities between different DNA and protein sequences that may have evolved from a common ancestor. Effective sequence alignment methodologies also provide insight into the structure\function of a sequence and are the first step in constructing evolutionary trees. In this dissertation, we use a tabu search approach to multiple sequence alignment. A tabu search is a heuristic approach that uses adaptive memory features to align multiple sequences. The adaptive memory feature, a tabu list, helps the search process avoid local optimal solutions and explores the solution space in an efficient manner. We develop two main tabu searches that progressively align sequences. A randomly generated bifurcating tree guides the alignment. The objective is to optimize the alignment score using either the sum of pairs or parsimony scoring function. The use of a parsimony scoring function provides insight into the homology between sequences in the alignment. We also explore iterative refinement techniques such as a hidden Markov model and an intensification heuristic to further improve the alignment. Moreover, a new approach to multiple sequence alignment is developed that provides improved alignments as compared to other methods.Table 6.10 and 6.11 display the minimum, maximum, average and standard deviation of the CPU times for Tabu B, Tabu ... Tabu Aa#39; and Tabu C were coded in Matlab. The source code for SAGA was downloaded from http://www.tcoffee.org/ Projects_home_page/ saga_home_page.html_saga. ... This plot shows that SAGA and Tabu C have the shortest and longest processing times of the four algorithms, anbsp;...
|Title||:||A Tabu Search Approach to Multiple Sequence Alignment|
|Publisher||:||ProQuest - 2008|