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 computed 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. This approach to multiple sequence alignment provides improved alignments as compared to several other methods.
| Identifer | oai:union.ndltd.org:NCSU/oai:NCSU:etd-05312008-191232 |
| Date | 05 August 2008 |
| Creators | Lightner, Carin Ann |
| Contributors | Dr. Simon M. Hsiang, Dr. Elmor Peterson, Dr. Henry L. W. Nuttle, Dr. Shu-Cherng Fang |
| Publisher | NCSU |
| Source Sets | North Carolina State University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://www.lib.ncsu.edu/theses/available/etd-05312008-191232/ |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dis sertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to NC State University or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.0185 seconds