论文部分内容阅读
序列联配算法是生物信息处理中非常重要的一类算法,最基本的序列联配算法是动态规划算法,其时间和空间复杂度都为O(m×n),(其中m和n为两序列的长度).实际应用中,该算法的空间复杂度是限制问题规模的瓶颈.Hirschberg在1975年提出的算法减少了序列联配问题的空间需求,其空间复杂度为O(m+n),但是Hirschberg算法的时间需求是基本动态规划算法的两倍.文章提出一种新的序列联配算法Fast Alignment(FA),FA算法的时间复杂度和空间复杂度介于基本动态规划算法和Hirschb