动态规划
- 前言
- 一、LCS问题
-
- 1. 子序列
- 2. 公共子序列
- 二、Needleman Wunsch
- 三、Smith Waterman算法
- 四、算法实现(函数式)
- 五 算法实现(面向对象)
-
- aligner.h
- aligner.cpp
- main.cpp
- 总结
前言
序列比较是生物信息学中一个非常重要的概念，在生物数据的分析起着不可或缺的作用。目前，绝大多数序列比较工具都包含了基于动态规划的序列比较步骤。序列比较问题类似于最长的公共子序列问题 ，然后衍生出尼德曼-翁施算法的全局比较算法 史密斯-沃特曼算法与局部比较 。
一、LCS问题
1. 子序列
若给出序列 X = { x 1 , x 2 , . . . , x m } X = \{x_1,x_2,...,x_m\} X={
x1,x2,...,xm}，还有另一个序列 Z = { z 1 , z 2 , . . . , z k } Z=\{z_1,z_2,...,z_k\} Z={
z1
2. 公共子序列
给出两条序列 X X X和 Y Y Y，如果序列 Z Z Z是序列 X X X和 Y Y Y的共同的子序列，则称 Z Z Z为序列 X X X和 Y Y Y的公共子序列。 设 Z = { z 1 , z 2 , . . . , z k } Z=\{z_1,z_2,...,z_k\} Z={ z1,z2,...,zk}是序列 X = { x 1 , x 2 , . . . , x m } X=\{x_1,x_2,...,x_m\} X={ x1,x2,...,xm}与序列 Y = { y 1 , y 2 , . . . , y n } Y=\{y_1,y_2,...,y_n\} Y={ y1,y2,...,yn}的最长公共子序列，则有： （1）如果 x m = y n x_m=y_n xm=yn，则有 z k = x m = y n z_k=x_m=y_n zk=xm=yn，并且 Z k − 1 Z_{k-1} Zk−1是序列 X m − 1 X_{m-1} Xm−1与 Y n − 1 Y_{n-1} Yn−1的最长公共子序列； （2）如果 x m ≠ y n x_m \neq y_n xm=yn，且 z k ≠ x m z_k \neq x_m zk=xm，则序列 Z Z Z是序列 X m − 1 X_{m-1} Xm−1和序列 Y Y Y的最长公共子序列； （3）如果 x m ≠ y n x_m \neq y_n xm=yn，且 z k ≠ y n z_k \neq y_n zk=yn，则序列 Z Z Z是序列 X X X和序列 Y n − 1 Y_{n-1} Yn−1的最长公共子序列；
由此可见，两个序列的最长公共子序列包含两个序列前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。 根据最长公共子序列问题的最优子结构性质，可以建立子问题最优值的递归关系。使用 c [ i ] [ j ] c[i][j] c[i][j]表示序列 X i = { x 1 , x 2 , . . . , x i } X_i=\{x_1,x_2,...,x_i\} Xi={ x1,x2,...,xi}与序列 Y j = { y 1 , y 2 , . . . , y j } Y_j=\{y_1,y_2,...,y_j\} Yj={ y1,y2,...,yj}的最长公共子序列的长度。当 i = 0 i=0 i=0或者 j = 0 j=0 j=0时，显然最长公共子序列是空的，此时 c [ i ] [ j ] = 0 c[i][j]=0 c[i][j]=0。进而可以根据最优子结构特性构建递归关系，如下所示： c [ i ] [ j ] = { 0 , i = 0 ∨ j = 0 c [ i − 1 ] [ j − 1 ] + 1 , i , j > 0 ∧ x i = y j max { c [ i ] [ j − 1 ] , c [ i − 1 ] [ j ] } , i , j > 0 ∧ x i ≠ y j \begin{equation} c[i][j]= \begin{cases} 0, & i=0 \vee j=0 \\ c[i-1][j-1]+1, & i,j > 0 \land x_i=y_j \\ \max\{c[i][j-1], c[i-1][j]\}, & i,j>0 \land x_i\neq y_j \end{cases} \end{equation} c[i][j]=⎩ ⎨ ⎧0,c[i−1][j−1]+1,max{ c[i][j−1],c[i−1][j]},i=0∨j=0i,j>0∧xi=yji,j> 标签： 5tj5zk连接器1208tj2连接器2431tj62连接器