论文部分内容阅读
序列比对是生物信息学中一个基本的问题。在序列比对中广泛使用的三种算法有Needleman-Wunsch算法、Hirschberg算法和FastLSA算法，而FastLSA算法是这三种算法中效率最高的算法。 为了进一步改进FastLSA算法性能，本论文利用一个简单而有效的“波阵线机制”对FastLSA算法进行了并行化处理，本文称这种经过并行处理的FastLSA算法为并行FastLSA算法。相对于FastLSA算法，本文的并行FastLSA算法进一步改进了时间性能，同时保持使用线性空间。 本论文也详细的描述了并行FastLSA算法的实验环境：PC并行机群系统，LINUX操作系统及其软件分布式共享内存系统(DSM)。本论文同时也分析了并行FastLSA算法的效率以及理论上和实际上的算法的性能。而且，从实验的结果上也展示了并行FastLSA算法在PC机群系统中具有好的加速比，并且随着被比对的序列的长度的增加，算法的效率会变得更好。