计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (36): 48-50.DOI: 10.3778/j.issn.1002-8331.2008.36.013

• 理论研究 • 上一篇    下一篇

双序列比对的算法研究

吴德敏1,2,陈 俊3   

  1. 1.武汉大学 师资培训中心,武汉 430072
    2.武汉大学 计算机学院,武汉 430072
    3.武汉大学 信息管理学院,武汉 430072
  • 收稿日期:2008-08-01 修回日期:2008-10-23 出版日期:2008-12-21 发布日期:2008-12-21
  • 通讯作者: 吴德敏

Research on algorithm of pairwise alignment

WU De-min1,2,CHEN Jun3   

  1. 1.Teachers Training Center of Wuhan University,Wuhan 430072,China
    2.School of Computer,Wuhan University,Wuhan 430072,China
    3.School of Information Management,Wuhan University,Wuhan 430072,China
  • Received:2008-08-01 Revised:2008-10-23 Online:2008-12-21 Published:2008-12-21
  • Contact: WU De-min

摘要: 双序列比对是生物信息学中最基本的问题之一,其研究方法是设计具有针对性的有效算法对两个DNA或蛋白质序列进行比较,找出两者之间的最大相似性匹配进而判断其是否具有同源性。详尽分析了双序列比对的实际意义,提出最佳比对不一定能反映进化的实际过程并给予分析,重点探讨了最重要的全局比对算法——Smith Waterman算法,同时提出了一种用数组记录比对过程中遍历路径的方法并对比对过程进行递归调用,使之能找出全部具有最大相似性的比对结果。

Abstract: Pairwise alignment is one of the major problems in bioinformatics,the solution to which is to devise pertinent and efficient algorithms to discern the most similar matching between two sequences of DNA or protein through some certain algorithms,and then to establish whether the two enjoy the quality of the same source.In the careful examination of the practical importance of pairwise alignment,the article suggests and illustrates that the best alignment may not necessarily reflect the actual process of evolution.Emphasis lays upon the most important one——general alignment algorithm(Smith Waterman’s algorithm).Finally,the paper puts forward a way by which all the passed routes can be recorded with arrays in the process of alignment,which,by means of recursion,is able to be transferred to a certain use so that the most similar result of alignment can be located.