用互关联后继树模型实现一个局部相似性比对算法

对基因数据库的一种常见操作是找到与待查询序列相似的序列.目前常使用的是BLAST算法,但是这种启发式算法有时会漏解.如果使用精确匹配算法,例如Smith-Waterman(S-W)算法,计算代价又会太大.OASIS算法是一种高效并且精确的生物序列局部相似性比对算法,而且互关联后继树模型的空间效率很高,因此使用互关联后继树实现了OASIS,并命名为OASISirst算法,其比对结果和OASIS一样按照得分降序排列,并且当目标序列和查询序列均较长时,时间优势明显.