Abstract: 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 optimal solution. For multiple sequences alignment, the shortest path seeked in the N-dimensional space can be obtained in the two-dimensional space. It can be proved that the problem is greatly simplified and the sub-optimal solution can be obtained.

Key words: sequence alignment, Dijkstra algorithm, shortest path, directed acyclic graph

摘要： 提出一种基于Dijkstra算法的序列比对方法，该算法主要用于求最短路径，而序列比对可以转化为在有向无环图中寻找最短路径问题。对于少量序列比对，使用该算法可以求出最优解。对于多序列比对，可将在N维空间求解最短路径问题转化为在二维空间求解最短路径。该算法可以简化问题复杂度，能求得相对最优解。

关键词: 序列比对, Dijkstra算法, 最短路径, 有向无环图