Gap Alignment Discuss

0.定義:
2 個字串在某部份分開後, 能得到較好的相似度(比對分數)


1.說明
最簡單的比對是兩個字串作線性的比對, 此是比對只有兩種情形發生 match 與 mismatch,
e.g
CATCCGA alignment CAAAGCGA, 最後是只有兩個字母像似.

CATCCGA
CAAAGCGA
CA******

但是若能使用 gap 則字串就能分開以求得最好的相似度, 但是此時會產生不同 gap 方式, 如
gap 1:
C-A--TCCGA
CAAAG-CAGA
此時有 3 個 gap, 連續的分開算一個

gap 2:
CA---TCCGA
CAAAG-CAGA
有 2 個 gap

gap ....

2. 有 gap 後, 兩字串最像的計分方式;
通常會需要從許多不同分開 gap 字串中, 計算哪一組的分數最高,
已得到兩字串最像的結果.

Score Formula:(計分的方式, 可以據不同的應用或人而定)
if xi and yi is match score is 2,
if xi and yi is not match score is -1,
if this region is gap, the score is -(4 + k), k is the consecutive gap

例如:
gap 1 is
2 - (4+1) + 2 - (4+2) - (4+1) + 2 - 1 = -7
gap 2 is
2 - (4+3) - (4+1) +2 - 1 + 4 = -3

如而最好的字串比對是
CA--TCCGA
CAAAGCAGA score = 3









2. 參考:
Gap Punishment Aligment Problem(DP):

3. 進階閱讀:
affine gap cost -http://homepage.usask.ca/~ctl271/857/affine_gap_penalties.shtml

Online document(Algorithms for SP-optimal multiple alignments): http://lectures.molgen.mpg.de/online_lectures.html

Gap costs for multiple sequence alignment (paper)
Logarithmic gap costs decrease alignment accuracy(paper)

sequencing problem:
http://seqcore.brcf.med.umich.edu/doc/dnaseq/interpret.html