https://scholars.lib.ntu.edu.tw/handle/123456789/415129
標題: | A novel filtration method in biological sequence databases | 作者: | Lee A.J.T. Lin C.-W. Lo W.-H. Chen C.-C. Chen J.-X. |
關鍵字: | Bioinformatics;Filtration method;Sequence comparison | 公開日期: | 2007 | 卷: | 28 | 期: | 4 | 起(迄)頁: | 447-458 | 來源出版物: | Pattern Recognition Letters | 摘要: | In this paper, we propose a new filtration method, called Transformation-based Database Filtration method (TDF), to screen out those data sequences of a DNA sequence database which cannot satisfy a given query sequence. Our proposed method consists of two phases. First, we divide each data sequence into several windows (blocks), each of which is transformed into a data feature vector using the Haar wavelet transform. The transformed data feature vectors are then stored in an index file. Second, we divide a query sequence into sliding windows, each of which is, again, transformed into a query feature vector using the Haar wavelet transform. We then search the index file to find the candidate sequences for each query feature vector and check if they match the query sequence using the sequence alignment algorithm. We transform the bound of edit distance between sequences to the bound of Manhattan distance between feature vectors. Since the Manhattan distance is much easier to compute, our proposed method can efficiently screen out impossible data sequences and guarantee no false negatives. The experimental results show that our proposed method outperforms the QUASAR method in terms of filtration ratio, precision, execution time and index size. The proposed method also outperforms the YM method for long query, low complexity and repetitive data. ? 2006 Elsevier B.V. All rights reserved. |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/415129 | ISSN: | 01678655 | DOI: | 10.1016/j.patrec.2006.08.015 |
顯示於: | 資訊管理學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。