A fast algorithm for exact sequence search in biological sequences using polyphase decomposition.
Exact sequence search allows a user to search for a specific DNA subsequence in a larger DNA sequence or database. It serves as a vital block in many areas such as Pharmacogenetics, Phylogenetics and Personal Genomics. As sequencing of genomic data becomes increasingly affordable, the amount of sequence data that must be processed will also increase exponentially. In this context, fast sequence search algorithms will play an important role in exploiting the information contained in the newly sequenced data. Many existing algorithms do not scale up well for large sequences or databases because of their high-computational costs. This article describes an efficient algorithm for performing fast searches on large DNA sequences. It makes use of hash tables of Q-grams that are constructed after downsampling the database, to enable efficient search and memory use. Time complexity for pattern search is reduced using beam pruning techniques. Theoretical complexity calculations and performance figures are presented to indicate the potential of the proposed algorithm.
Srikantha
Abhilash
A
Samsung Advanced Institute of Technology, Bangalore, Karnataka, India. s.abhilash@samsung.com
Bopardikar
Ajit S
AS
Kaipa
Kalyan Kumar
KK
Venkataraman
Parthasarathy
P
Lee
Kyusang
K
Ahn
TaeJin
T
Narayanan
Rangavittal
R
D000465:Algorithms; D001483:Base Sequence; D002878:Chromosomes, Human, Pair 1; D030541:Databases, Genetic; D023281:Genomics / Q000379:methods*; D006801:Humans; D017422:Sequence Analysis, DNA / Q000379:methods*
Genome Res. 2001 Oct;11(10):1725-9
11591649
Genome Biol. 2004;5(2):R12
14759262
J Mol Biol. 1990 Oct 5;215(3):403-10
2231712
Science. 1985 Mar 22;227(4693):1435-41
2983426
Bioinformatics. 2010 Mar 1;26(5):589-95
20080505
Proc Natl Acad Sci U S A. 1988 Apr;85(8):2444-8
3162770
Bioinformatics. 2002 Mar;18(3):440-5
11934743
N Engl J Med. 2009 Apr 2;360(14):1408-17
19339720
Gene. 2002 Oct 30;300(1-2):105-15
12468092