存储约束条件下的序列联配算法

Sequences Alignment Algorithm with Memory Constraints

序列联配算法是生物信息处理中非常重要的一类算法,最基本的序列联配算法是动态规划算法,其时间和空间复杂度都为O(m×n),(其中m和n为两序列的长度)。实际应用中,该算法的空间复杂度是限制问题规模的瓶颈。Hirschberg在1975年提出的算法减少了序列联配问题的空间需求,其空间复杂度为O(m+n),但是Hirschberg算法的时间需求是基本动态规划算法的两倍。文章提出一种新的序列联配算法FastAlignment(FA),FA算法的时间复杂度和空间复杂度介于基本动态规划算法和Hirschberg算法之间,通过对算法参数k的调节,可以获得在不同存储条件下最小序列联配问题解决时间。

Sequence alignment is one of the most important algorithm in bioinformatics. The first algorithm that result sequence alignment problem is dynamic programming algorithm. The dynamic programming algorithm's spatial and temporal requirement all are. In real application,the spatial requirement of dynamic programming is the bottleneck. Hirschberg algorithm reduce the spatial requirement from to comparing with dynamic programming algorithm, but doubles the cost of computing time. This paper introduce a new algorithm Fast Alignment(FA),its spatial and temporal requirement is between the dynamic programming algorithm and Hirschberg algorithm. Tuning the argument k of FA algorithm,the algorithm can get the best tradeoff between available memory and computing time.