Dijkstra算法在蛋白质序列比对中的研究  

Research of Dijkstra algorithm in protein sequence alignment

作　　者：祁长红[1] 郁芸[2] 韩新焕[2] 

机构地区：[1]南京医科大学生物医学工程系,南京210029 [2]南京医科大学数学与计算机教研室,南京210029

出　　处：《计算机工程与应用》2012年第24期122-126,148,共6页Computer Engineering and Applications

基　　金：江苏省大学生科技创新基金(No.KY101J2010004)

摘　　要：提出一种基于Dijkstra算法的序列比对方法,该算法主要用于求最短路径,而序列比对可以转化为在有向无环图中寻找最短路径问题。对于少量序列比对,使用该算法可以求出最优解。对于多序列比对,可将在N维空间求解最短路径问题转化为在二维空间求解最短路径。该算法可以简化问题复杂度,能求得相对最优解。A sequence alignment algorithm based on Dijkstra algorithm is put forward, which is mainly used to seek the shortest path while the problem of sequence alignment can be transformed into a problem to look for the shortest path in directed acyclic graph. For a small amount of sequences, Dijkstra algorithm is easier to seek the op- timal solution. For multiple sequences alignment, the shortest path seeked in the N-dimensional space can be ob- tained in the two-dimensional space. It can be proved that the problem is greatly simplified and the sub-optimal so- lution can be obtained.

关 键 词：序列比对 DIJKSTRA算法 最短路径 有向无环图 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]