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

A Local Alignment Algorithm Implemented with Inter-Related Suffix Tree Model

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

A common operation of gene database is to search for sequence similar to query sequence. The Heuristics-Based search tool BLAST is used currently, but some targets may be missed when using this tool. Accurate algorithms, such as S- W, are computationally prohibitive. OASIS is an effective and accurate local alignment algorithm for biological sequence. Inter-Related Suffix Tree （IRST） has good space utilization. OASISirst is a new algorithm based on OASIS and IRST. OA- SISirst returns research results in descending order of match score as OASIS. But it is faster in searching than OASIS when target and query sequences are long.