Sequence Alignment with Piecewise Linear Gap Penalties
Date Issued
2004
Date
2004
Author(s)
Cheng, Kun-Ye
DOI
en-US
Abstract
Genomic DNA sequences, essentially a gigantic string of the four letters A, C, G, and T, can help us understand many of the >4000 genetic diseases that afflict mankind. However, the data will be useless unless the proper methods are developed to interpret the information encoded. Many sequences alignment models are proposed to analyze DNA sequences. We design two algorithms for piecewise linear gap penalties which suit to locate the intermittent similarities. One applies Smith-Waterman approach whose running time is O(MN) that M and N are lengths of two sequences, respectively. The other one uses the property of the diagonalwise monotonicity of the cost tables whose running time is O((M+N)C) that C is the cost of the alignment, M and N are lengths of two sequences respectively.
Subjects
protein
homologous
DNA
gap
suffix automation construction
alignment
difference block
piecewise linear gap penalties
affine gap penalties
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-93-R91922097-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):10ea9d3b85de2430bafa9d24072f4f5b