生物信息学作业SC13231008王飞序列分析中基本问题是如何计算的？答：以序列的相似性分析为例，比如DNA序列，给定两段序列来确定两段序列的相似程度。相似程度的大小需要一个指标，于是对两条序列相似性的判断即转化为此指标的数值大小。求解问题也转变为对此指标的寻找，在此选取最长共同子序列作为一个判断两序列相似性的指标。我们规定，两条序列只允许有插入和删除的操作。比如序列：ATGATTA和ATCGTA,容易看出其最长共同子序列为ATGTA.但是对于较长的序列，一般难以直接找出最长共同子序列，需要找到一个算法求解。1.首先需要建立一个计算模型。构建一个如下图所示的联配矩阵，ATGA-TTAAT-CGT-A设两个序列的长度分别为m，n，要求不能有一列都没有元素，列数l应满足max(m,n)<=l<=m+n，若同一列上下两行的碱基相同，称为匹配，得1分，否则为失配，得0分。于是寻找最长共同子序列的问题就转化为求最大总得分函数的问题。所有可能的匹配矩阵中必然存在一个得分最大的，对应最长共同子序列。2.选择动态规划算法。长度分别为m，n的序列V,W，它们的共同序列满足：1≤푗1≤푗2≤⋯≤푗푘≤푚,1≤푖1≤푖2≤⋯≤푖푘≤푛,푣푗푡=푤푖푡(1≤t≤k)构建一个m*n的二维编辑图，如下，v=ATCTGAT,W=TGCATA,AB蓝色表示权值为0的路线，行和列元素相同时增加一条权值为1的路线，图中橙色所示，即为求从A到B的加权最长路径问题。3求解方法欲求到B点的最大路径，先求出B点之前个点的最大路径长度。设A点坐标为푆0,0,对一点푆푖,푗,有递推公式：푆푖−1,푗푆푖,푗=푚푎푥{푆푖,푗−1(푠푖,0=푠0,푗=0)푆푖−1,푗−1+1,(푖푓푣푖=푤푗)可选的方法有递归算法和动态规划算法，考虑递归过程耗时较长，所以选用动态规划。从前到后计算每一点的最长路径长度，得到一个最长路径表。i,j01234560000000010000111201111223011222240112233501222336012233470122344所以最长共同子序列的长度为4.算法：要求找出两个字符串中共同的最长子序列。输入：两个字符串v，w输出：字符串v，w的最长共同子序列伪代码：LCS（v,w）Fori=0tomS(I,0)=0;Forj=0tonS(j,0)=0;Fori=1tomForj=1ton푆푖−1,푗푆푖,푗=푚푎푥{푆푖,푗−1푆푖−1,푗−1+1,(푖푓푣푖=푤푗)"↓"푖푓푠푖,푗=푠푖−1,푗"→"푖푓푠푠푏푖,푗={푖,푗=푖,푗−1↘푖푓푠푖,푗=푠푖−1,푗−1+1Return(푠푚,푛,푏)算法小结：动态规划算法首先将序列匹配的问题转化为可以通过得分来评判的模型，又把这种得分模型放到一个带权的有向无圈图中变成了寻找最长路径的问题，从而把生物问题与常见的计算方法联系起来，在我看来是很有创造性的思路。后面通过动态规划算法来解决也简便易行。参考文献：N.C.琼斯，P.A.趴伏纳著，生物信息学算法导论，王翼飞等译，化学工业出版社，2007,132-139