Volume 3 Number 2 (Mar. 2013)
Home > Archive > 2013 > Volume 3 Number 2 (Mar. 2013) >
IJBBB 2013 Vol.3(2): 145-148 ISSN: 2010-3638
DOI: 10.7763/IJBBB.2013.V3.183

Approximate String Matching for Searching DNA Sequences

Jolanta Kawulok
Abstract—This paper presents a new algorithm for searching short fragments of sequences in long DNA sequences. A short sequence (pattern) is searched in both DNA strands with a given maximal value of errors. Each DNA sequence (T) is preprocessed by compressing it using Burrows-Wheeler transform and wavelet tree. First, the pattern is divided into short words which overlap themselves, and then their positions in T are determined using FM-index. Connections between the words are searched under the assumption of an acceptable maximal error allowed. Experimental results indicate that the algorithm is highly effective and it outperforms a popular Basic Local Alignment Search Tool (BLAST) in case of searching for short sequences.

Index Terms—Approximate string matching, compressed index, wavelet tree

J. Kawulok is with the Institute of Informatics, Silesian University of Technology, Gliwice, Poland (e-mail: jolanta.kawulok@polsl.pl).


Cite:Jolanta Kawulok, "Approximate String Matching for Searching DNA Sequences," International Journal of Bioscience, Biochemistry and Bioinformatics vol. 3, no. 2, pp. 145-148, 2013.

General Information

ISSN: 2010-3638
Frequency: Bimonthly (2011-2015); Quarterly (Since 2016)
DOI: 10.17706/IJBBB
Editor-in-Chief: Prof. Ebtisam Heikal 
Abstracting/ Indexing: Electronic Journals Library, Chemical Abstracts Services (CAS), Engineering & Technology Digital Library, Google Scholar, and ProQuest.
E-mail: ijbbb@iap.org
  • Jan 05, 2017 News!

    [CFP] 2017 the annual meeting of IJBBB Editorial Board, ICOCB 2017, will be held in Jakarta, Indonesia during May 24-26, 2017. [Click]

  • Sep 22, 2017 News!

    IJBBB Vol. 8, No. 1 has been published online!  [Click]

  • Sep 12, 2017 News!

    The papers published in Vol. 7, No. 4 have all received dois from Crossref. [Click]

  • Aug 29, 2017 News!

    IJBBB Vol. 7, No. 4 has been published online!  [Click]

  • Jun 12, 2017 News!

    The papers published in Vol. 7, No. 3 have all received dois from Crossref. [Click]

  • Read more>>