title: A fast algorithm for exact sequence search in biological sequences using polyphase decomposition.
abstract: 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.
authors.affiliation: Samsung Advanced Institute of Technology, Bangalore, Karnataka, India. s.abhilash@samsung.com
authors.forename: Abhilash
authors.initials: A
authors.lastname: Srikantha
authors.forename: Ajit S
authors.initials: AS
authors.lastname: Bopardikar
authors.forename: Kalyan Kumar
authors.initials: KK
authors.lastname: Kaipa
authors.forename: Parthasarathy
authors.initials: P
authors.lastname: Venkataraman
authors.forename: Kyusang
authors.initials: K
authors.lastname: Lee
authors.forename: TaeJin
authors.initials: T
authors.lastname: Ahn
authors.forename: Rangavittal
authors.initials: R
authors.lastname: Narayanan
mesh_terms: 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*
references.citation: Genome Res. 2001 Oct;11(10):1725-9
references.pmid: 11591649
references.citation: Genome Biol. 2004;5(2):R12
references.pmid: 14759262
references.citation: J Mol Biol. 1990 Oct 5;215(3):403-10
references.pmid: 2231712
references.citation: Science. 1985 Mar 22;227(4693):1435-41
references.pmid: 2983426
references.citation: Bioinformatics. 2010 Mar 1;26(5):589-95
references.pmid: 20080505
references.citation: Proc Natl Acad Sci U S A. 1988 Apr;85(8):2444-8
references.pmid: 3162770
references.citation: Bioinformatics. 2002 Mar;18(3):440-5
references.pmid: 11934743
references.citation: N Engl J Med. 2009 Apr 2;360(14):1408-17
references.pmid: 19339720
references.citation: Gene. 2002 Oct 30;300(1-2):105-15
references.pmid: 12468092