分块递归序列比对算法

利用分块递归的思想,结合检查点计算方法,提出一种线性空间复杂度序列比对算法,对于给定长为m和n的2条序列,空间需求约5(m+n)+Lsmin(m-1,n-1)+C2~5(m+n)+Ls(m+n-2)+C2,而时间需求一般情况下约1.5mn^3mn,在待比对序列相似度较高时约1.5mn^2mn,并通过同源物种全基因组序列比对实验证明,如果归一化编辑距离小于0.25,那么该算法比Hirschberg算法快10%以上.

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

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