Featheast Lee 李羽东

1. DNA, RNA和蛋白质序列都可以被看作为字符串，字符串的搜索算法有：Horspool/Boyer-Moore. KMP, Rabin-Karp, Suffix-trees。和生物学有关的方面包括：近似匹配，因为测序错误或者进化（在物种内部或之间）。我们需要寻找的是相似的字符串，部分匹配，能够达到近似的测量值。

2. 测量两个序列之间的距离：Euclidean距离，City Block距离，Hanmming距离
Edit距离是最小的操作数目来吧一个字符串转换为另一个字符串，操作包括插入/删除，和替换
优点：对生物进化的建模，考虑了序列相关的可能性；缺点：可能与实际的进化过程不符合，通常情况下两个相关的DNA片段是继承自同一祖先，而不是相互。

3. 序列比对
全局比对：插入空格，在中间或者序列1和序列2的结尾；将一个序列放在另一个序列的上方，使得每个字符都是另一个字符对应的或者是空格。
DPA算法：动态编程来计算出比对的最小值，两步：计算通过递归关系得到距离，回溯。
代表算法：Needleman-Wunsch算法
局部比对，代表算法：Smith-Waterman算法