Fast Filter-and-Refine Algorithms for Subsequence Selection

• Main Authors: OOI, Beng-Chin, PANG, Hwee Hwa, WANG, Hao, WONG, Limsoon, YU, Cui
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2002
• Subjects: DNA sequences; approximate subsequence matching; biology; bitmap indexing structure; data sequence condensing; data sequence encoding; false positive removal; fast filter-and-refine algorithms; gene sequences; index sequence; large DNA sequence databases; large sequence databases; protein sequences; query processing; query string; response time; small space overhead; subsequence selection; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/1144; https://ink.library.smu.edu.sg/context/sis_research/article/2143/viewcontent/FastFilterandRefine_edited_.pdf
• Institution: Singapore Management University

Large sequence databases, such as protein, DNA and gene sequences in biology, are becoming increasingly common. An important operation on a sequence database is approximate subsequence matching, where all subsequences that are within some distance from a given query string are retrieved. This paper...