数据比对

生物学问题：比较两个序列的相似度

目的：通过序列的相似性，推测结构和功能的联系

蛋白质测序结果图解读：

竖线：相同残基；点：两比对序列在该位点残基替换后得分大于0；冒号：替换后得分小于0；虚线：表示空位即插入或删除（indel=insertion/deletion）

总分：根据残基的相同及差异、残基替换得分、indel得分算出来的总分数

双序列比对的算法

数据：两条序列

设定参数：可以对给定的比对结果进行量化的打分函数

输出：可是比对最大化的比对结果即最优比对结果（maximal score）

应用算法：

dynamic programming（动态规划算法）：将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

最优解定义（百度）：数学规划的基本概念之一。指在数学规划问题中，使目标函数取最小值（对极大化问题取最大值）的可行解。使目标函数取最小值的可行解称为极小解，使其取最大值的可行解称为极大解。极小解或极大解均称为最优解。相应地，目标函数的最小值或最大值称为最优值。有时，也将最优解和最优值一起称为相应数学规划问题的最优解。判定方法：最小二乘法估计、最大似然值估计、贝叶斯估计。

全局比对（global alignment）：对从头到尾比对所有序列

局部部比对（local alignment）：虽然两条序列差异很大，但是局部可能存在功能相近或相同的结构片段，所以产生了局部比对