基于高分片段对的双序列比对分治算法SPDCA

Pairwise Sequence Alignment Based on High-segment Pairs

针对传统双序列比对算法的高时空复杂性,在动态规划比对算法的基础上,引入了片段对和分治思想,提出了一个新型的基于高分片段对的分治算法.模拟结果表明:该算法在降低了双序列比对算法的时空需求的同时,还能发现双序列之间微弱的相似关系,可适用于序列数据库相似性的搜索.

The traditional algorithm for pairwise sequence alignment has the high complexity of time and space. Based on the dynamic programming alignment algorithm, high-segment pairs, divide and conquer are introduced. Furthermore, a new alignment algorithm called SPDCA is deduced. Simulation results show that the algorithm lower pairwise sequence alignment algorithm＇s requirement of time and space, that it can help find the subtle similarity between pairwise sequences, and thus that it is applicable to the search of sequence database similarity.