2.4 Supplementary materials

2.4 补充材料 同源、相似性、相似性矩阵、点阵图

S1: Alignment with Affine Gap Penalty——对于空位罚分的改进

第一节 罚分：区分 opening和 extending 并对此线性组合

第二三节 罚分：不区分opening 和extending 统一用 d

这一节 分三个状态M、X、Y

将之前的罚分分成了d和e两种，如果是第一个gap，罚分就为d，如果是接着前面的gap后面还是gap，那后面那个gap的罚分就是e，故叫做open gap即开场，叫做extension gap即延续

例：

• 第一种

  

  当前的是Xi对比上Yj

  1、如果前一个也是match对比成功，那就是前面的分加上替换矩阵对应的分

  2、如果前一个是Xi对比上空位，那就是用前面X的分加上替换矩阵对应的分

  3、如果前一个是Yj对比上空位，那就是用前面X的分加上替换矩阵对应的分
  最终结果取这三者中的最大值

• 第二种

  

  当前的是Xi对比上空位即gap

  1、如果前一个是match对比成功，那就是当前空位是open gap 开头的gap 即罚分为d

  2、如果前一个是Xi对比上空位，那就是当前空位是extension gap 是延续上一个gap的gap 即罚分为e

• 第三种

  

  当前的是Yj对比上空位即gap

  1、如果前一个是match对比成功，那就是当前空位是open gap 开头的gap 即罚分为d

  2、如果前一个是Yj对比上空位，那就是当前空位是extension gap 是延续上一个gap的gap 即罚分为e

时间复杂度分析

从穷举的指数级别降低到了平方级别

S2 解释几种概念

• Homology & Similarity

  • Homology

    — derived from a common ancestor 来源于共同祖先

    — ortholog: derived from speciation 直系同源 不同物种中的两个序列来自历史上的共同祖先的同一个序列

    

    — paralog: derived from duplication 旁系同源 同一物种中的两个序列在历史上来自同一个序列

    

• Similarity Matrix——相似矩阵

  • For nucleotides,

    • usually only distinguish match / mismatch (identity matrix) for sequence alignment
    • but a more complicated substitution model is used for phylogeny reconstruction
    

  • For amino acids

    • PAM (1978, Margaret Dayhoff)

      • Two sequnences are 1 PAM apart if they differ in 1% of the residues

      • 1 PAM = one step of evolution

        

    • BLOSUM (1992, Steven Henikoff & Jorja Henikoff)

      • computed by looking at “blocks” of conserved sequences found in multiple protein alignments
      

• Dot Matrix