Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/22707
Title: | Context-Free Codon Alignment |
Authors: | Wu, Bin |
Advisor: | Jiang, Tao |
Department: | Computer Science |
Keywords: | context-free, codon alignment, DNA sequences, protein, quadratic time complexity function, heuristic |
Publication Date: | May-1998 |
Abstract: | <p> We study an alignment model for coding DNA sequences recently proposed by J. Hein in [4] that takes into account both DNA and protein information, and attempts to minimize the total amount of evolution at both DNA and protein levels[4,5,6]. Although there are two quadratic algorithms (i.e. Hua-Jiang algorithm[8] and PLH algorithm[9]) for Hein's model if the gap penalty function is affine, both of them are impractical because of the large constant factor embedded in the quadratic time complexity function. We therefore consider a mild simplification named Context-free Codon Alignment and present a much more efficient algorithm for the simplified model. The algorithms have been implemented and tested on both real and simulated sequences, and it is found that they produce almost identical alignments in most cases. Furthermore, we extend our model and design a heuristic algorithm to handle frame-shift errors and overlapping frames.</p> |
URI: | http://hdl.handle.net/11375/22707 |
Appears in Collections: | Digitized Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Wu_Bin_1998May_Masters..pdf | 2.13 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.