Bioinfomatics & Algorithm
2010-07-05 21:34:28| 分类:
biomed
| 标签:
|举报
|字号大中小 订阅
基因学的一个主要主题就是比较 DNA 序列并尝试找出两个序列的公共部分。如果两个 DNA 序列有类似的公共子序列,那么这些两个序列很可能是同源的。在比对两个序列时,不仅要考虑完全匹配的字符,还要考虑一个序列中的空格或间隙(或者,相反地,要考虑另一个序列中的插入部分)和不匹配,这两个方面都可能意味着突变。在序列比对中,需要找到最优的比对(最优比对大致是指要将匹配的数量最大化,将空格和不匹配的数量最小化)。如果要更正式些,您可以确定一个分数,为匹配的字符添加分数、为空格和不匹配的字符减去分数。
利用双序列的比对(pairwise alignment)可显示出序列间的类似性,也是多序列比对算法的基础。对已知的两个序列,要进行序列比对,要发现这两个序列之间的距离(Edit Distances),就是要计算序列之间的相似匹配程度。核心思想都是利用动态规划解决查找DNA序列最长公共子序列问题(longest common subsequence, LCS),LCS 越长,两个序列越相似。
比对算法的种类
1).全局比对
寻找在全长范围内寻找最佳比对, Needleman-Wunsch algorithm
2).局部比对
寻找局部区域的最高比对打分,这决定了局部比对的实际应用更加广泛。
Smith-Waterman algorithm
在 Smith-Waterman 算法中,不必比对整个序列。两个零长字符串即为得分为 0 的局部比对,这一事实表明在构建局部比对时,不需要使用负分。这样会造成进一步比对所得到的分数低于通过"重设"两个零长字符串所能得到的分数。而且,局部比对不需要到达任何一个序列的末端,所以也不需要从右下角开始回溯:可以从得分最高的单元格开始回溯。
http://www.ibm.com/developerworks/cn/java/j-seqalign/
评论这张
转发至微博
转发至微博
评论