一种优化的三序列比对算法及并行实现

Optimal Alignment of Three Sequences and Parallelization

序列比对算法在许多不同的领域得到应用。当前,一个重要的应用就是比对大分子,例如DNA和蛋白质序列比对。许多情况,有必要比对三序列。DavidR.Powell就提出过一种使用线性空位罚分的优化的三序列比对算法。这个算法最早是由Ukkonen提出的,该算法基于简单打分的两序列比对。该文通过引入“检查点法”对其进行改进,并充分利用近期蓬勃发展的高性能计算技术,对算法并行化,且在cluster机上实现。

Sequence alignment algorithms are used in a number of different areas.Currently,one of these important areas is the aligning of macro-molecules such as DNA sequences and protein sequences.For many applications,it is desirable to align three sequences at a time.A new algorithm is presented to align three sequences optimally using linear gap costs by David R.Powell.This algorithm is an extension of the two sequences and simple cost algorithm by Ukkonen(1983).This paper modifies the algorithm by using check point technology,implements it on clustering computers,and parallelize s the algorithm by using the high-performance computing technology.