fulltext.study @t Gmail

An efficient similarity search based on indexing in large DNA databases

Paper ID Volume ID Publish Year Pages File Format Full-Text
15345 1405 2010 6 PDF Available
Title
An efficient similarity search based on indexing in large DNA databases
Abstract

Index-based search algorithms are an important part of a genomic search, and how to construct indices is the key to an index-based search algorithm to compute similarities between two DNA sequences. In this paper, we propose an efficient query processing method that uses special transformations to construct an index. It uses small storage and it rapidly finds the similarity between two sequences in a DNA sequence database. At first, a sequence is partitioned into equal length windows. We select the likely subsequences by computing Hamming distance to query sequence. The algorithm then transforms the subsequences in each window into a multidimensional vector space by indexing the frequencies of the characters, including the positional information of the characters in the subsequences. The result of our experiments shows that the algorithm has faster run time than other heuristic algorithms based on index structure. Also, the algorithm is as accurate as those heuristic algorithms.

Keywords
Similarity search; Approximate string matching; Indexing; DNA sequence
First Page Preview
An efficient similarity search based on indexing in large DNA databases
Publisher
Database: Elsevier - ScienceDirect
Journal: Computational Biology and Chemistry - Volume 34, Issue 2, April 2010, Pages 131–136
Authors
, , , ,
Subjects
Physical Sciences and Engineering Chemical Engineering Bioengineering