Font Size: a A A

A tabu search approach to multiple sequence alignment

Posted on:2009-03-16Degree:Ph.DType:Dissertation
University:North Carolina State UniversityCandidate:Lightner, Carin AnnFull Text:PDF
GTID:1448390002993977Subject:Operations Research
Abstract/Summary:
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 structurefunction 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.
Keywords/Search Tags:Sequence alignment, Tabu search approach, Parsimony scoring function
Related items