Skip navigation
  • Home
  • Browse
    • Communities
      & Collections
    • Browse Items by:
    • Publication Date
    • Author
    • Title
    • Subject
    • Department
  • Sign on to:
    • My MacSphere
    • Receive email
      updates
    • Edit Profile


McMaster University Home Page
  1. MacSphere
  2. Open Access Dissertations and Theses Community
  3. Digitized Open Access Dissertations and Theses
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 SizeFormat 
Wu_Bin_1998May_Masters..pdf
Open Access
2.13 MBAdobe PDFView/Open
Show full item record Statistics


Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.

Sherman Centre for Digital Scholarship     McMaster University Libraries
©2022 McMaster University, 1280 Main Street West, Hamilton, Ontario L8S 4L8 | 905-525-9140 | Contact Us | Terms of Use & Privacy Policy | Feedback

Report Accessibility Issue