注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

中吴南顾惟一笑

成功法则就是那19个字

 
 
 

日志

 
 

Bioinfomatics & Algorithm  

2010-07-05 21:34:28|  分类: biomed |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
基因学的一个主要主题就是比较 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/
  评论这张
 
阅读(124)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017