文献类型：会议

作　　者：李永光 王镝 王国仁 马宜菲

作者单位：东北大学信息科学与工程学院计算机系统研究所

基　　金：教育部高等学校优秀青年教师教学科研奖励计划基金资助项目;国家自然科学基金(60273079,60473074)资助

会议文献：第二十二届中国数据库学术会议论文集（研究报告篇）

会议名称：第二十二届中国数据库学术会议

会议日期：20050819

会议地点：中国内蒙古呼和浩特

主办单位：中国计算机学会数据库专业委员会

出版单位：《计算机科学》杂志社

出版日期：20050819

学会名称：中国计算机学会数据库专业委员会

语　　种：中文

摘　　要：A common query against large protein and gene sequence data sets is to locate targets that are similar to an input query sequence.The current set popular search tools,such as BLAST,employ heuristics to improve the speed of such searches.However,such heuristics can sometimes miss targets,which in many cases is undesirable.The alternative to BLAST is to use an accurate algorithm,Such as Smith-Waterman(S-W) algorithm.However,these accurate algorithms are computationally very expensive.Recently,a new technique,OASIS,has been proposed to improve the efficiency and accuracy by employing dynamical programming during traversing suffix tree and its speed is comparable to BLAST.But its main drawback is too much memory consuming.We propose an efficient and accurate algorithm for locally aligning genome sequences.We construct a block sorting index structure for the large sequence. The index structure is less than the suffix tree index and can be fit for large data size.Experimental results show that our algorithm has better performance than OASIS.

关 键 词：SEQUENCE Block sorting index  ACCURACY

分 类 号：Q7]